potenze di 2 per un numero primo (bis)

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

potenze di 2 per un numero primo (bis)

Messaggio da angus89 » 08 feb 2008, 13:11

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 $
Ultima modifica di angus89 il 08 feb 2008, 18:15, modificato 1 volta in totale.
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui

fph
Site Admin
Messaggi: 3813
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 08 feb 2008, 13:40

Non era $ 2^n+1 $?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

PubTusi
Messaggi: 60
Iscritto il: 01 feb 2008, 15:30

Messaggio da PubTusi » 08 feb 2008, 13:40

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

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 08 feb 2008, 14:20

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

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 08 feb 2008, 18:16

scusate...ho corretto...(errore di battitura)
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui

Avatar utente
Oblomov
Messaggi: 284
Iscritto il: 23 ott 2005, 13:18
Località: Bologna

Re: potenze di 2 per un numero primo (bis)

Messaggio da Oblomov » 08 feb 2008, 20:43

angus89 ha scritto: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
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. - P. Erdös

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 08 feb 2008, 21:53

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
Messaggi: 60
Iscritto il: 01 feb 2008, 15:30

Messaggio da PubTusi » 09 feb 2008, 11:52

EUCLA ha scritto:
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? :?

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 09 feb 2008, 12:03

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

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 09 feb 2008, 12:46

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
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 09 feb 2008, 13:24

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 $
MIND TORNA CON NOI

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 09 feb 2008, 14:55

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...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui

Rispondi