Học thuyết số học mô đun

Số học mô đun là một hệ thống toán học dành cho số nguyên, trong đó các số được sắp xếp theo vòng tròn và lặp lại cho đến khi đạt đến giá trị xác định, gọi là mô đun (tiếng Anh: modulus, số nhiều moduli). Khái niệm này được phát triển bởi nhà toán học người Đức Carl Friedrich Gauss trong tác phẩm Disquisitiones Arithmeticae, xuất bản năm 1801.

Đồng dư

Với một số nguyên n > 1, gọi là mô đun, hai số nguyên a và b được coi là đồng dư modulo n nếu hiệu của chúng chia hết cho n (tức là, tồn tại số nguyên k sao cho a − b = kn).

Đồng dư mô đun n là một dạng quan hệ đồng dư, có tính chất tương đương và bảo toàn khi thực hiện các phép cộng, trừ, và nhân. Quan hệ đồng dư mô đun n thường được ký hiệu như sau:

$a\equiv <!--\; \equiv \; -->b\left(\mathrm{mod}n\right).$

Dấu ngoặc (mod n) áp dụng cho toàn bộ phương trình, không chỉ mỗi vế phải (b). Ký hiệu này khác với b mod n (không có dấu ngoặc), dùng để chỉ phép toán modulo. Cụ thể, b mod n biểu thị số dư khi chia b cho n, tức số nguyên a thỏa mãn 0 ≤ a < n và a ≡ b (mod n).

Ví dụ

Trong mô đun 12, chúng ta có thể diễn đạt như sau:

$38\equiv <!--\; \equiv \; -->14\left(\mathrm{mod}12\right)$

Bởi vì 38 − 14 = 24, một bội số của 12. Một cách khác để hiểu là cả 38 và 14 đều có cùng số dư là 2 khi chia cho 12.

Khái niệm đồng dư cũng áp dụng cho số nguyên âm, ví dụ như sau:

Các đặc điểm

Quan hệ đồng dư tuân theo các tính chất của một quan hệ tương đương:

• Tính phản xạ: a ≡ a (mod n)
• Tính đối xứng: a ≡ b (mod n) nếu và chỉ nếu b ≡ a (mod n) đối với mọi a, b
• Tính bắc cầu: nếu a ≡ b (mod n) và b ≡ c (mod n) thì a ≡ c (mod n)

Các phép toán cộng, trừ, nhân

Nếu a₁ ≡ b₁ (mod n) và a₂ ≡ b₂ (mod n), hoặc a ≡ b (mod n), thì:

• a + k ≡ b + k (mod n) với mọi số nguyên k
• k a ≡ k b (mod n) với mọi số nguyên k khác 0
• k a ≡ k b (mod kn) với mọi số nguyên k
• a₁ + a₂ ≡ b₁ + b₂ (mod n) (bảo toàn phép cộng)
• a₁ – a₂ ≡ b₁ – b₂ (mod n) (bảo toàn phép trừ)
• a₁ a₂ ≡ b₁ b₂ (mod n) (bảo toàn phép nhân)
• a ≡ b (mod n) với mọi số nguyên không âm k (bảo toàn phép mũ)
• p(a) ≡ p(b) (mod n), với mọi đa thức p(x) có hệ số nguyên (bảo toàn với đa thức)

Khi khử các hệ số ở cả hai vế, ta có những quy tắc sau đây:

• Nếu a + k ≡ b + k (mod n), với k là số nguyên tùy ý, thì a ≡ b (mod n)
• Nếu k a ≡ k b (mod n) và k là số nguyên tố cùng nhau với n, thì a ≡ b (mod n)
• Nếu k a ≡ k b (mod kn), thì a ≡ b (mod n)

Tính mũ

Từ a ≡ b (mod n) không thể kết luận rằng k ≡ k (mod n). Ví dụ, 2 ≡ 5 (mod 3), nhưng 2 ≢ 2 (mod 3). Tuy nhiên, có điều sau đây là đúng:

• Nếu c ≡ d (mod φ(n)), với φ là hàm phi Euler, thì a ≡ a (mod n), nếu như a và n là nguyên tố cùng nhau.

Nghịch đảo trong phép nhân

Nghịch đảo của phép nhân theo mô đun được định nghĩa như sau:

• Đối với mỗi số nguyên a, nếu có số nguyên khác sao cho aa ≡ 1 (mod n), thì a và n phải là các số nguyên tố cùng nhau. Số nguyên a này được gọi là nghịch đảo phép nhân mô đun của a theo modulo n.
• Nếu a ≡ b (mod n) và a có nghịch đảo, thì a ≡ b (mod n).
• Nếu a x ≡ b (mod n) và a là số nguyên tố cùng nhau với n, thì nghiệm của phương trình này là x ≡ ab (mod n)

Nghịch đảo phép nhân x ≡ a (mod n) có thể được tính thông qua giải phương trình Bézout ax + ny = 1—bằng cách sử dụng thuật toán Euclid mở rộng.

Cụ thể, nếu p là số nguyên tố, thì mỗi số a nguyên tố cùng nhau với p trong khoảng 0 < a < p; do đó, nghịch đảo phép nhân của a tồn tại với mọi a không chia hết cho p.

Các thuộc tính khác

Một số thuộc tính nâng cao của quan hệ đồng dư bao gồm:

• Định lý Fermat nhỏ: Với số nguyên tố p không chia hết cho a, ta có a ≡ 1 (mod p).
• Định lý Euler: Nếu a và n nguyên tố cùng nhau, thì a ≡ 1 (mod n), trong đó φ là hàm phi Euler.
• Định lý Wilson: Số p là số nguyên tố nếu và chỉ nếu (p − 1)! ≡ −1 (mod p).
• Định lý thặng dư Trung Hoa: Với mọi a, b và m, n nguyên tố cùng nhau, tồn tại duy nhất một x (mod mn) sao cho x ≡ a (mod m) và x ≡ b (mod n). Cụ thể, x ≡ b m_n m + a n_m n (mod mn), với m_n là nghịch đảo của m modulo n và n_m là nghịch đảo của n modulo m.
• Định lý Lagrange: Một đa thức f (x) ≡ 0 (mod p), với p là số nguyên tố và f (x) = a_n x + ... + a₀ có hệ số nguyên và a₀ ≠ 0 (mod p), có tối đa n nghiệm.
• Căn nguyên thủy modulo n: Một số g được gọi là căn nguyên thủy modulo n nếu với mọi số nguyên a nguyên tố cùng nhau với n, tồn tại một số nguyên k sao cho g ≡ a (mod n). Căn nguyên thủy modulo n tồn tại khi và chỉ khi n là 2, 4, p hoặc 2p, với p là số nguyên tố lẻ và k là số nguyên dương. Nếu có tồn tại căn nguyên thủy modulo n, thì có đúng φ(φ(n)) căn nguyên thủy như vậy, với φ là hàm phi Euler.
• Thặng dư bình phương: Một số nguyên a là thặng dư bình phương modulo n nếu tồn tại số nguyên x sao cho x ≡ a (mod n). Tiêu chuẩn Euler chỉ ra rằng, nếu p là số nguyên tố lẻ và a không chia hết cho p, thì a là thặng dư bình phương modulo p nếu và chỉ nếu a ≡ 1 (mod p).

Chú thích

• John L. Berggren. 'số học mô đun'. Encyclopædia Britannica.
• Maarten Bullynck. 'Số học mô đun trước C.F. Gauss. Các hệ thống và thảo luận về vấn đề dư số trong thế kỷ 18 tại Đức Lưu trữ 2013-11-02 tại Wayback Machine'
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, và Clifford Stein. Giới thiệu về Thuật toán, Tái bản lần thứ hai. MIT Press và McGraw-Hill, 2001. ISBN 0-262-03293-7. Mục 31.3: Số học mô đun, tr. 862–868.
• Anthony Gioia, Số học, một Giới thiệu Tái bản (2001) Dover. ISBN 0-486-41449-3.
• Long, Calvin T. (1972). Giới thiệu cơ bản về Số học (ấn bản lần 2). Lexington: D. C. Heath and Company. LCCN 77171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Các yếu tố của Số học. Englewood Cliffs: Prentice Hall. LCCN 71081766.
• Sengadir, T. (2009). Toán học rời rạc và Tổ hợp. Chennai, Ấn Độ: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

Liên kết ngoài

• Hazewinkel, Michiel biên tập (2001), 'Đồng dư', Bách khoa toàn thư Toán học, Springer, ISBN 978-1-55608-010-4
• Trong bài viết về nghệ thuật mô đun Lưu trữ 2006-01-01 tại Wayback Machine, bạn có thể tìm hiểu thêm về ứng dụng của số học mô đun trong nghệ thuật.
• Weisstein, Eric W., 'Số học mô đun' từ MathWorld.
• Một bài viết Lưu trữ 2016-02-20 tại Wayback Machine về số học mô đun trên wiki GIMPS
• Số học mô đun và các mẫu trong bảng cộng và nhân
• Whitney Music Box—một minh họa âm thanh/video về toán học mô đun số nguyên