Đồng dư

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

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 + b_1) \equiv (a_2 + b_2) \pmod n\,
  • (a_1 - b_1) \equiv (a_2 - 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[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

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 đủ[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

  • 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[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]