Đồng dư

Bách khoa toàn thư mở Wikipedia

Đị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 a,b có cùng số dư khi chia cho n. Điều này tương đương với hiệu a trừ b chia hết cho n.

Ký hiệu:

Ví dụ:

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

11: 3 = 3 (dư 2)

5: 3 = 1 (dư 2)


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ó:

Thì ta có:

  • , với k nguyên dương.

Luật giản ước[sửa | sửa mã nguồ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ố sao cho: , số x này được gọi là nghịch đảo của a theo mô-đun n.

Đối với số chính phương[sửa | sửa mã nguồn]

Tính chất[sửa | sửa mã nguồn]

  • Một số chính phương chia 3 luôn có số dư là 0 hoặc 1 và không thể có số dư là 2. Kí hiệu x2 ☰ 0; 1 (mod 3) với mọi số nguyên x.
  • Một số chính phương chia 4 luôn có số dư là 0 hoặc 1 và không thể có số dư là 2 và 3. Kí hiệu x2 ☰ 0; 1 (mod 4) với mọi số nguyên x.
  • Một số chính phương chẵn chia 4 luôn có số dư là 0. Kí hiệu x2 ☰ 0 (mod 4) với mọi số nguyên chẵn x.
  • Một số chính phương lẻ chia 4 luôn có số dư là 1. Kí hiệu x2 ☰ 1 (mod 4) với mọi số nguyên lẻ x.
  • Một số chính phương chia 8 luôn có số dư là 0, 1 hoặc 4 và không thể có số dư là 2,3,5,6 và 7. Kí hiệu x2 ☰ 0; 1; 4 (mod 8) với mọi số nguyên x.
  • Một số chính phương lẻ chia 4,8 luôn có số dư là 1. Kí hiệu x2 ☰ 1 (mod 4,8) với số nguyên lẻ x.
  • Một số chính phương chia 10 luôn có số dư là 0, 1, 4, 5, 6 hoặc 9 và không thể có số dư là 2,3,7 và 8. Kí hiệu x2 ☰ 0; 1; 4; 5; 6; 9 (mod 10) với mọi số nguyên x.

Hệ thặng dư đầy đủ[sửa | sửa mã nguồn]

Tập hợp được gọi là một hệ thặng dư đầy đủ mô-đun n nếu với mọi số nguyên i, , tồn tại duy nhất chỉ số j sao cho .

Tính chất[sửa | sửa mã nguồn]

  • Nếu là một hệ thặng dư đầy đủ mô-đun n thì là một hệ thặng dư đầy đủ mô-đun n với mọi số nguyên a.
  • Nếu là một hệ thặng dư đầy đủ mô-đun n thì 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.
  • Đã thay đổi

Xem thêm[sửa | sửa mã nguồn]

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