Số học mô đun

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 , gọi là **mô đun**, hai số nguyên  và  được gọi là **đồng dư** modulo , nếu hiệu của chúng chia hết cho  (đó là, nếu tồn tại số nguyên  sao cho ).

Đồng dư mô đun  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  được ký hiệu là:

:a \equiv b \pmod n.

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

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

:38 \equiv 14 \pmod {12}

vì , 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{align}
2 &\equiv -3 \pmod 5\\
-3 &\equiv \ \ \ 7 \pmod 5\\
-3 &\equiv -8 \pmod 5
\end{align}

## 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ạ: 
* Đối xứng:  khi và chỉ khi  với mọi , 
* Bắc cầu: nếu  và  thì 

### Cộng, trừ, nhân
Nếu  và  hoặc  thì:
*  với mọi số nguyên  
*  với mọi số nguyên  khác 0
*  với mọi số nguyên 
*  (bảo toàn phép cộng)
*  (bảo toàn phép trừ)
*  (bảo toàn phép nhân)
*  với mọi số nguyên không âm  (bảo toàn phép mũ)
* , với mọi đa thức  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 , với  là số nguyên bất kì, thì 
* Nếu  và  nguyên tố cùng nhau với , thì 
* Nếu  , thì 

### Số mũ
Từ  không thể suy ra được . Ví dụ, , nhưng . Tuy nhiên điều sau là đúng:
* Nếu  với  là hàm phi Euler, thì —nếu như  nguyên tố cùng nhau với .

### 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à  sao cho  khi và chỉ khi  nguyên tố cùng nhau với . Số nguyên  này gọi là *nghịch đảo phép nhân mô đun* của  modulo .
* Nếu  và  tồn tại, thì 
* Nếu  và  nguyên tố cùng nhau với , lời giải của đồng dư thức này là 

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

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

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

## 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)

## Chú thích

## 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 "
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *[[Introduction to Algorithms]]*, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 31.3: Modular arithmetic, pp.&nbsp;862–868.
* Anthony Gioia, *Number Theory, an Introduction* Reprint (2001) Dover. .
* 
* 
* 

## Liên kết ngoài
* 
* In this modular art  article, one can learn more about applications of modular arithmetic in art.
* 
* An article  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