Esercizio base

[Pairo]

$ \displaystyle163n\equiv 1\mod2000 $. Allora quando vale n? Se qualcuno riuscisse ad aiutarmi mi farebbe un grande favore!

[Haile]

Mmm

tutte gli n di forma $ $ n = 2000 \cdot t - 773$ $ sono soluzione.

Si ricava dal fatto che $ $ 163n - 1 = 2000k $ $, da cui $ $ 163n - 2000k = 1 $ $ che è una diofantea lineare risolvibile, dato che $ $(163,2000) = 1$ $.

Soluzione abbastanza barbara, devo ammettere

[SkZ]

puoi ragionare in modo "contoso"
se $ ~163n\equiv 1 \pmod{2000} $, allora $ ~163n=2000k+1 $
ergo $ ~n=10a_1+7 $, quindi $ ~1630a_1+1141=2000k+1 $ che e' $ ~163a_1+114=200k $, ergo $ ~a_1=2+10a_2 $
...

[pak-man]

La congruenza scritta equivale a $ 163n=2000k+1 $, cioè $ 163n+2000m=1 $ per qualche $ m\in\mathbb{Z} $.
Poiché $ (163,2000)=1 $ per il Teorema di Bezout la diofantea ha soluzioni.

2000=163*12+44
163=44*3+31
44=31*1+13
31=13*2+5
13=5*2+3
5=3*1+2
3=2*1+1

1=3-2=3-(5-3)=2*3-5
=2(13-5*2)-5=2*13-5*5=
=2*13-5(31-13*2)=12*13-5*31=
=12(44-31)-5*31=12*44-17*31=
=12*44-17(163-44*3)=63*44-17*163=
=63(2000-163*12)-17*163=2000*63-773*163

Poiché $ 163n+2000m=1=2000\cdot63-163\cdot773 $ allora una soluzione della diofantea è $ (n,m)=(773,63) $.
Risolvendo modulo 2000 si ha che $ n\equiv773\pmod{2000} $

edit: anticipato, come al solito...questa è la versione completa della soluzione contosa proposta da Haile

[Haile]

anticipato, come al solito...questa è la versione completa della soluzione contosa proposta da Haile

Esatto... hai fatto bene a metterla giù completa

Comunque, se non erro, è anche il metodo standard per la risoluzione di equazioni con mod, la trasformazione in diofantea

[Pairo]

Grazie mille ragazzi! Gentilissimi!