Học số học theo mô đun

Trong toán học, số học theo mô đun là phương pháp tính toán với các số nguyên dựa trên mô đun. Trong phương pháp này, các số được gán vào vòng tròn và tiếp tục lặp lại cho đến khi đạt giá trị mong muốn, gọi là mô đun (tiếng Anh: modulus, số nhiều moduli). Carl Friedrich Gauss, một nhà toán học người Đức, đã phát triển lý thuyết số học theo mô đun trong tác phẩm nổi tiếng của ông Disquisitiones Arithmeticae, xuất bản năm 1801.

Đồng dư số học

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

Đồng dư theo mô đun n là một loại quan hệ đồng dư, tức là một quan hệ tương đương tuân theo các phép toán 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 trong (mod n) áp dụng cho toàn bộ phương trình, không chỉ riêng vế phải (b). Ký hiệu này có nghĩa 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 n cho b, nghĩa là số nguyên a thỏa mãn 0 ≤ a < n và a ≡ b (mod n).

Ví dụ minh họa

Trong hệ mô đun 12, ta có thể biểu diễn như sau:

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

do 38 − 14 = 24, là bội số của 12. Một cách khác để diễn đạt điều này 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 các số nguyên âm, ví dụ như:

Đặ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 như sau:

• Phản xạ: a ≡ a (mod n)
• Đối xứng: Nếu a ≡ b (mod n), thì b ≡ a (mod n), với mọi a và b
• Bắc cầu: Nếu a ≡ b (mod n) và b ≡ c (mod n), thì a ≡ c (mod n)

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

Nếu a₁ ≡ b₁ (mod n) và a₂ ≡ b₂ (mod n), hoặc a ≡ b (mod n), thì các tính chất sau đây được thỏa mãn:

• 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ố ở hai bên, chúng ta có các quy tắc sau đây:

• Nếu a + k ≡ b + k (mod n), với k là một số nguyên bất kỳ, 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)

Về số mũ

Từ a ≡ b (mod n) không thể suy ra k ≡ k (mod n). Ví dụ, 2 ≡ 5 (mod 3), nhưng 2 ≢ 2 (mod 3). Tuy nhiên, đ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 a là số nguyên tố cùng nhau với n.

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

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

• Có tồn tại một số nguyên ký hiệu là a sao cho aa ≡ 1 (mod n) chỉ khi a nguyên tố cùng nhau với n. Số nguyên a này gọi là nghịch đảo phép nhân mô đun của a 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 nguyên tố cùng nhau với n, thì nghiệm của đồng dư thức này là x ≡ ab (mod n)

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

Cụ thể, nếu p là số nguyên tố, thì a nguyên tố cùng nhau với p đối với mọi a thỏa mãn 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 đặc điểm nổi bật khác

Một số đặc điểm nâng cao của quan hệ đồng dư bao gồm:

• Định lý Fermat nhỏ: Nếu p là số nguyên tố và không chia hết cho a, thì a ≡ 1 (mod p).
• Định lý Euler: Nếu a và n là các số nguyên tố cùng nhau, thì a ≡ 1 (mod n), trong đó φ là hàm phi Euler.
• Định lý Wilson: 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 một và chỉ một x (mod mn) sao cho x ≡ a (mod m) và x ≡ b (mod n). Cụ thể hơn, 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: Đồng nhất thức f (x) ≡ 0 (mod p), với p là số nguyên tố và f (x) = a_n x + ... + a₀ là một đa thức có hệ số nguyên sao cho a₀ ≠ 0 (mod p), có tối đa n nghiệm.
• Căn nguyên thủy modulo n: Một số g là căn nguyên thủy của 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 bằng 2, 4, p hoặc 2p, với p là số nguyên tố lẻ và k là một số nguyên dương. Nếu một căn nguyên thủy modulo n tồn tại, 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 một số nguyên x sao cho x ≡ a (mod n). Tiêu chuẩn Euler cho biết rằng, nếu p là một 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 khi và chỉ khi a ≡ 1 (mod p).

Chú giải

• John L. Berggren. 'số học mô-đun'. Bách khoa toàn thư Britannica.
• Maarten Bullynck 'Số học mô-đun trước C.F. Gauss. Hệ thống và thảo luận về các vấn đề dư 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, Ấn bả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 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 rời rạc và Tổ hợp học. Chennai, Ấn Độ: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

Liên kết bên 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à bảng nhân
• Hộp nhạc Whitney—một minh họa audio/video về toán học mô-đun số nguyên