Piccolo teorema di Fermat e crittografia RSA

[Lorenzo Pantieri]

Buongiorno, e perdonatemi se la domanda è sciocca, ma sono decenni che non studio l'Algebra con la A maiuscola.

Il piccolo teorema di Fermat dice che se $p$ è un numero primo, allora per ogni intero $a$:
\[
a^p \equiv a \mod{p}
\]
Su Wiki trovo scritto che una "piccola generalizzazione del teorema, che deriva immediatamente da questo", è la seguente: se $p$ è primo e $m$ e $n$ sono interi positivi con
\[
m \equiv n \mod{(p-1)}
\]
allora
\[
a^m \equiv a^n \mod p
\]
per ogni intero $a$. In questa forma, il teorema giustifica il sistema di cifratura a chiave pubblica RSA.

Qualcuno mi dimostra la "piccola generalizzazione", a partire dall'enunciato originale del teorema?

Grazie.

[3m0o]

Segue direttamente dal Teorema di Eulero, che dice quanto segue: se \(n\) è un intero positivo e \(\operatorname{gcd}(a,n)=1\) allora \( a^{\varphi(n)} \equiv 1 \mod n \) dove \( \varphi (n)\) è la funzione toziente!
Nota che se \(p\) è primo allora \( \varphi(p)=p-1\), pertanto da \( n \equiv m \operatorname{mod} \varphi(p) \) deduciamo che
\[ a^n =a^{m + \varphi(p)k} = a^m a^{\varphi(p) k} \equiv a^m 1^k = a^m \operatorname{mod} p \]

Edit:

Qualcuno mi dimostra la "piccola generalizzazione", a partire dall'enunciato originale del teorema?

Se non vuoi usare il Teorema di Eulero, che è una generalizzazione del piccolo Teorema di Fermat, allora nota semplicemente che \( a^p \equiv a \mod p \) è equivalente ad \( a^{p-1} \equiv 1 \mod p \), e invece di scrivere \( \varphi(p)\) scrivi \(p-1\):
\[ a^n =a^{m + (p-1)k} = a^m a^{(p-1) k} \equiv a^m 1^k = a^m \operatorname{mod} p \]

[Lorenzo Pantieri]

Per me, c'è ancora qualcosa che non va in questa dimostrazione.

Infatti i risultati che usi sfruttano il fatto che $a$ sia coprimo con $p$. Più precisamente, quando scrivi che $a^{p-1}\equiv1 \mod p$, stai assumendo che $a$ e $p$ siano coprimi.

Invece Wiki scrive che il risalato vale per ogni $a$. Copio incollo da Wiki:

Una piccola generalizzazione del teorema, che deriva immediatamente da questo, è la seguente: se $p$ è primo e $m$ e $n$ sono interi positivi con $m \equiv n \mod(p-1)$, allora $a^m \equiv a^n \mod p$ per ogni intero $a$.

https://it.wikipedia.org/wiki/Piccolo_teorema_di_Fermat

Mi viene il sospetto che la tesi vada riformulata così:

Una piccola generalizzazione del [piccolo] teorema [di Fermat], che deriva immediatamente da questo, è la seguente: se $p$ è primo e $m$ e $n$ sono interi positivi con $m \equiv n \mod(p-1)$, allora $a^m \equiv a^n \mod p$ per ogni intero $a<p$.

Poiché $p$ è primo, ogni $a<p$ è coprimo con $p$, e quindi la dimostrazione fila.

Sbaglio io o sbaglia Wiki?

[3m0o]

Sì nella dimostrazione assumo che \(a\) è coprimo con \(p\), ma non è un problema perché se \( a \) e \(p\) non sono coprimi, allora siccome \(p\) è primo, abbiamo che \( p \mid a \) da cui ottieni banalmente \(a^m \equiv 0 \equiv a^n \mod p \) e non c'è nulla da dimostrare.

Edit: Anche se piuttosto che generalizzazione lo chiamerei corollario

[Lorenzo Pantieri]

Sì nella dimostrazione assumo che \(a\) è coprimo con \(p\), ma non è un problema perché se \( a \) e \(p\) non sono coprimi, allora siccome \(p\) è primo, abbiamo che \( p \mid a \) da cui ottieni banalmente \(a^m \equiv 0 \equiv a^n \mod p \) e non c'è nulla da dimostrare.

Edit: Anche se piuttosto che generalizzazione lo chiamerei corollario

Ora la dimostrazione è perfetta. Grazie mille, di cuore.