Số học mô đun

Chiếc đồng hồ với mô đun bằng 12

Trong toán học, số học mô đun là một hệ thống số học dành cho số nguyên. Trong số học mô đun, các con số được viết bao quanh lấy nhau thành nhiều vòng tròn cho đến khi chạm đến giá trị đích, gọi là mô đun (tiếng Anh: modulus, số nhiều moduli). Bộ môn nghiên cứu số học mô đun hiện đại được nhà toán học người Đức, Carl Friedrich Gauss phát triển trong cuốn sách của ông có tên Disquisitiones Arithmeticae, xuất bản năm 1801.

Đồng dư

Với một số nguyên Bản mẫu:Math, gọi là mô đun, hai số nguyên Bản mẫu:Mvar và Bản mẫu:Mvar được gọi là đồng dư modulo Bản mẫu:Mvar, nếu hiệu của chúng chia hết cho Bản mẫu:Mvar (đó là, nếu tồn tại số nguyên Bản mẫu:Math sao cho Bản mẫu:Math).

Đồng dư mô đun Bản mẫu:Mvar là một quan hệ đồng dư, tức nó là một quan hệ tương đương tương thích với các phép cộng, trừ, và nhân. Đồng dư mô đun Bản mẫu:Mvar được ký hiệu là:

$a\equiv b(\mathrm{mod}n).$

Dấu ngoặc nghĩa là Bản mẫu:Math áp dụng cho toàn bộ phương trình, không chỉ mỗi vế phải (Bản mẫu:Mvar). Ký hiệu này mang ý nghĩa khác với Bản mẫu:Math (không có dấu ngoặc), dùng để chỉ phép toán modulo. Cụ thể hơn, Bản mẫu:Math ký hiệu số dư khi chia Bản mẫu:Mvar cho Bản mẫu:Mvar, tức số nguyên Bản mẫu:Mvar thỏa mãn Bản mẫu:Math và Bản mẫu:Math

Ví dụ

Trong mô đun 12, ta có thể viết:

$38\equiv 14(\mathrm{mod}12)$

vì Bản mẫu:Math, một bội của 12. Một cách khác để thể hiện điều này là cả 38 và 14 có cùng số dư là 2 khi chia cho 12.

Định nghĩa đồng dư cũng áp dụng cho số nguyên âm, ví dụ như:

$\begin{array}{cc}2& \equiv -3(\mathrm{mod}5)\\ -3& \equiv 7(\mathrm{mod}5)\\ -3& \equiv -8(\mathrm{mod}5)\end{array}$

Tính chất

Quan hệ đồng dư thỏa mãn các tính chất của một quan hệ tương đương:

• Phản xạ: Bản mẫu:Math
• Đối xứng: Bản mẫu:Math khi và chỉ khi Bản mẫu:Math với mọi Bản mẫu:Mvar, Bản mẫu:Mvar
• Bắc cầu: nếu Bản mẫu:Math và Bản mẫu:Math thì Bản mẫu:Math

Cộng, trừ, nhân

Nếu Bản mẫu:Math và Bản mẫu:Math hoặc Bản mẫu:Math thì:

• Bản mẫu:Math với mọi số nguyên Bản mẫu:Math
• Bản mẫu:Math với mọi số nguyên Bản mẫu:Math khác 0
• Bản mẫu:Math với mọi số nguyên Bản mẫu:Math
• Bản mẫu:Math (bảo toàn phép cộng)
• Bản mẫu:Math (bảo toàn phép trừ)
• Bản mẫu:Math (bảo toàn phép nhân)
• Bản mẫu:Math với mọi số nguyên không âm Bản mẫu:Math (bảo toàn phép mũ)
• Bản mẫu:Math, với mọi đa thức Bản mẫu:Math có hệ số nguyên (bảo toàn với đa thức)

Đối với việc khử các hệ số ở hai bên, ta có các luật sau:

• Nếu Bản mẫu:Math, với Bản mẫu:Math là số nguyên bất kì, thì Bản mẫu:Math
• Nếu Bản mẫu:Math và Bản mẫu:Math nguyên tố cùng nhau với Bản mẫu:Math, thì Bản mẫu:Math
• Nếu Bản mẫu:Math , thì Bản mẫu:Math

Số mũ

Từ Bản mẫu:Math không thể suy ra được Bản mẫu:Math. Ví dụ, Bản mẫu:Math, nhưng Bản mẫu:Math. Tuy nhiên điều sau là đúng:

• Nếu Bản mẫu:Math với Bản mẫu:Math là hàm phi Euler, thì Bản mẫu:Math—nếu như Bản mẫu:Math nguyên tố cùng nhau với Bản mẫu:Math.

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

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

• Tồn tại: có một số nguyên ký hiệu là Bản mẫu:Math sao cho Bản mẫu:Math khi và chỉ khi Bản mẫu:Math nguyên tố cùng nhau với Bản mẫu:Math. Số nguyên Bản mẫu:Math này gọi là nghịch đảo phép nhân mô đun của Bản mẫu:Mvar modulo Bản mẫu:Math.
• Nếu Bản mẫu:Math và Bản mẫu:Math tồn tại, thì Bản mẫu:Math
• Nếu Bản mẫu:Math và Bản mẫu:Math nguyên tố cùng nhau với Bản mẫu:Math, lời giải của đồng dư thức này là Bản mẫu:Math

Nghịch đảo phép nhân Bản mẫu:Math có thể được tính bằng các giải phương trình Bézout Bản mẫu:Math—dùng thuật toán Euclid mở rộng.

Cụ thể hơn, nếu Bản mẫu:Math là một số nguyên tố, thì Bản mẫu:Math nguyên tố cùng nhau với Bản mẫu:Math với mọi Bản mẫu:Math thỏa Bản mẫu:Math; do đó nghịch đảo phép nhân của Bản mẫu:Math tồn tại với mọi Bản mẫu:Mvar không chia hết cho Bản mẫu:Math.

Các tính chất khác

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

• Định lý Fermat nhỏ: Nếu số nguyên tố Bản mẫu:Math không phải là ước của Bản mẫu:Math thì Bản mẫu:Math
• Định lý Euler: Nếu Bản mẫu:Math và Bản mẫu:Math nguyên tố cùng nhau thì Bản mẫu:Math, trong đó Bản mẫu:Math là hàm phi Euler.
• Định lý Wilson: Bản mẫu:Math nguyên tố khi và chỉ khi Bản mẫu:Math.
• Định lý thặng dư Trung Hoa: Với mọi Bản mẫu:Math, Bản mẫu:Math và Bản mẫu:Math, Bản mẫu:Math nguyên tố cùng nhau, tồn tại đúng một Bản mẫu:Math sao cho Bản mẫu:Math và Bản mẫu:Math. Cụ thể hơn, Bản mẫu:Math, trong đó Bản mẫu:Math là nghịch đảo của Bản mẫu:Math modulo Bản mẫu:Math và Bản mẫu:Math là nghịch đảo của Bản mẫu:Math modulo Bản mẫu:Math.
• Định lý Lagrange: Đồng nhất thức Bản mẫu:Math, trong đó Bản mẫu:Math nguyên tố và Bản mẫu:Math là một đa thức có hệ số nguyên sao cho Bản mẫu:Math, có tối đa Bản mẫu:Math nghiệm.
• [[Căn nguyên thủy modulo n|Căn nguyên thủy modulo Bản mẫu:Mvar]]: Một số Bản mẫu:Math là căn nguyên thủy Bản mẫu:Math nếu, với mọi số nguyên Bản mẫu:Math nguyên tố cùng nhau với Bản mẫu:Math, tồn tại một số nguyên Bản mẫu:Math sao cho Bản mẫu:Math. Căn nguyên thủy modulo Bản mẫu:Math tồn tại khi và chỉ khi Bản mẫu:Math bằng Bản mẫu:Math hoặc Bản mẫu:Math, với Bản mẫu:Math là số nguyên tố lẻ và Bản mẫu:Math là một số nguyên dương. Nếu một căn nguyên thủy modulo Bản mẫu:Math tồn tại thì có đúng Bản mẫu:Math căn nguyên thủy như thế, với Bản mẫu:Math là hàm phi Euler.
• Thặng dư bình phương: Một số nguyên Bản mẫu:Math là thặng dư bình phương modulo Bản mẫu:Math nếu tồn tại một số nguyên Bản mẫu:Math sao cho Bản mẫu:Math. Tiêu chuẩn Euler nói rằng, nếu Bản mẫu:Math là một số nguyên tố lẻ, Bản mẫu:Mvar không là bội của Bản mẫu:Mvar, thì Bản mẫu:Math là thặng dư bình phương modulo Bản mẫu:Math khi và chỉ khi Bản mẫu:Math

Xem thêm

• Vành Boolean
• Đồng dư
• Phép chia
• Trường Galois
• Ký hiệu Legendre
• Mũ hóa mô đun
• Lý thuyết số
• Chu kỳ Pisano
• Căn nguyên thủy modulo n
• Luật tương hỗ bậc hai
• Các chủ đề liên quan:
  • Nhóm cyclic
  • Nhóm nhân các số nguyên modulo n
• Các định lý liên quan khác
  • Định lý Carmichael
  • Định lý số dư Trung Quốc
  • Định lý Euler
  • Định lý nhỏ Fermat
  • Định lý Lagrange (lý thuyết nhóm)

Tham khảo

• John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
• Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany Bản mẫu:Webarchive"
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Bản mẫu:Isbn. Section 31.3: Modular arithmetic, pp. 862–868.
• Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. Bản mẫu:Isbn.
• Bản mẫu:Chú thích sách
• Bản mẫu:Chú thích sách
• Bản mẫu:Chú thích sách

Liên kết ngoài

• Bản mẫu:Springer
• In this modular art Bản mẫu:Webarchive article, one can learn more about applications of modular arithmetic in art.
• Bản mẫu:MathWorld
• An article Bản mẫu:Webarchive on modular arithmetic on the GIMPS wiki
• Modular Arithmetic and patterns in addition and multiplication tables
• Whitney Music Box—an audio/video demonstration of integer modular math