Xem mã nguồn của Số học mô đun

[[Tập tin:Clock group.svg|thumb|250px|right|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 Gauß|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]] {{math|''n'' > 1}}, gọi là '''mô đun''', hai số nguyên {{mvar|a}} và {{mvar|b}} được gọi là '''đồng dư''' modulo {{mvar|n}}, nếu hiệu của chúng [[chia hết]] cho {{mvar|n}} (đó là, nếu tồn tại số nguyên {{math|''k''}} sao cho {{math|1=''a'' − ''b'' = ''kn''}}).

Đồng dư mô đun {{mvar|n}} 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 [[Phép cộng|cộng]], [[Phép trừ|trừ]], và [[Phép nhân|nhân]]. Đồng dư mô đun {{mvar|n}} được ký hiệu là:

:<math>a \equiv b \pmod n.</math>

Dấu ngoặc nghĩa là {{math|(mod ''n'')}} áp dụng cho toàn bộ phương trình, không chỉ mỗi vế phải ({{mvar|b}}). Ký hiệu này mang ý nghĩa khác với {{math|''b'' mod ''n''}} (không có dấu ngoặc), dùng để chỉ [[phép toán modulo]]. Cụ thể hơn, {{math|''b'' mod ''n''}} ký hiệu số dư khi chia {{mvar|n}} cho {{mvar|b}}, tức số nguyên {{mvar|a}} thỏa mãn {{math|0 ≤ ''a'' < ''n''}} và {{math|1=''a'' ≡ ''b'' (mod ''n'').}}

===Ví dụ===
Trong mô đun 12, ta có thể viết:

:<math>38 \equiv 14 \pmod {12}</math>

vì {{math|1=38 − 14 = 24}}, 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ư:

:<math> \begin{align}
2 &\equiv -3 \pmod 5\\
-3 &\equiv \ \ \ 7 \pmod 5\\
-3 &\equiv -8 \pmod 5
\end{align}</math>

==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ạ: {{math|''a'' ≡ ''a'' (mod ''n'')}}
* Đối xứng: {{math|''a'' ≡ ''b'' (mod ''n'')}} khi và chỉ khi {{math|''b'' ≡ ''a'' (mod ''n'')}} với mọi {{mvar|a}}, {{mvar|b}}
* Bắc cầu: nếu {{math|''a'' ≡ ''b'' (mod ''n'')}} và {{math|''b'' ≡ ''c'' (mod ''n'')}} thì {{math|''a'' ≡ ''c'' (mod ''n'')}}

===Cộng, trừ, nhân===
Nếu {{math|''a''<sub>1</sub> ≡ ''b''<sub>1</sub> (mod ''n'')}} và {{math|''a''<sub>2</sub> ≡ ''b''<sub>2</sub> (mod ''n''),}} hoặc {{math|''a'' ≡ ''b'' (mod ''n''),}} thì:
* {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''n'')}} với mọi số nguyên {{math|''k''}} 
* {{math|''k a'' ≡ ''k b'' (mod ''n'')}} với mọi số nguyên {{math|''k''}} khác 0
* {{math|''k a'' ≡ ''k b'' (mod ''kn'')}} với mọi số nguyên {{math|''k''}}
* {{math|''a''<sub>1</sub> + ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> + ''b''<sub>2</sub> (mod ''n'')}} (bảo toàn phép cộng)
* {{math|''a''<sub>1</sub> – ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> – ''b''<sub>2</sub> (mod ''n'')}} (bảo toàn phép trừ)
* {{math|''a''<sub>1</sub> ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> ''b''<sub>2</sub> (mod ''n'')}} (bảo toàn phép nhân)
* {{math|''a''<sup>''k''</sup> ≡ ''b''<sup>''k''</sup> (mod ''n'')}} với mọi số nguyên không âm {{math|''k''}} (bảo toàn phép mũ)
* {{math|''p''(''a'') ≡ ''p''(''b'') (mod ''n'')}}, với mọi [[đa thức]] {{math|''p''(''x'')}} 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 {{math|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''n'')}}, với {{math|''k''}} là số nguyên bất kì, thì {{math|''a'' ≡ ''b'' (mod ''n'')}}
* Nếu {{math|''k a'' ≡ ''k b'' (mod ''n'')}} và {{math|''k''}} nguyên tố cùng nhau với {{math|''n''}}, thì {{math|''a'' ≡ ''b'' (mod ''n'')}}
* Nếu {{math|''k a'' ≡ ''k b'' (mod ''kn'')}} , thì {{math|''a'' ≡ ''b'' (mod ''n'')}}

===Số mũ===
Từ {{math|''a'' ≡ ''b'' (mod ''n'')}} không thể suy ra được {{math|''k<sup>a</sup>'' ≡ ''k<sup>b</sup>'' (mod ''n'')}}. Ví dụ, {{math|2 ≡ 5 (mod 3)}}, nhưng {{math|2<sup>2</sup> ≢ 2<sup>5</sup> (mod 3)}}. Tuy nhiên điều sau là đúng:
* Nếu {{math|''c'' ≡ ''d'' (mod ''φ''(''n'')),}} với {{math|''φ''}} là [[hàm phi Euler]], thì {{math|''a''<sup>''c''</sup> ≡ ''a''<sup>''d''</sup> (mod ''n'')}}—nếu như {{math|''a''}} [[nguyên tố cùng nhau]] với {{math|''n''}}.

===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à {{math|''a''<sup>–1</sup>}} sao cho {{math|''aa''<sup>–1</sup> ≡ 1 (mod ''n'')}} khi và chỉ khi {{math|''a''}} nguyên tố cùng nhau với {{math|''n''}}. Số nguyên {{math|''a''<sup>–1</sup>}} này gọi là ''nghịch đảo phép nhân mô đun'' của {{mvar|a}} modulo {{math|''n''}}.
* Nếu {{math|''a'' ≡ ''b'' (mod ''n'')}} và {{math|''a''<sup>–1</sup>}} tồn tại, thì {{math|''a''<sup>–1</sup> ≡ ''b''<sup>–1</sup> (mod ''n'').}}
* Nếu {{math|''a x'' ≡ ''b'' (mod ''n'')}} và {{math|''a''}} nguyên tố cùng nhau với {{math|''n''}}, lời giải của đồng dư thức này là {{math|''x'' ≡ ''a''<sup>–1</sup>''b'' (mod ''n'')}}

Nghịch đảo phép nhân {{math|''x'' ≡ ''a''<sup>–1</sup> (mod ''n'')}}  có thể được tính bằng các giải [[Bổ đề Bézout|phương trình Bézout]] {{math|1=''ax'' + 
''ny'' = 1}}—dùng [[thuật toán Euclid mở rộng]].

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

===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ố {{math|''p''}} không phải là ước của {{math|''a''}} thì {{math|''a'' <sup>''p''–1</sup> ≡ 1 (mod ''p'').}}
* [[Định lý Euler]]: Nếu {{math|''a''}} và {{math|''n''}} nguyên tố cùng nhau thì {{math|''a'' <sup>''φ''(''n'')</sup> ≡ 1 (mod ''n'')}}, trong đó {{math|''φ''}} là [[hàm phi Euler]].
* [[Định lý Wilson]]: {{math|''p''}} nguyên tố khi và chỉ khi {{math|(''p'' − 1)! ≡ −1 (mod ''p'')}}.
* [[Định lý thặng dư Trung Hoa]]: Với mọi {{math|''a''}}, {{math|''b''}} và {{math|''m''}}, {{math|''n''}} nguyên tố cùng nhau, tồn tại đúng một {{math|''x'' (mod ''mn'')}} sao cho {{math|''x'' ≡ ''a'' (mod ''m'')}} và {{math|''x'' ≡ ''b'' (mod ''n'')}}. Cụ thể hơn, {{math|''x'' ≡ ''b m''<sub>''n''</sub><sup>–1</sup> ''m'' + ''a n''<sub>''m''</sub><sup>–1</sup> ''n'' (mod ''mn'')}}, trong đó {{math|''m''<sub>''n''</sub><sup>−1</sup>}} là nghịch đảo của {{math|''m''}} modulo {{math|''n''}} và {{math|''n''<sub>''m''</sub><sup>−1</sup>}} là nghịch đảo của {{math|''n''}} modulo {{math|''m''}}.
* [[Định lý Lagrange (lý thuyết số)|Định lý Lagrange]]: Đồng nhất thức {{math|''f'' (''x'') ≡ 0 (mod ''p'')}}, trong đó {{math|''p''}} nguyên tố và {{math|1=''f'' (''x'') = ''a''<sub>''n''</sub> ''x''<sup>''n''</sup> + ... + ''a''<sub>0</sub>}} là một [[đa thức]] có hệ số nguyên sao cho {{math|''a''<sub>0</sub> &ne; 0 (mod ''p'')}}, có tối đa {{math|''n''}} nghiệm.
* [[Căn nguyên thủy modulo n|Căn nguyên thủy modulo {{mvar|n}}]]: Một số {{math|''g''}} là căn nguyên thủy {{math|''n''}} nếu, với mọi số nguyên {{math|''a''}} nguyên tố cùng nhau với {{math|''n''}}, tồn tại một số nguyên {{math|''k''}} sao cho {{math|''g''<sup>''k''</sup> ≡ ''a'' (mod ''n'')}}. Căn nguyên thủy modulo {{math|''n''}} tồn tại khi và chỉ khi {{math|''n''}} bằng {{math|2, 4, ''p''<sup>''k''</sup>}} hoặc {{math| 2''p''<sup>''k''</sup>}}, với {{math|''p''}} là số nguyên tố lẻ và {{math|''k''}} là một số nguyên dương. Nếu một căn nguyên thủy modulo {{math|''n''}} tồn tại thì có đúng {{math|''φ''(''φ''(''n''))}} căn nguyên thủy như thế, với {{math|''φ''}} là [[hàm phi Euler]].
* [[Thặng dư bình phương]]: Một số nguyên {{math|''a''}} là thặng dư bình phương modulo {{math|''n''}} nếu tồn tại một số nguyên {{math|''x''}} sao cho {{math|''x''<sup>2</sup> ≡ ''a'' (mod ''n'')}}. [[Tiêu chuẩn Euler]] nói rằng, nếu {{math|''p''}} là một số nguyên tố lẻ, {{mvar|a}} không là bội của {{mvar|p}}, thì {{math|''a''}} là thặng dư bình phương modulo {{math|''p''}} khi và chỉ khi {{math|''a'' <sup>(''p''–1)/2</sup> ≡ 1 (mod ''p'').}}

==Xem thêm==
{{Div col|colwidth=25em}}
* [[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
** [[Hàm Carmichael|Đị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)]]
{{Div col end}}

==Chú thích==
{{tham khảo}}

==Tham khảo==
* John L. Berggren. [http://www.britannica.com/EBchecked/topic/920687/modular-arithmetic "modular arithmetic"]. [[Encyclopædia Britannica]].
* Maarten Bullynck "[http://www.kuttaka.org/Gauss_Modular.pdf Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany] {{Webarchive|url=https://web.archive.org/web/20131102014013/http://www.kuttaka.org/Gauss_Modular.pdf |date = ngày 2 tháng 11 năm 2013}}"
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{isbn|0-262-03293-7}}. Section 31.3: Modular arithmetic, pp.&nbsp;862–868.
* [http://genealogy.math.ndsu.nodak.edu/id.php?id=3545 Anthony Gioia], ''Number Theory, an Introduction'' Reprint (2001) Dover. {{isbn|0-486-41449-3}}.
* {{chú thích sách |last=Long |first=Calvin T. |year=1972 |title=Elementary Introduction to Number Theory |url=https://archive.org/details/elementaryintrod0000long_m1z0_2ndedi |edition=2nd |publisher=[[D. C. Heath and Company]] |location=Lexington |lccn=77171950}}
* {{chú thích sách |last1=Pettofrezzo |first1=Anthony J. |last2=Byrkit |first2=Donald R. |year=1970 |title=Elements of Number Theory |url=https://archive.org/details/elementsofnumber0000pett |publisher=[[Prentice Hall]] |location=Englewood Cliffs |lccn=71081766}}
* {{chú thích sách |last=Sengadir |first=T. |title=Discrete Mathematics and Combinatorics |year=2009 |publisher=Pearson Education India |location=Chennai, India |isbn=978-81-317-1405-8 |oclc=778356123}}

==Liên kết ngoài==
* {{springer|title=Congruence|id=p/c024850}}
* In this [http://britton.disted.camosun.bc.ca/modart/jbmodart.htm modular art] {{Webarchive|url=https://web.archive.org/web/20060101075602/http://britton.disted.camosun.bc.ca/modart/jbmodart.htm |date = ngày 1 tháng 1 năm 2006}} article, one can learn more about applications of modular arithmetic in art.
* {{MathWorld | urlname=ModularArithmetic | title= Modular Arithmetic}}
* An [http://mersennewiki.org/index.php/modular_arithmetic article] {{Webarchive|url=https://web.archive.org/web/20160220061222/http://mersennewiki.org/index.php/Modular_arithmetic |date = ngày 20 tháng 2 năm 2016}} on modular arithmetic on the GIMPS wiki
* [http://www.cut-the-knot.org/blue/Modulo.shtml Modular Arithmetic and patterns in addition and multiplication tables]
* [http://wheelof.com/whitney Whitney Music Box]—an audio/video demonstration of integer modular math

{{Lý thuyết số}}

[[Thể loại:Số học Modulo]]
[[Thể loại:Trường Galois]]
[[Thể loại:Lý thuyết nhóm]]