n|2^n+1, not very easy form Parma 2007

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

n|2^n+1, not very easy form Parma 2007

Messaggio da salva90 » 30 apr 2007, 12:23

Trovare gli $ n $ naturali per cui $ n|2^n+1 $

Per chi volesse la versione più semplice, trovare tutti gli n naturali per cui $ n $ e $ 2^n+1 $ hanno gli stessi fattori primi

Avatar utente
frengo
Messaggi: 223
Iscritto il: 01 gen 1970, 01:00

Messaggio da frengo » 30 apr 2007, 19:34

uhm,non credo questo problema abbia una soluzione olimpica...

tipo $ n=3^5\cdot19\cdot163\cdot87211 $ funziona, le soluzioni sono tantissime e vanno in un sacco di direzioni...hai una soluzione?

PS il problema carino (non chè IMO19xx/x) è se hai $ n^{2} |2^n+1 $....

ciao ciao

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 30 apr 2007, 20:19

Io non ho una soluzione, anche perchè la versione proposta a Parma è stata corretta e resa pèiù semplice (come ho poi aggiunto nel mio post).
Mi sembra di avere letto una soluzione di questo problema, ma ora che mi ci fai pensare bene forse era quello che haii citato tu :wink:

Vabbe, resta valida la versione più semplice, per chi la vuole provare, che ha soluzione elementare.

E questa per i coraggiosi, magari HiTLeuLeR :wink:

EvaristeG
Site Admin
Messaggi: 4726
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 02 mag 2007, 13:34

No, questo non ha una soluzione olimpica ... ed è il motivo per cui il testo a parma è stato cambiato.
Se qualcuno volesse buttarsi a farlo, consiglio la sezione di matematica non elementare.

Avatar utente
pi_greco_quadro
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da pi_greco_quadro » 02 mag 2007, 17:35

ok work in progress allora.. stufo di scrivere c******e
Ultima modifica di pi_greco_quadro il 02 mag 2007, 20:22, modificato 3 volte in totale.
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"

EvaristeG
Site Admin
Messaggi: 4726
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 02 mag 2007, 17:54

(2n,p-1)=2 ... perchè mai?
n=21, p=7 ... (42, 6)=6.

EvaristeG
Site Admin
Messaggi: 4726
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 02 mag 2007, 18:45

Eh, no ... altrimenti così avresti risolto anche n|2^n+1 ... in particolare non è vero che $ q\le p $ in quanto p è il più grande fattore primo di n, mentre q è il più grande fattore primo di $ 2^p+1 $ che può avere fattori primi che non compaiono in n. Tale disuguaglianza era vera nel caso proposto a parma proprio perchè l'ipotesi diceva che i fattori primi di $ n $ e $ 2^n+1 $ erano gli stessi.
Infine, nota stilistica ... il fatto che n sia pari meglio metterlo all'inizio, sennò col fischio che $ 2^p+1|2^n+1 $ (9=2^3+1 non divide 65=2^6+1).

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 04 mag 2007, 15:28

salva90 ha scritto:Trovare tutti gli n naturali per cui $ n $ e $ 2^n+1 $ hanno gli stessi fattori primi
Sia $ n \in \mathbb{N} $ tale da verificare la condizione imposta dalla consegna del problema. Naturalmente, $ n $ è dispari. Perciò $ 3 \mid (2^n + 1) $, e quindi $ n = 3^k \cdot q $, dove $ k, q \in \mathbb{N}^+ $ e $ \gcd(q,6) = 1 $. Per assurdo, ammettiamo $ q > 1 $. Sia, di conseguenza, $ p \ge 5 $ il più piccolo divisore primo naturale di $ q $. Allora $ 2 < \mbox{ord}_p(2) \le \gcd(2q, p-1) = 2 $, assurdo (vedi qui)! Dunque $ n = 3^k $. Eppure $ 2^{3^2} + 1 = 3^2 \cdot 19 $. Pertanto $ k = 1 $, e in effetti $ n = 3 $ è l'unica soluzione permessa ($ 2^3 + 1 = 3^2 $).

Rispondi