Classe dei resti e congruenze lineari

[gundamrx91-votailprof]

Mentre studiavo la dimostrazione del seguente teorema "Una congruenza lineare [tex]ax\equiv b_(_m_o_d_n_)[/tex] ha soluzione, qualunque sia [tex]b[/tex] se e solo se [tex](a,n)=1[/tex] ", giocando un pò con i numeri ho verificato che:

1) se [tex](a,n)=1[/tex] allora le classi dei resti [tex]a[0]_(_n_), a[1]_(_n_), ... ,a[n-1]_(_n_)[/tex] sono tutte diverse
2) se [tex](a,n)\neq1 \wedge a|n[/tex] allora [tex][a]_(_n_)=[0]_(_n_) \forall [a]_(_n_) \in Z_n[/tex]
3) se [tex](a,n)\neq 1 \wedge a\nmid n[/tex] allora le classi dei resti ciclano, ovvero si azzerano ogni [tex]n/d[/tex] dove [tex]d=(a,n)[/tex]

Ad esempio nella congruenza algebrica [tex]99x \equiv 2_(_m_o_d_1_5_)[/tex] in cui [tex](99,15)=3[/tex] si ha che dopo [tex]15/3=5[/tex] iterazioni (non so come definirle....), la classe è di nuovo zero:

[tex]99[0]_(_1_5_)=[0]_(_1_5_)[/tex]
[tex]99[1]_(_1_5_)=[99]_(_1_5_)=[9]_(_1_5_)[/tex]
[tex]99[2]_(_1_5_)=[198]_(_1_5_)=[3]_(_1_5_)[/tex]
[tex]99[3]_(_1_5_)=[297]_(_1_5_)=[12]_(_1_5_)[/tex]
[tex]99[4]_(_1_5_)=[396]_(_1_5_)=[6]_(_1_5_)[/tex]

le successive si ripetono e così via.
Ne ho provate delle altre e il comportamento è sempre lo stesso. Ho provato a cercare un pò nella mia dispensa ma non ho trovato nulla in proposito, e
volevo capire se è corretto quanto ho verificato e, soprattutto, a quale teorema/proposizione corrisponde.

Grazie e scusate l'eventuale banalità e/o fesserie scritte

[Gi81]

Tutto corretto. Questo teorema spiega tutto (con $(a,n)$ si intende il massimo comun divisore tra $a$ e $n$):

Una equazione congruenziale $ax-=b_(mod n)$ ha soluzioni se e solo se $(a,n)|b$
In questo caso il numero di soluzioni è esattamente $(a,n)$

Il teorema da te citato ne è una ovvia conseguenza

[gundamrx91-votailprof]

Ah, ok, quel teorema nella dispensa è indicato subito dopo

Grazie

[gundamrx91-votailprof]

Sempre per stare in tema, volevo un chiarimento su questo teorema/lemma:


Lemma 8.7: Precisato che per sistema completo di residui modulo $a$ si
intende un qualunque insieme di $\phi(a)$ (funzione di Eulero) interi mai due dei quali congrui modulo
$a$, siano $a$, $b$ e $c$ interi e sia $(a, b) = 1$; se $x$ percorre $M$, un sistema completo
di residui modulo $a$, allora anche $bx + c$ percorre un sistema completo di
residui modulo $a$, diciamolo $M$'.

Dimostrazione: Basta provare che, nelle attuali ipotesi, mai due distinti
elementi $bx + c$ e $by + c$ dell'insieme $M$' sono congrui modulo $a$. In caso
contrario infatti si avrebbe

$(bx + c) - (by + c) = b(x- y) = ma$

ma per ipotesi $a$ e’ primo con $b$ e quindi ogni divisore primo di $a$, non potendo
dividere $b$, dovrebbe dividere $x-y$, e quindi $a$ stesso dovrebbe dividere $x-y$,
in contraddizione con l'assunto che $x$ e $y$ non siano congrui modulo $a$.


Il quesito l'avevo postato tempo fa, ma non avevo ricevuto nessuna risposta, per cui ci
riprovo: avete idea di cosa intende per "percorrere" un sistema completo di residui modulo n??

[gundamrx91-votailprof]

Nessun suggerimento/idea?