Đị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 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:
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)
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ó:
Thì ta có:
·
·
·
· , với k nguyên dương.
Luật giản ước[
Nếu và (b,n)=1 (b,n nguyên tố cùng nhau) thì
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ố sao cho: , 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 đượ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ấtNế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.
Đị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 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:
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)
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ó:
Thì ta có:
·
·
·
· , với k nguyên dương.
Luật giản ước[
Nếu và (b,n)=1 (b,n nguyên tố cùng nhau) thì
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ố sao cho: , 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 đượ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ấtNế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.