n non divide 2^n-1

[pi_greco_quadro]

Si dimostri che, per ogni intero $ \displaystyle n\geq 2 $

$ \displaystyle n\nmid 2^n-1 $

[darkcrystal]

Sia p il (mitico!) più piccolo primo che divide n.
Allora si ha
$ 2^n \equiv 1 \pmod p $
Ossia che $ ord_p(2) | p-1 $ e $ ord_p(2)|n $, ma questo è assurdo perchè i divisori di p-1 sono più piccoli di p e quindi non possono dividere n. Unica possibilità, $ ord_p(2) $ è 1... ma allora $ 2 \equiv 1 \pmod p $ che è nuovamente assurdo.
Ciao!

[pi_greco_quadro]

@crystal: ok

[hydro]

similmente a quel che ha detto darkcrystal, se p è il minimo primo che divide n, allora $ \gcd(p-1,n)=1 $. Pertanto dall'identità di Bezout, $ \exists x,y \in \mathbb{Z} $ t.c. $ 1=(p-1)x+ny $ da cui segue $ 2^1=2^{(p-1)x} \cdot 2^{ny} $. Per Fermat, $ [2^{(p-1)}]^x \equiv 1 \mod p $, quindi se fosse $ 2^n \equiv 1 \mod p $ si avrebbe $ 2 \equiv 1 \cdot 1 \mod p $, assurdo.

[CapitanoPo]

oppure anche $ (2^n - 1) = ( 2^{n-1} + 2^{n-2} +... + 2 + 1) $ che non è mai divisibile per due in quanto somma di potenze di due più uno..... o sbaglio?? E' la prima volta che posto una soluzione

[salva90]

Hai letto male il testo: non devi esaminare la divisibilità per 2, ma per n. Comunque non ti scoraggiare, errare humanum est

[CapitanoPo]

me pareva semplice
in effetti non aveva molto senso
vabbè al primo post di soluzione ce sta na figuraccia del genere

[Pigkappa]

me pareva semplice
in effetti non aveva molto senso
vabbè al primo post di soluzione ce sta na figuraccia del genere

Per come avevi interpretato l'esercizio, avresti potuto risolverlo semplicemente dicendo che $ 2^n-1 $ è dispari

[salva90]

avresti potuto risolverlo semplicemente

Caro pigkappa, siamo su un forum olimpico, se anche esiste una soluzione semplice è nostro dovere trovare quella più complicata

[HiTLeuLeR]

Si dimostri che, per ogni intero $ \displaystyle n\geq 2 $ $ \displaystyle n\nmid 2^n-1 $

Periodicamente ritornano.