Simpatico quesito sui resti

[Kashaman]

simpatico quesito, che forse qualcuno conosce già

Prove it :
sia $n$ un intero.
il resto della divisione euclidea di $2^n$ per $n$ non è mai uno, se $n>1$



EDIT dovrebbe avere un senso ora.

[UmbertoM1]

Ma scusa, se $n=2$ segue che $2^n-1=3$ e $3:2$ da come resto 1.

[xXStephXx]

Oltre tutto viene 1 come resto per ogni $n$ primo, quindi manco a dire che $n=2$ è un caso isolato xD

[Kashaman]

sorry, ho fatto un macello a riportare la traccia.
Correggo subito.

[xXStephXx]

Forse è un po' troppo "scroccata" come dimostrazione ma dovrebbe andare...

Supponiamo per assurdo [tex]2^n \equiv 1 \pmod n[/tex]
Ovviamente $n$ è dispari, quindi gli $n$ pari sono scarati a priori.
Sia $p$ il più piccolo fattore primo che divide $n$, tale che $n=kp$.
Allora: [tex](2^p)^k \equiv 1 \pmod p[/tex]
Per il piccolo teorema di fermat ne segue: [tex]2^k \equiv 1 \pmod p[/tex].
Cosa valida se e solo se [tex]ord_p(2) | k[/tex]. Ma [tex]ord_p(2) | \phi(p) = p-1[/tex]
Le due cose non sono compatibili perchè se [tex]ord_p(2) | k[/tex] e [tex]ord_p(2) | p-1[/tex] allora
[tex]ord_p(2) | MCD(p-1,k)[/tex]. Essendo $p$ il più piccolo fattore primo di $n$, i fattori primi che contiene $p-1$ sono minori di $p$, mentre i fattori primi di $k$ sono maggiori o uguali a $p$. (ok, tranne se $n$ è primo, ma in quel caso il problema non si pone). Dunque l'MCD vale $1$. Quindi [tex]ord_p(2) =1[/tex]. Da cui [tex]2 \equiv 1 \pmod p[/tex] assurdo.

[Kashaman]

mi sembra perfetta, bravo!