1. Máy tính bỏ túi Việt Nam
  2. Các chuyên về máy tính
Cảm ơn 1 Theo dõi 2 Sao chép

Đị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:

Deion: a \equiv b \pmod n\,

Ví dụ:

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

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

Deion: a_1 \equiv a_2 \pmod n\,

Deion: b_1 \equiv b_2 \pmod n\,

Thì ta có:

·         Deion: (a_1 + b_1) \equiv (a_2 + b_2) \pmod n\,

·         Deion: (a_1 - b_1) \equiv (a_2 - b_2) \pmod n\,

·         Deion: (a_1 b_1) \equiv (a_2 b_2) \pmod n.\,

·         Deion: a_1^k \equiv a_2^k \pmod n\,, với k nguyên dương.

Luật giản ước[

Nếu Deion: (a_1*b) \equiv (a_2*b) \pmod n\, và (b,n)=1 (b,n nguyên tố cùng nhau) thì Deion: 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ố Deion: x \in \{0,1,2, \cdots, n-1\} sao cho: Deion: 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 Deion: \{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 iDeion: 0\le i\le n-1, tồn tại duy nhất chỉ số j sao cho Deion: a_j\equiv i \pmod n\,.

Tính chấtNếu Deion: \{a_1,a_2,\cdots,a_n\} là một hệ thặng dư đầy đủ mô-đun n thì Deion: \{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.

Đị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:

Deion: a \equiv b \pmod n\,

Ví dụ:

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

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

Deion: a_1 \equiv a_2 \pmod n\,

Deion: b_1 \equiv b_2 \pmod n\,

Thì ta có:

·         Deion: (a_1 + b_1) \equiv (a_2 + b_2) \pmod n\,

·         Deion: (a_1 - b_1) \equiv (a_2 - b_2) \pmod n\,

·         Deion: (a_1 b_1) \equiv (a_2 b_2) \pmod n.\,

·         Deion: a_1^k \equiv a_2^k \pmod n\,, với k nguyên dương.

Luật giản ước[

Nếu Deion: (a_1*b) \equiv (a_2*b) \pmod n\, và (b,n)=1 (b,n nguyên tố cùng nhau) thì Deion: 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ố Deion: x \in \{0,1,2, \cdots, n-1\} sao cho: Deion: 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 Deion: \{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 iDeion: 0\le i\le n-1, tồn tại duy nhất chỉ số j sao cho Deion: a_j\equiv i \pmod n\,.

Tính chấtNếu Deion: \{a_1,a_2,\cdots,a_n\} là một hệ thặng dư đầy đủ mô-đun n thì Deion: \{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.