Đồ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ố và lý thuyết số, quan hệ đồng dư (gọi đơn giản là đồng dư) là một quan hệ tương đương trên tập hợp 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 có cùng số dư khi chia cho n. Điều này tương đương với hiệu a-b chia hết cho n.

Kí hiệu:

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:

11: 3 = 3 (dư 2)

5: 3 = 1 (dư 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]