Problema

publiosulpicio · Messaggio da **publiosulpicio** » 01 gen 1970, 01:33

Per quali valori interi positivi di n l\'espressione (2^n+1)/n è un intero?

massiminozippy · Messaggio da **massiminozippy** » 01 gen 1970, 01:33

Questo problema mi piace, lo faccio domani in classe.
 Mica è difficile?

publiosulpicio · Messaggio da **publiosulpicio** » 01 gen 1970, 01:33

Bhè insomma... trovare una dimostrazione non è proprio banale ma si può fare...

XT · Messaggio da XT » 01 gen 1970, 01:33

Non è [2^(n+1)]/n vero publio vero?

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

Forse sono cavolate, visto che è tardi e sono stanco, ma non ho voglia di riconnettere i neuroni per controllare...
 2^n + 1 congruo a -1 mod n è questo che si chiede.
 Per n pari è evidentemente falso: 2^n è pari e kn-1 è dispari quindi...
 Per n primo sappiamo che 2^n congruo a 2 mod n. 2 congruo a -1 solo mod 3 e quindi l\'unico primo possibile è 3 : verificando si ottiene (2^3 +1)/3=3.
 Per il resto boh, ma credo che si possa riuscire a dimostrare che quanto detto sopra vale anche per n che è prodotto di primi di cui almeno 1 maggiore di 3.
 Perciò presumo che gli unici n validi siano nella forma 3^k, ma non so come dimostrarlo... <IMG SRC="images/forum/icons/icon_eek.gif"> <IMG SRC="images/forum/icons/icon_confused.gif"> <IMG SRC="images/forum/icons/icon_razz.gif">

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

Forse ho trovato: 2^r non è congruo a -1 mod r se r è primo>3 e quindi, prendendo un primo s si avrà che 2^(r*s) non è congruo a -1 mod r e viceversa se s è primo maggiore di 3 vale 2^s non congruo a -1 mod s e quindi 2^(r*s)non è congruo a-1 mod s. quindi per un qualche teorema che certamente esiste 2^(r*s) non è congruo a -1 mod r*s perchè tale congruenza vale almeno mod r o mod s, se non per entrambi quando sono primi maggiori di 3. E ciò lascia solo 3^2. qUesto ragionamento può essere esteso similmente a n composto con qualunque numero di fattori primi e lascia come soluzioni quei numeri i cui fattori sono tutti 3.Quindi le soluzioni sono 1,3,9,27,etc.
 
 Ci ho preso?
 
 Buonanotte <IMG SRC="images/forum/icons/icon_wink.gif">

massiminozippy · Messaggio da **massiminozippy** » 01 gen 1970, 01:33

Ci hai preso Evariste, i valori possibili sono quelli tali che n=3^k, con k appartenente a N con zero.
 Si dice \"N con zero\" quando si vuol dire che l\'insieme N è quello dei numeri naturali compreso lo zero?

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

In sè, no. N con 0 è proprio l\'insieme dei numeri naturali escluso lo 0, o almeno così mi pare... quindi k deve appartenere a N, poichè vale anche per k=0 e n=1. <IMG SRC="images/forum/icons/icon_razz.gif">

pennywis3 · Messaggio da **pennywis3** » 01 gen 1970, 01:33

Scusate, ma 2^(9*19)+1 non è divisibile per 9*19?
 
 [2^(9*19)+1=(2^9)^19+1=(2^9+1)*(qualcosa), 2^9+1=513=19*27....]
 
 
 ~p3~

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

Hai ragione, penny! e anche per lo stesso 513, a questo punto. Forse ho trovato l\'errore:
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-03-24 00:14, EvaristeG wrote:
 ... quindi per un qualche teorema che certamente esiste 2^(r*s) non è congruo a -1 mod r*s perchè tale congruenza vale almeno mod r o mod s, se non per entrambi quando sono primi maggiori di 3. E ciò lascia solo 3^2...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 In effetti questo passaggio fa acqua: la congruenza mod r*s vale quando valgono sia quella mod r sia quella mod s. Questo lascia intoccati tutti i multipli di 3, ma evidentemente non è accettabile. Intuitivamente si può dire che,se vale per un certo n1, allora vale anche per tutti i divisori di 2^n1 + 1 maggiori di n1. In quanto a dimostrarlo...nebbia fitta....
 
 <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif">

DD · Messaggio da DD » 01 gen 1970, 01:33

per ogni k esiste un n con k fattori primi tale che n|2^n+1 (cfr imo 2000/5)

publiosulpicio · Messaggio da **publiosulpicio** » 01 gen 1970, 01:33

Sorpresa! Anche questo è un IMO... ma non scoraggiatevi!

publiosulpicio · Messaggio da **publiosulpicio** » 01 gen 1970, 01:33

Ops... mi sono accorto adesso di un piccolo errore nel testo... bhè allora fate questo problema: per quali valori di n interi positivi l\'espressione (2^n+1)/(n^2) è intera?

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

Allora, DD, il risultato che hai citato è interessante, ma non dice molto: servirebbe il risultato opposto. Inoltre, n è dato da qualche formula in funzione di k?
 <IMG SRC="images/forum/icons/icon_confused.gif">
 In quanto a te, caro publio, ce lo dici adesso???? <IMG SRC="images/forum/icons/icon_mad.gif"> <IMG SRC="images/forum/icons/icon_mad.gif"> <IMG SRC="images/forum/icons/icon_mad.gif">
 Il problema è assai più semplice:
 sia a il più piccolo primo che divide n; sia b il più piccolo intero tale che
 2^b=-1 mod a e sia c il più piccolo intero tale che 2^c=1 mod a.
 Sicuramente cVediamo n come funzione lineare di c: n=dc+e allora
 -1=2^n=((2^c)^d)*2^e=2^e mod a perciò e sarà tra b e c.
 Ripetiamo come funzione di b: n=fb+g e allora
 -1=((2^b)^f)*2^g=(-1)^f*2^g. poniamo g>0 e vediamo che se f è pari allora b non è il più piccolo numero =-1 mod a, mentre se f è dispari c non è il più piccolo numero =1 mod a. Dunque g=0 e b divide n, ma b<a e a è il più piccolo primo che divide n, perciò b=1 e 2=-1 mod a; di consequenza a=3 (non può essere due perchè 2^n+1 è dispari e n^2 devee esserlo anch\'esso).
 Ora, poniamo che 3^x divida n e 3^(x+1) non lo divida: se scriviamo 2=3-1 allora possiamo sviluppare (3-1)^n+1 come=1-1+3n+1/2(n-1)n3^2+....
 3n è divisibile per 3^(x+1) e non è difficile dimostrare che tutti gli altri termini sono divisibili per 3^(x+2). Allora 2^n+1 è divisibile al massimo per 3^(x+1), ma esso è anche divisibile per 3^(2x) per ipotesi e quindi x=1.
 Se ripetiamo il ragionamento assegnando a come il più piccolo primo maggiore di 3 che divide p, troveremo ancora che a deve esser tale che 2=-1 mod a o 2^3=-1 mod a, che porta ad a=3, che è contraddittorio. Dunque non esiste un altro primo maggiore di 3 che divida p.
 
 La soluzione è tre. <IMG SRC="images/forum/icons/icon_biggrin.gif">
 
 Cmq ho ancora in mente l\'altro... <IMG SRC="images/forum/icons/icon_razz.gif">