Teorema Eulero-Fermat e crittografia

[diedro]

ciao a tutti,
Ho il seguente esercizio:

Sia $n=pq$, ove $p,q$ sono due primi distinti. Siano $r,s,t$ tali che $rs+\phi(n)t=1$.
Si mostri che $a^{rs}\equiv a(mod n)$.

Sicuramente ci sono due casi, il caso in cui $gcd(a,n)=1$ e tutto segue poi da Eulero-Fermat. Caso un po' più complicato è quando $gcd(a,n) \ne 1$.

Io sono già bloccato con il primo.
Qualcuno potrebbe darmi un aiuto?
Grazie

[Stickelberger]

Se scrivi $u=rs$, allora va dimostrato che la congruenza
$u\equiv 1$ mod $\phi(n)$ implica che $a^u\equiv a$ mod $n$ per ogni $a\in ZZ$.
Questo e' vero quando $n$ e' primo e quindi anche se $n$ e' un
prodotto di primi distinti.

Non e' vero per ogni $n$. Basta prendere $n=4$, $u=3$ e $a=2$.

[diedro]

ciao,
quindi, supponiamo il caso in cui $(a,n)=1$, come faccio a dimostrarlo?
scusami, ma sono nuovo e purtroppo non riesco ad andare a lezione.