✨Số học mô đun

thumb|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 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\; \backslash equiv\; b\; \backslash 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\; \backslash equiv\; 14\; \backslash 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ư:

:

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