Chiếc đồng hồ đeo tay 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.
Cho số nguyên n > 1, hai số được gọi là đồng dư môđun n nếu n là ước của hiệu giữa hai số đó (nghĩa là tồn tại số nguyên k sao cho a – b = nk.
Đồng dư môđun là quan hệ đồng dư, nghĩa là nó là quan hệ tương đương tương thích với phép nhân, phép cộng và phép trừ. Ký hiệu đồng dư môđun n là:
a
≡
b
(
mod
n
)
{displaystyle aequiv b{pmod {n}}}
Dấu ngoặc được dùng để biểu thị phép toán diễn ra ở hai bên, để tránh nhầm lẫn với ký hiệu b mod n không có dấu ngoặc.
Khi xét môđun 12, ta có:
38
≡
14
(
mod
12
)
{displaystyle 38equiv 14{pmod {12}}}
bởi vì
38
−
14
=
24
{displaystyle 38-14=24}
Vì quan hệ đồng dư là quan hệ tương tự, nên ta có những đặc thù từ quan hệ tương tự :
- Phản xạ:
a ≡ a (mod n)
- Đối xứng:
a ≡ b (mod n)
khi và chỉ khi
b ≡ a (mod n)
với mọi a, b
- Bắc cầu: nếu
a ≡ b (mod n)
và
b ≡ c (mod n)
thì
a ≡ c (mod n)
Nếu a1 ≡ b1 (mod n) và a2 ≡ b2 (mod n), hoặc a ≡ b (mod n), thì:
-
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
-
a1 + a2 ≡ b1 + b2 (mod n)
(bảo toàn phép cộng)
-
a1 – a2 ≡ b1 – b2 (mod n)
(bảo toàn phép trừ)
-
a1 a2 ≡ b1 b2 (mod n)
(bảo toàn phép nhân)
-
ak ≡ bk (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)
Nếu a ≡ b (mod n), ta thường dễ nhầm cho rằng ka ≡ kb (mod n). Tuy nhiên điều sau là đúng:
- Nếu
c ≡ d (mod φ(n)),
với
φ
is Hàm phi euler, thì
ac ≡ ad (mod n)
— nếu như
a
nguyên tố cùng nhau với
n
.
Đối với việc vô hiệu thành phần ở hai bên, ta có những luật sau :
- Nếu
a + k ≡ b + k (mod n)
, với
k
là số nguyên bất kì, thì
a ≡ b (mod n)
- Nếu
k a ≡ k b (mod n)
và
k
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)
