potenze di 2 per un numero primo (bis)

[angus89]

Allora...
Questo è abbastanza semplice, se la mia soluzione è giusta...
Consiglierei soprattutto a chi è agli inizi di provarci dato che la dimostrazione non è tanto difficile

dimostrare che se $ \dispaystyle 2^{n}+1 $ è primo allora $ \dispaystyle n $ è una potenza di $ \dispaystyle 2 $

[fph]

Non era $ 2^n+1 $?

[PubTusi]

Ma $ 2^3-1 $ non era primo un tempo?

[ndp15]

Angus angus..hai dimostrato te stesso ieri che se n non è primo allora $ \dispaystyle 2^{n}-1 $ non puo' essere primo

[angus89]

scusate...ho corretto...(errore di battitura)

[Oblomov]

se $ \dispaystyle 2^{n}+1 $ è primo allora $ \dispaystyle n $ è una potenza di $ \dispaystyle 2 $

Ci provo.

Allora, partendo dal fatto abbastanza noto ed evidente (evidente svolgendo il prodotto dei termini a secondo membro) che $ \displaystyle a^{2k+1}+b^{2k+1}=(a+b)(a^{2k}-a^{2k-1} \cdot b+a^{2k-2}\cdot b^2-...+b^{2k}) $ arrivo a notare, ponendo $ \displaystyle a=2^m $ e $ \displaystyle b=1 $, che un numero P della forma $ \dispaystyle 2^{n}+1 $, se n è multiplo di un qualche numero dispari (cioè $ \displaystyle n=m(2k+1) $), è multiplo di $ \displaystyle 2^m+1 $ e di un fattore maggiore di 1 (per notare ciò, basta porre $ \dispaystyle b=1 $ nel lemmino di cui sopra e vedere come i termini di segno positivo superino sempre i termini negativi se a è maggiore di 1) e quindi non primo (tranne che nel trascurabile caso m=0, nel qual caso P assume il solo valore 2). Ora, abbiamo visto che n non può avere nessun fattore dispari. Il che significa che la sua fattorizzazione in numeri primi contiene solo numeri pari, cioè solo dei 2. Cioè, n è potenza di 2.

Sì, lo so, sono prolisso e avrei avuto bisogno di dimostrare la metà di quella roba, ma è come mi è venuto...

Buonasera a tutti,
Ob

[EUCLA]

Ok. Un'altra:

$ 2^{2n}\equiv 1 \pmod {2^n+1} $

$ 2^{2^n}\equiv 1 \pmod {2^n+1} $ (qua sfrutto il fatto che è primo)

O $ 2^n\vert 2n $ ma questo vale solo per $ n=1,2 $ che son potenze di 2,

o $ 2n\vert 2^n \Rightarrow n\vert 2^{n-1} $ da cui la tesi.

[PubTusi]

O $ 2^n\vert 2n $...

o $ 2n\vert 2^n $...

Scusami, sarò un pò tardo, ma puoi spiegarmi questo passaggio che non riesco a capirlo, please?

[EUCLA]

No, scusa te, l'ho detto male. Cioè quella cosa è vera, però ho sbagliato argomentazione, dunque ci ripenso.

[EUCLA]

Ecco la spiegazione giusta:

$ 2^{n}\equiv -1 \pmod {2^n+1} $

$ 2^{2n}\equiv 1 \pmod {2^n+1} $

$ 2^{2^n}\equiv 1 \pmod {2^n+1} $

Dunque $ ord_{2^n+1} (2) \vert 2^n $ e da qui si ricava che l'ordine è una potenza di 2.

Dal fatto invece che:

$ ord\vert 2n, ord \not \vert n $ si hanno 3 possibilità:

(1) L'ordine non contiene nessuno dei fattori di $ n $.
Allora l'ordine è 2, che rende $ n=1 $

(2) L'ordine è $ 2n \Rightarrow 2n\vert 2^n $ da cui segue che $ n $è potenza di 2.

(3) L'ordine è $ 2k $ con $ k\vert n, k\not =2^a $ → assurdo

[Jacobi]

secondo me e + facile cosi: poniamo $ n = {2^k}d $ con d dispari e $ 2^k||n $, allora:

$ 2^n+1 = (2^{2^k})^d+1^d $, quindi$ 2^{2^k}+1|2^n+1 $ e affinche tale fattore sia banale deve essere $ d=1 $

[angus89]

Sembrano tutte corrette come soluzioni, magari quella più intuitiva era quella cui accennava Oblomov...non l'ho letta bene ma ci siamo...

Bastava sapere che la somma di due quadrati non è mai scomponibile, pertanto doveva essere n sempre divisibile per due, in definitiva una potenza di 2...

Anche quella di EUCLA non è male, anche se sono ancora poco pratico e non sò utilizzare al meglio le congruenze ma mi sembra giusta...