Đồng dư

Trong toán học, đặc biệt là trong đại số, quan hệ đồng dư (gọi đơn giản là đồng dư) là một quan hệ tương đương trên Z

Định nghĩa

Cho số nguyên dương n, hai số nguyên a,b được gọi là đồng dư theo mô-đun n nếu chúng cho cùng số dư khi chia cho n (hay là a-b chia hết cho n).

Kí hiệu là:

$a \equiv b \pmod n\,$

Ví dụ:

$11 \equiv 5 \pmod 3\,$

Vì 11 và 5 khi chia cho 3 đều cho số dư là 2.

Tính chất

Ngoài các tính chất của một quan hệ tương đương (phản xạ, đối xứng, bắc cầu), phép đồng dư còn có thêm các tính chất sau: Có thể cộng, trừ, nhân và nâng lên lũy thừa các đồng dư thức có cùng một mô-đun, cụ thể. Nếu ta có:

$a_1 \equiv a_2 \pmod n\,$

$b_1 \equiv b_2 \pmod n\,$

Thì ta có:

• $(a_1 + a_2) \equiv (b_1 + b_2) \pmod n\,$
• $(a_1 - a_2) \equiv (b_1 - b_2) \pmod n\,$
• $(a_1 b_1) \equiv (a_2 b_2) \pmod n.\,$
• $a_1^k \equiv a_2^k \pmod n\,$, với k nguyên dương.

Luật giản ước

Nếu $(a_1*b) \equiv (a_2*b) \pmod n\,$ và (b,n)=1 (b,n nguyên tố cùng nhau) thì $a_1 \equiv a_2 \pmod n\,$

Nghịch đảo mô-đun

Nếu số nguyên dương n và số nguyên a nguyên tố cùng nhau thì tồn tại duy nhất một số $x \in \{0,1,2, \cdots, n-1\}$ sao cho: $ax \equiv 1 \pmod n\,$, số x này được gọi là nghịch đảo của a theo mô-đun n.

Hệ thặng dư đầy đủ

Tập hợp $\{a_1,a_2,\cdots,a_n\}$ được gọi là một hệ thặng dư đầy đủ mô-đun n nếu với mọi số nguyên i, $0\le i\le n-1$, tồn tại duy nhất chỉ số j sao cho $a_j\equiv i \pmod n\,$.

Tính chất

• Nếu $\{a_1,a_2,\cdots,a_n\}$ là một hệ thặng dư đầy đủ mô-đun n thì $\{a_1+a,a_2+a,\cdots,a_n+a\}$ là một hệ thặng dư đầy đủ mô-đun n với mọi số nguyên a.
• Nếu $\{a_1,a_2,\cdots,a_n\}$ là một hệ thặng dư đầy đủ mô-đun n thì $\{aa_1,aa_2,\cdots,aa_n\}$ là một hệ thặng dư đầy đủ mô-đun n với mọi số nguyên a nguyên tố cùng nhau với n.

Xem thêm

• Định lý nhỏ Fermat
• Định lý Euler
• Định lý Wilson