Question

đồng dư là gì (cho ví dụ)

nguyên lý đi rích lê là gì (cho ví dụ)

Answer 1

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 số nguyên.

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

{\displaystyle a\equiv b{\pmod {n}}\,}

Ví dụ:

{\displaystyle 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ó:

{\displaystyle a_{1}\equiv a_{2}{\pmod {n}}\,}

{\displaystyle b_{1}\equiv b_{2}{\pmod {n}}\,}

Thì ta có:

{\displaystyle (a_{1}+b_{1})\equiv (a_{2}+b_{2}){\pmod {n}}\,}{\displaystyle (a_{1}-b_{1})\equiv (a_{2}-b_{2}){\pmod {n}}\,}{\displaystyle (a_{1}b_{1})\equiv (a_{2}b_{2}){\pmod {n}}.\,}{\displaystyle 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 {\displaystyle (a_{1}*b)\equiv (a_{2}*b){\pmod {n}}\,} và (b,n)=1 (b,n nguyên tố cùng nhau) thì {\displaystyle 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ố {\displaystyle x\in \{0,1,2,\cdots ,n-1\}} sao cho: {\displaystyle 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 {\displaystyle \{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, {\displaystyle 0\leq i\leq n-1}, tồn tại duy nhất chỉ số j sao cho {\displaystyle a_{j}\equiv i{\pmod {n}}\,}.

Tính chất[sửa 

Nếu {\displaystyle \{a_{1},a_{2},\cdots ,a_{n}\}} là một hệ thặng dư đầy đủ mô-đun n thì {\displaystyle \{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 {\displaystyle \{a_{1},a_{2},\cdots ,a_{n}\}} là một hệ thặng dư đầy đủ mô-đun n thì {\displaystyle \{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.

Answer 2

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 số nguyên.

VD : 

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

Nếu đem m thỏ vào n lồng với m>n thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ. Tương tự, nếu đem m đồ vật vào n ô ngăn kéo, với m>n, thì ít nhất cũng phải có 1 ô ngăn kéo chứa không ít hơn 2 đồ vật
Phần chứng minh bài toán, các bạn chắc gần như ai cũng biết, mình chỉ xin nêu một vài bài toán vận dụng cơ bản.