Determinare tutti i numeri naturali n che divisi per 10, 3, 7, 11, danno come resti, rispettivamente, 4, 2, 3, 1.
La richiesta equivale al sistema di congruenze
x = 4 mod 10
x = 2 mod 3
x = 3 mod 7
x = 1 mod 11
Dalla prima si ricava che x=10y+4, che sostituito nella seconda porta a
10y+4 = 2 mod 3 =>
y = 1 mod 3
e quindi y=3w+1 e pertanto x=30w+14. Sostituendo questa espressione di x nella terza equazione si ha
30w+14 = 3 mod 7 =>
2w = 3 mod 7
per cui 2w=7v+3. Dal momento che a destra abbiamo un numero pari, deve essere per forza v=2z+1 dispari, così che anche il membro destro sia pari: ma allora
2w=14z+10 => w=7z+5.
Sostituendo di nuovo a ritroso si trova
x=210z+164.
Sostituendo ora nell'ultima.congruenza abbiamo
210z+164 = 1 mod 11 =>
z = 2 mod 11
e quindi z=11k+2. Pertanto
x=2310k+584
x=4 mod 10
x=2 mod 3
x=3 mod 7
x=1 mod 11
10, 3, 7, 11 sono coprimi a due a due e posso applicare il teorema cinese del resto.
x=a₁ mod n₁
x=a₂ mod n₂
x=a₃ mod n₃
x=a₄ mod n₄
N=n₁n₂n₃n₄=2310
costruisco i nuovi moduli
N₁=3·7·11=231
N₂=10·7·11=770
N₃=10·3·11=330
N₄=10·3·7=210
risolvo
231x₁=1 mod 10
770x₂=1 mod 3
330x₃=1 mod 7
210x₄=1 mod 11
ovvero
x₁=1 mod 10
x₂=-1 mod 3 →xᵢ
x₃=1 mod 7
x₄=1 mod 11
calcolo
x=∑ᵢ₌₁⁴aᵢNᵢxᵢ mod N
x=n=4·231·1-2·770·1+3·330·1+1·210·1 mod 2310
n=584 mod 2310
n=2310k+584
con k ∈ ℕ
About Post Author
