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

[dan952]

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}$

[hydro1]

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.

[dan952]

@Hydro

$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?...

[hydro1]

"dan95":@Hydro

$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\)…

[dan952]

Sorry 42

[hydro1]

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

[hydro1]

Ci riprovo.

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

Cita

Segnala

[dan952]

Va bene ma...

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

[hydro1]

"dan95":Va bene ma...

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

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.

[dan952]

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