Congruenze lineari

[ladepie]

il teorema dice:

La congruenza lineare ax=b (mod n) ammette soluzione qualunque sia b se e solo se a è primo con n.

la dim. delle dispense è questa:

[img]http://yfrog.com/0mnuovaimmaginebitmapbp[/img]

Mi potreste spiegare perchè "i-j=0" dal momento che sono entrambi minori di zero?

[Steven11]

Non sono entrambi minori di zero, infatti.
Semplicemente lui ti sta dicendo che [tex]$n$[/tex] deve dividere [tex]$i-j$[/tex], ma sia $i$ che $j$ sono minori di $n$, quindi la loro differenza, che puoi assumere positiva, sarà sicuramente minore di [tex]$n$[/tex].

Quindi [tex]$n$[/tex] divide una quantità non negativa minore di [tex]$n$[/tex], e questo è possibile se e solo se quella quantità è zero, cioè [tex]$i-j=0$[/tex] ovvero le due classi sono uguali.

Ti torna?
Ciao.

[ladepie]

si avevo pensato anche io ad una soluzione del genere pero' volevo una conferma...
forse sono un po' troppo perfezionista...

[ladepie]

adesso non mi torna il fatto che $a[n']$ e $a'[dn]$ siano la stessa classe... e cosa centrano con la classe 0 ? non riesco a legarle con il fatto che $(a,n)=d$ diverso da $1$

[ladepie]

supponendo per assurdo che $(a,n)=d$ diverso da 1 si ha quindi che $a=da'$ e $n=dn'$. Da cio' consegue che $an'=a'n$ e che $a[n']=a'[n]$ (mod n) essendo $[0]=[n]$ e $n'

Cita

Segnala