Il piccolo Teorema di Fermat... O quasi...

[dan95]

Trovare tutti i numeri interi positivi $n$ tali che

$a^{n+1} \equiv a \mod n$


Per ogni $a \in \mathbb{Z}//n\mathbb{Z}$

[hydro]

Testo nascosto, fai click qui per vederlo

Per ogni divisore $d$ di $\varphi(n)$ esiste $a$ coprimo con $n$ tale che $a^d\equiv 1\mod n$. Ma per questi $a$ si ha $a^n\equiv 1\mod n$ per ipotesi, e siccome $d\le n$ dev'essere \(d\mid n\). Segue che $\varphi(n)$ divide $n$. Se $n=\prod_{i=1}^m p_i^{e_i}$ è la fattorizzazione in primi, si ha quindi che $(p_1-1)\ldots (p_m-1)$ divide $p_1\ldots p_m$. Guardando la valutazione $2$-adica, dev'essere $m\le 2$. Se $m=1$ per forza $n=2$, se $m=2$ si vede facilmente che $n=6$. Viceversa, $n=2$, $n=6$ vanno bene.

[dan95]

@Hydro

Testo nascosto, fai click qui per vederlo

$n=42$ e $n=1806$ li scordiamo?


Quanto vale la valutazione $p$-adica di $n$ con $p|n$? (Vedi meglio)

Qual è la parità di $n$?


Quanto deve valere il più piccolo numero primo dispari che divide $n$? E il secondo? E il terzo? E il quarto?...

[hydro]

@Hydro

Testo nascosto, fai click qui per vederlo

$n=43$ e $n=1806$ li scordiamo?


Quanto vale la valutazione $p$-adica di $n$ con $p|n$? (Vedi meglio)

Qual è la parità di $n$?


Quanto deve valere il più piccolo numero primo dispari che divide $n$? E il secondo? E il terzo? E il quarto?...

Allora non ho capito il problema perché \(2^{44}\equiv 4 \mod 43\)…

[dan95]

Sorry 42

[hydro]

Aaaah certo ho scritto una stupidaggine, nella mia testa stavo pensando che il gruppo moltiplicativo fosse ciclico…

[hydro]

Ci riprovo.

Testo nascosto, fai click qui per vederlo

Sia \(n=\prod_{i=1}^r p_i^{e_i}\) la fattorizzazione in primi. Scegliamo $a=n/p_i$ per qualche $i\in \{1,\ldots,r\}$. Dalla relazione \(n\mid a\cdot (a^n-1)\) si evince immediatamente che $e_i=1$. Quindi $n$ è un prodotto di primi distinti. Adesso per ogni $i\in \{1,\ldots,r\}$ scegliamo $a_i$ un generatore modulo $p_i$. Allora $a_i^n\equiv 1 \mod p_i$, e siccome $a_i$ genera dev'essere \(p_i-1\mid n\). Dunque dobbiamo cercare tutti gli $n=p_1\ldots p_r$ con la proprietà che \(p_i-1\mid n\) per ogni $i$. Supponiamo $p_1<p_2<\ldots<p_r$. Siccome $p_i-1$ è $1$ oppure pari, dev'essere necessariamente $p_1=2$. Adesso $p_2-1$ deve dividere $n$, ma i primi che dividono $p_2-1$ sono $<p_2$, quindi dev'essere $p_2-1=p_1$, quindi $p_2=3$. Analogamente, $p_3-1$ divide $n$, quindi i primi che lo dividono possono essere solo $2,3$. Siccome $p_3$ è primo, dev'essere per forza $p_3-1=p_1p_2=6$, e $p_3=7$. Ragionando nello stesso modo si trova $p_4=43$. Adesso c'è un numero finito di possibilità per $p_5-1$, ma nessuna va bene perchè dà valori non primi per $p_5$. Quindi $n\in \{2,2\cdot 3,2\cdot 3\cdot 7,2\cdot 3\cdot 7\cdot 43\}$, e ora basta controllare se questi valori vanno bene o no.

[dan95]

Va bene ma...

Testo nascosto, fai click qui per vederlo

...non ho capito la parte dove dici che $e_i=1$

[hydro]

Va bene ma...

Testo nascosto, fai click qui per vederlo

...non ho capito la parte dove dici che $ e_i=1 $

Testo nascosto, fai click qui per vederlo

Prendi ad esempio $a=p_1^{e_1-1}p_2^{e_2}\ldots p_r^{e_r}$. Allora \(n\mid a(a^n-1)\) per ipotesi, il che significa che \(p_1^{e_1}p_2^{e_2}\ldots p_r^{e_r}\mid p_1^{e_1-1}p_2^{e_2}\ldots p_r^{e_r}((p_1^{e_1-1}p_2^{e_2}\ldots p_r^{e_r})^n-1)\). Ma questo implica che \(p_1\mid ((p_1^{e_1-1}p_2^{e_2}\ldots p_r^{e_r})^n-1)\), cosa che è chiaramente impossibile se $e_1>1$. E così per tutti gli esponenti.

[dan95]

Sì tutto chiaro io avevo preso direttamente $a=p_i$ ecco perché non mi tornava poi ho capito.