Dim che la congruenza mod n ha soluzioni sse MCD(a,n)/b

[pier_IP]

La congruenze lineare $ax \equiv b (mod n)$ ha soluzioni sse $MCD(a,n)$ divide $b$. Come si dimostra sto fatto?
Ho cercato in rete ma non ho trovato nulla e sul mio libro (Facchini) non ci sono le congruenze lineari.

Ho provato a dare una dimostrazione mia ma dubito che sia buona.
Io ho pensato che visto che le congruenze si risolvono con la relativa equazione diofantea, basta dimostrare che l'eq diofantea ha soluzione. Quindi l'eq diofantea è $ax + ny = b$ e questa ha soluzione solo se b è divisibile per MCD(a,n) e di questo fatto la dimostrazione è conosciuta.

Mi sembra non buona, anche perchè forse il fatto che le congruenze si risolvono con le eq diofantee deriva proprio da questa dimostrazione.

[Kashaman]

Poniamo $M.C.D(a,n)=d$
dobbiamo provare
a) $ax-=b(modn)$ ha soluzione$=> d|b$
b) $d|b => ax-=b(modn)$


Proviamo b) Poiché $(a,n)=d$ per il lemma di Bezout esistono $s,t \in ZZ : as+tn=d$ (1)
Per ipotesi $d|b$ , pertanto $b=dq$ per un certo $q$.
Moltiplicando per $q$ la (x) si ha che
$a(sq)+n(tq)=dq=b$ da cui $a(sq)-b=n(-tq)$ ciò vuol dire che $n|asq-b$ e a norma di definizione vuol dire che $asq-=b(modn)$, pertanto $sq$ è soluzione particolare di $ax-=b(modn)$. Risulta provata 2).
Proviamo b) per ipotesi abbiamo che $ax-=b(modn) $ (1) ha soluzione.
Denotiamo con $x_0$ una soluzione particolare.
Dalla (1) si ha che $n|ax_0-b <=> ax-b=nk$ per un certo $k in ZZ$.
E cioé
$ax_0+n(-k)=b$.(2)
Poiché $(a,n)=d$
risulta per definizione di massimo comune divisore che
$d|a , d|n$
Ma si ha anche che
$d|ax_0 , d|n(-k)$ , per il fatto che se un numero ne divide un'altro ne divide anche un suo multiplo.
Per le proprietà di $|$ si ha anche che
$d|ax_0+n(-k)=b$ per la (2)
Pertanto $d|b$ , quello che volevamo.
Anche la uno risulta essere provata.

[Gi81]

edit: anticipato
metto in spoiler il mio intervento, nel caso serva un altro punto di vista

\(\displaystyle ax \equiv b \quad (\bmod n) \qquad \Leftrightarrow \qquad \exists y \in \mathbb{N} : \quad ax+ny=b\)


Sia \(\displaystyle d:= M.C.D. \bigl(a,n\bigr) \). Quindi \(\displaystyle \exists \bar{a}\in \mathbb{N} : \quad a= \bar{a}\cdot d \qquad \) e \(\displaystyle \exists \bar{n} \in \mathbb{N}: \quad n = \bar{n}\cdot d \)

Se \(\displaystyle d \nmid b \) allora \(\displaystyle (ax+ny) \nmid b \) (perchè?), quindi non ci sono $x$ tali che \(\displaystyle ax \equiv b \quad (\bmod n)\).

Se \(\displaystyle d \mid b \) allora \(\displaystyle b= \bar{b}\cdot d \).
Saprai senz'altro che esistono \(\displaystyle x',y' \in \mathbb{N} \) tali che \(\displaystyle ax'+ny' = d \) (tramite l'algoritmo per il calcolo del M.C.D.)
Quindi...

[pier_IP]

Grazie mille! E' molto chiaro!