teoria dei numeri (o simile)

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

premetto che non sarò pittoresco come Antimateria ed EvaristeG...
<BR>
<BR>trovare tutti gli interi positivi n tali che
<BR>
<BR>[2^(n)+2]/n sia intero (100<=n<=1997)
<BR>
<BR>enjoy
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
bug84
Messaggi: 47
Iscritto il: 01 gen 1970, 01:00
Località: casa tua (sono dietro di te)

Messaggio da bug84 »

se non ricordo male, ha a che fare coi numeri primi: vale se e solo se n è primo, e (forse) lo puoi dimostrare partendo dal binomiale...
<BR>c\'ho azzeccato? Se no, era una cosa simile (forse con -2 al posto di +2)
quando il gioco si fa duro, i duri cominciano a giocare

(John "Bluto" Belushi)
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

up!
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
cekko
Messaggi: 196
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da cekko »

(2^(n)+2)/n = 2(2^(n-1)+1)/n
<BR>se n è primo non è mai vero: a^p-1==1 modp se p è primo e a non è multiplo di p.
<BR>se n è multiplo di 4 non va bene: 2^(n-1)+1 è dispari.
<BR>per ora non mi viene altro.
"...e d'un tratto capii che il pensare è per gli stupidi, mentre i cervelluti si affidano all'ispirazione e a quello che il buon Bog manda loro".
Alex, Arancia Meccanica.
Avatar utente
caratheodory
Messaggi: 8
Iscritto il: 01 gen 1970, 01:00
Località: Alba (CN)

Messaggio da caratheodory »

Cekko ha rag...
<BR>
<BR>Di sicuro n è pari della forma 2 * (a1^q1)*(a2^q2)*...(ak^qk) dove gli ak sono numeri primi e qk sono le rispettive molteplicità.
<BR>In poche parole n è pari, prodotto di 2 ed un numero dispari..
<BR>
<BR>Per vederlo basta porre n =2h.. L\'esp. semplifica in
<BR>
<BR>[2^(2h - 1)+1]/h
<BR>
<BR>il termine a num. è dispari ed h per essere suo divisore non può essere pari..
<BR>
<BR>
Bonardi Emanuele
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

bene...
<BR>quindi il problema ora è trovare tutti gli 50<=h<=998
<BR>tali che h | 2^(2h-1)+1
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
caratheodory
Messaggi: 8
Iscritto il: 01 gen 1970, 01:00
Località: Alba (CN)

Messaggio da caratheodory »

Altre osservazioni..
<BR>
<BR>2^(2h - 1) + 1 è sicuramente un multiplo di 3...
<BR>
<BR>Osserviamo che 2 = 2 (mod 3) , 2^(2)= 1 (mod 3), 2^(3)= 2 (mod 3)..
<BR>in generale 2^(2k) = 1 (mod 3) e soprattutto 2^(2k - 1) = 2 (mod 3)
<BR>con k = 1, 2, ...
<BR>
<BR>Pertanto se 2^(2k - 1 ) - 2 è un multiplo di 3
<BR>
<BR>Lo sarà anche 2^(2k - 1) - 2 + = 2^(2k - 1) + 1<BR><BR>[ Questo Messaggio è stato Modificato da: caratheodory il 08-12-2003 20:28 ]
Bonardi Emanuele
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

Ciao! Mi permetto di intervenire su questo tema giusto per fare qualche piccola annotazione, trascendendo un attimino dai vincoli imposti alla libera variabilità del parametro n€N<sub>0</sub>, ove N<sub>0</sub> è l\'insieme degli interi positivi.
<BR>
<BR>i) Osserviamo innanzitutto che n = 1 ed n = 2 sono soluzioni banali al problema, sebbene debbano poi essere escluse poiché non rientrano nel range di variazione stabilito nella traccia. D\'ora innanzi, supporremo pertanto n ≥ 3.
<BR>
<BR>ii) Se n è una soluzione al nostro problema ed n ≡ 1 (mod. 2), allora:
<BR>
<BR>2<sup>n</sup> + 2 ≡ 2*(2<sup>n - 1</sup> + 1) ≡ 0 (mod. n) ==> 2<sup>n - 1</sup> + 1 ≡ 0 (mod. n)
<BR>
<BR>poiché, in tal caso: D(2,n) = 1.
<BR>
<BR>iii) Cekko ha già osservato che n non puot\'essere un numero PRIMO di valenza dispari, siccome s\'avrebbe altrimenti (stante l\'osservazione (i)) che:
<BR>
<BR>2<sup>n-1</sup> + 1 ≡ (2<sup>n-1</sup> - 1) + 2 ≡ 0 (mod. n) ==>
<BR>
<BR>==> [Per il piccolo th. di Fermat] ==> 2 ≡ 0 (mod. n)
<BR>
<BR>condizione palesemente assurda, poiché (essendo un primo dispari): n ≥ 3. Indi, se esiste un n€N<sub>0</sub> che rende la frazione (2<sup>n</sup> + 2)/n un intero, allora necessariamente n non può essere un PRIMO di valenza dispari, fatto che tuttavia non esclude nel modo più assoluto l\'eventualità che n possa essere comunque un numero COMPOSTO della medesima valenza! Siamo d\'accordo? E allora, mi chiedo, perché limitarsi a ricercare le potenziali soluzione al problema posto da Talpuz nella sola classe degli interi positivi di valenza pari? E soprattutto, perché tu, Talpuz, hai assecondato le conclusioni di qualcuno (Caratheodory) in questo senso? Si badi bene, io non sto dicendo che esistono delle soluzioni in numeri dispari al quesito di cui qui si discute (e in verità non affermo neppure il contrario...): mi riservo di osservare soltanto che questa possibilità non è stata ancora esclusa!
<BR>
<BR>
<BR>iv) Supponiamo che n sia la potenza di un numero primo q ≥ 3, cioè assumiamo
<BR>n = q<sup>m</sup>, con m ≥ 2 (per non ricadere nel caso già considerato al punto (ii)). Sotto quest\'ipotesi, se n è soluzione del problema, allora (vedi ancora l\'osserv. (i)):
<BR>
<BR>q<sup>m</sup> | 2<sup>(q<sup>m</sup> - 1)</sup> + 1 <=> 2<sup>(q<sup>m</sup> - 1)</sup> + 1 ≡ 0 (mod. q) ($)
<BR>
<BR>Ora: q<sup>m</sup> - 1 ≡ 0 (mod. q - 1), dacché: q<sup>m</sup> - 1 = (q - 1)*sum[k=0,...,m-1] q<sup>m-k</sup>. E d\'altro canto: q - 1 = f(q), essendo f(·) la funzione di Eulero. Ma allora (in base a un noto risultato di <!-- BBCode Start --><I>Teoria Elementare dei Numeri</I><!-- BBCode End -->):
<BR>
<BR>2<sup>(q<sup>m</sup> - 1)</sup> ≡ 1 (mod. q) <=> 2<sup>(q<sup>m</sup> - 1)</sup> - 1 ≡ 0 (mod. q)
<BR>
<BR>Combinando pertanto quest\'ultima relazione con la ($), si deduce ancora che:
<BR>
<BR>2<sup>(q<sup>m</sup> - 1)</sup> + 1 ≡ 0 (mod. q) ==> [2<sup>(q<sup>m</sup> - 1)</sup> - 1] + 2 ≡ 0 (mod. q)
<BR>
<BR>e quindi: 2 ≡ 0 (mod. q), che di nuovo è assurdo, poiché q è un primo dispari, e dunque q ≥ 3. Ne segue che, se n è una soluzione di valenza dispari al problema di Talpuz, allora n è quantomeno il prodotto delle potenze (eventualmente a esponente unitario) di due numeri primi distinti ≥ 3.
<BR>
<BR>NOTA: in effetti, quest\'ultima osservazione ricopre al suo interno, come caso
<BR>particolare, il contenuto della precedente, che di conseguenza avrei anche potuto omettere, per brevità! Ho preferito inserirla in ogni caso per evidenziare (a solo fin di bene) gli svarioni commessi in questo topic!
<BR>
<BR>v) Se n è una soluzione al nostro problema ed n ≡ 0 (mod. 2), allora, come già osservato dal solito (nel senso che ti ho già nominato poco sopra) Cekko:
<BR>n !≡ 0 (mod. 4), ove !≡ si legge \"incongruo a\". Dunque, se n è una soluzione di valenza pari, concordemente all\'ultimo post di Caratheodory, non può che doversi assumere n = 2p, ove p è (in linea di principio) un numero intero positivo ≥ 3 (primo o composto) di valenza dispari (ricordo che abbiamo assunto inizialmente n > 2). In particolare, poiché dev\'essere:
<BR>
<BR>2<sup>2p</sup> + 2 ≡ 0 (mod. 2p) ==> 2<sup>2p-1</sup> + 1 ≡ 0 (mod. p)
<BR>
<BR>vi) Con riferimento al punto (v), ammettiamo che p possa rappresentare una qualche potenza di un numero primo di valenza dispari; ovvero assumiamo
<BR>p = q<sup>m</sup>, con m ≥ 2 e q primo ≥ 3. Allora, stante l\'osservazione (v), dovrà essere:
<BR>
<BR>2<sup>2q<sup>m</sup> - 1</sup> + 1 ≡ 0 (mod. q<sup>m</sup>) ==> 2<sup>2q<sup>m</sup> - 1</sup> + 1 ≡ 0 (mod. q) ==>
<BR>
<BR>==> (2<sup>q<sup>m</sup></sup> + 2)*(2<sup>q<sup>m</sup> - 1</sup> - 1) + 3 ≡ 0 (mod. q) ==> 3 ≡ 0 (mod. q) ==> q = 3
<BR>
<BR>quando si consideri (vedi le argomentazioni promosse in seno all\'osserv. (iv)) che, essendo q un numero primo di valenza dispari: 2<sup>q<sup>m</sup> - 1</sup> - 1 ≡ 0 (mod. q), e quindi pure: 2<sup>q<sup>m</sup></sup> + 2)*(2<sup>q<sup>m</sup> - 1</sup> - 1) ≡ 0 (mod. q). Dunque, se n è una qualche soluzione al problema di Talpuz (privo, ribadisco, delle sue limitazioni!) nella forma 2q<sup>m</sup>, con q primo dispari ed m ≥ 1, allora necessariamente q = 3 ed n = 2 * 3<sup>m</sup>. Ora, evidentemente, per m = 1, ovvero per n = 6, il problema ammette soluzione (sebbene non inclusa entro il range specificato dalla traccia), datosi che: 2<sup>6-1</sup> + 1 ≡ 33 ≡ 0 (mod. 3). Tuttavia, cio\' non esclude che possano esistere delle altre soluzione di questa stessa specie per m ≥ 2. Ammettiamo allora per assurdo che possa esservene alcuna. In tal caso, stante la condizione espressa dalla (v), dovrebbe risultare:
<BR>
<BR>2<sup>2*3<sup>m</sup> - 1</sup> + 1 ≡ 0 (mod. 3<sup>m</sup>) ==> 2<sup>2*3<sup>m</sup> - 6 + 5</sup> + 1 ≡ 0 (mod. 9) ==>
<BR>
<BR>==> 2<sup>5</sup>*[2<sup>6*(3<sup>m-1</sup> - 1)</sup> - 1] + 2<sup>5</sup> + 1 ≡ 0 (mod. 9) (£)
<BR>
<BR>Del resto, in accordo al teorema di Euler-Fermat, essendo
<BR>f(9) = f(3<sup>2</sup>) = 3*f(3) = 3*(3-1) = 6: 2<sup>f(n)</sup> ≡ 2<sup>6</sup> ≡ 1 (mod. 9), ove f(·) denota (come di consueto) la funzione di Eulero. Ne consegue (come già ho ricordato implicitamente in riferimento all\'osserv. (iv)) che:
<BR>2<sup>k*f(9)</sup> ≡ 2<sup>6k</sup> ≡ 1 (mod. 9), per ogni k€N<sub>0</sub>. Ora, poiché si suppone m ≥ 2: 3<sup>m-1</sup> - 1 ≥ 3 - 1 = 2 > 0, cosicché: 2<sup>6*(3<sup>m-1</sup> - 1)</sup> - 1 ≡ 0 (mod. 9); onde dedurne - sulla base della precedene relazione (£) - che dev\'essere:
<BR>
<BR>2<sup>5</sup> + 1 ≡ 0 (mod. 9) ==> 33 ≡ 0 (mod. 3<sup>2</sup>)
<BR>
<BR>e cio\' è assurdo! La contraddizione, determinata dall\'aver supposto che un intero positivo n della forma 2*3<sup>m</sup> potesse essere soluzione del problema di Talpuz per m ≥ 2 porta necessariamente a concludere (in sintesi di quanto sinora stabilito) che l\'unica soluzione della forma n = 2*p<sup>m</sup>, con p primo dispari ed m ≥ 1, si ha assumendo p = 3 ed m = 1, ovvero n = 6.
<BR>
<BR>vi) Dunque, tirando le somme (rimosse al solito le limitazioni di sorta):
<BR>- n = 1, n = 2 sono soluzioni banali al problema;
<BR>- se esistono delle soluzioni per n dispari > 2, allora n dev\'essere il prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti ≥ 3;
<BR>- le eventuali soluzioni per n pari > 2, sono tutte, ad eccezione del caso singolare n = 6, della forma n = 2p, ove p è un intero positivo ≥ 15 di valenza dispari che sia altresì prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti ≥ 3.
<BR>
<BR>Per il momento, credo di potermi fermar qui! Buon lavoro a tutti, dunque...
<BR>
<BR>Salvo (alias euler_25)
<BR>
<BR>----
<BR>
<BR>\"Ho voluto capire i cuori degli uomini.
<BR>Ho voluto sapere perché le stelle brillano in cielo.
<BR>E ho cercato di comprendere il potere pitagorico
<BR>per il quale il numero esercita il proprio imperio sul flusso.\"
<BR>
<BR> Bertrand Russel<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 04-01-2004 16:39 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

Come già nel mio precedente intervento su questo medesimo tema del forum, prescinderò nelle considerazioni dai vincoli imposti dalla traccia del quesito alla libera variabilità del parametro intero n > 0.
<BR>
<BR>Richiamo innanzitutto brevemente le conclusioni che avevo formulato nel mio ultimo post su questo topic:
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 14-12-2003, 22:48, euler_25 wrote:
<BR>i) n = 1, n = 2 sono soluzioni banali al problema;
<BR>ii) se esistono delle soluzioni per n dispari > 2, allora n dev\'essere il prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti >= 3;
<BR>iii) le eventuali soluzioni per n pari > 2, sono tutte, ad eccezione del caso singolare n = 6, della forma n = 2h, ove h è un intero positivo ≥ 15 di valenza dispari che sia altresì prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti ≥ 3.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Procediamo a questo punto distinguendo fra le due possibili alternative qui di seguito enumerate:
<BR><!-- BBCode Start --><B>1<sup>o</sup> caso</B><!-- BBCode End -->: sia n > 2 il prodotto di r > 1 numeri primi di valenza dispari p<sub>1</sub>, p<sub>2</sub>,..., p<sub>r</sub> secondo la rappresentazione canonica (peraltro, univocamente definita):
<BR>
<BR>n = p<sub>1</sub><sup>a<sub>1</sub></sup> * p<sub>2</sub><sup>a<sub>2</sub></sup> * ... * p<sub>r</sub><sup>a<sub>r</sub></sup>
<BR>
<BR>ove a<sub>i</sub> > 0 è la molteplicità con cui il generico p<sub>i</sub> interviene nella relazione precedente quale fattore della decomposizione in primi di n, per ogni i = 1, 2, ..., r. Ora, se n è soluzione del nostro problema, allora chiaramente n soddisfa la (ii); e pertanto:
<BR>
<BR>2<sup>n - 1</sup> + 1 ≡ 0 (mod.n) ==> 2<sup>n - 1</sup> ≡ -1 (mod.p<sub>i</sub>) ($)
<BR>
<BR>per ogni i = 1, 2, ..., r. D\'altra parte, n è dispari, poiché prodotto di numeri interi di valenza dispari. <!-- BBCode Start --><I>Ergo</I><!-- BBCode End -->, n - 1 è pari, e tanto è sufficiente per concludere che, se n costituisce effettivamente una soluzione del problema di Talpuz, allora la congruenza quadratica: x<sup>2</sup> ≡ -1 (mod.p<sub>i</sub>) è risolvibile (in interi) per ogni i = 1, 2, ..., r, come suggerito dalla relazione ($). Adesso, C.N.S. affinché il vincolo anzidetto risulti soddisfatto è che -1 sia residuo quadratico di p<sub>i</sub>, per ogni i = 1, 2, ...,r; ovvero che:
<BR>
<BR>Jacobi(-1, p<sub>i</sub>) = 1, per ogni i = 1, 2, ...,r (£)
<BR>
<BR>pur di considerare che, in tutta evidenza: D(-1,p<sub>i</sub>) = 1, e rammentare che (per ipotesi) p<sub>1</sub>, p<sub>2</sub>,..., p<sub>r</sub> sono tutti primi di valenza dispari. Ora, come qui supporrò sia noto:
<BR>
<BR>Jacobi(-1, p<sub>i</sub>) = (-1)<sup>(p<sub>i</sub> - 1)/2</sup>
<BR>
<BR>e pertanto la (£) risulta verificata se e soltanto se:
<BR>
<BR>(p<sub>i</sub> - 1)/2 ≡ 0 (mod.2) ==> p<sub>i</sub> ≡ 1 (mod.4)
<BR>
<BR>per ogni i = 1, 2, ..., r. In altre parole, tutti i primi che intervengono nella decomposizione canonica di n, quando n sia soluzione del problema di Talpuz (relativamente al caso qui preso in esame), devono essere necessariamente della forma 4k + 1, con k intero > 0. E poiché qui si sta ammettendo (coerentemente con la (ii)) che n sia prodotto di r > 1 numeri primi distinti di valenza dispari, se ne conclude (sulla base delle argomentazioni proposte) che necessariamente n ≥ 5 * 13 = 65, dacché i più piccoli numeri primi della forma 4k + 1 sono per l\'appunto il 5 e il 13.
<BR>
<BR><!-- BBCode Start --><B>2<sup>o</sup> caso</B><!-- BBCode End -->: sia n = 2h, ove h ≥ 15 è il prodotto di s > 1 numeri primi di valenza dispari q<sub>1</sub>, q<sub>2</sub>,..., q<sub>s</sub> secondo la rappresentazione canonica (come sempre, univocamente definita):
<BR>
<BR>h = q<sub>1</sub><sup>b<sub>1</sub></sup> * q<sub>2</sub><sup>b<sub>2</sub></sup> * ... * q<sub>s</sub><sup>b<sub>s</sub></sup>
<BR>
<BR>ove b<sub>i</sub> > 0 è la molteplicità con cui il generico q<sub>i</sub> interviene nella relazione precedente quale fattore della decomposizione in primi di h, per ogni i = 1, 2, ..., s. Ora, se n è soluzione del nostro problema, allora chiaramente n soddisfa la (iii); perciocché:
<BR>
<BR>2<sup>2h - 1</sup> + 1 ≡ 0 (mod. h) ==> 2<sup>2(h - 1)</sup> ≡ -1(mod. q<sub>i</sub>) ==>
<BR>
<BR>==> 2<sup>2(h - 1)</sup> ≡ -1*[2<sup>-1</sup>(mod. q<sub>i</sub>)] (mod. q<sub>i</sub>) (&)
<BR>
<BR>per ogni i = 1, 2, ..., s, ove 2<sup>-1</sup>(mod. q<sub>i</sub>) denota l\'inverso di 2 modulo q<sub>i</sub>, la cui esistenza è garantita dal fatto d\'essere: D(2, q<sub>i</sub>) = 1. D\'altro canto, per il piccolo teorema di Fermat, stante questa medesima condizione, avviene che:
<BR>
<BR>p.o. i = 1, 2, ..., r: 2<sup>q<sub>i</sub> - 1</sup> ≡ 1 (mod. q<sub>i</sub>) ==> [2<sup>-1</sup>(mod. q<sub>i</sub>)] ≡ 2<sup>q<sub>i</sub> - 2</sup> (mod. q<sub>i</sub>)
<BR>
<BR>onde dedurne, in virtù della (&), che ancor dev\'essere (per ogni i = 1, 2, ..., s):
<BR>
<BR>2<sup>2(h - 1)</sup> ≡ -2<sup>q<sub>i</sub> - 2</sup> (mod. q<sub>i</sub>) (#)
<BR>
<BR>E poiché: h - 1 > 0, tanto è sufficiente per concludere che, se n costituisce effettivamente una soluzione dello spinoso problema di Talpuz, allora la congruenza quadratica: y<sup>2</sup> ≡ -2<sup>q<sub>i</sub> - 2</sup> (mod.q<sub>i</sub>) è risolvibile (in interi) per ogni i = 1, 2, ..., s, come suggerito dalla relazione (#). Ora, C.N.S. affinché lo statement anzidetto risulti soddisfatto è che -2<sup>q<sub>i</sub> - 2</sup> sia residuo quadratico di q<sub>i</sub>, per ogni i = 1, 2, ...,s; ovvero che:
<BR>
<BR>Jacobi(-2<sup>q<sub>i</sub> - 2</sup>, q<sub>i</sub>) = 1, per ogni i = 1, 2, ...,s (§)
<BR>
<BR>pur di considerare che, in tutta evidenza: D(-2<sup>q<sub>i</sub> - 2</sup>,q<sub>i</sub>) = 1, e rammentare che (per ipotesi) q<sub>1</sub>, q<sub>2</sub>,..., q<sub>s</sub> sono tutti primi di valenza dispari. Ora, in base alle proprietà del simbolo di Jacobi (che qui darò per note):
<BR>
<BR>Jacobi(-2<sup>q<sub>i</sub> - 2</sup>, q<sub>i</sub>) = Jacobi(-1, q<sub>i</sub>) * Jacobi(2<sup>q<sub>i</sub> - 2</sup>, q<sub>i</sub>) =
<BR>
<BR>= Jacobi(-1, q<sub>i</sub>) * [Jacobi(2, q<sub>i</sub>)]<sup>q<sub>i</sub> - 2</sup> =
<BR>
<BR>[Poiché la differenza q<sub>i</sub> - 2 ha valenza dispari per ogni i = 1, 2, ..., r]
<BR>
<BR>= Jacobi(-1, q<sub>i</sub>) * [Jacobi(2, q<sub>i</sub>)] = (-1)<sup>(q<sub>i</sub> - 1)/2</sup> * (-1)<sup>(q<sub>i</sub><sup>2</sup> - 1)/8</sup>
<BR>
<BR><!-- BBCode Start --><I>Ergo</I><!-- BBCode End -->, se q<sub>i</sub> = 4k<sub>i</sub> + 1, allora la (§) è verificata se e soltanto se:
<BR>
<BR>(-1)<sup>2k<sub>i</sub></sup> * (-1)<sup>k<sub>i</sub>(2k<sub>i</sub> + 1)</sup> = 1 ==> (-1)<sup>k<sub>i</sub></sup> = 1
<BR>
<BR>donde k<sub>i</sub> ≡ 0 (mod. 2), e quindi: q<sub>i</sub> = 8m<sub>i</sub> + 1, con m<sub>i</sub> > 0. Se poi, di converso: q<sub>i</sub> = 4k<sub>i</sub> + 3, allora la (§) risulta valida se e soltanto se:
<BR>
<BR>(-1)<sup>2k<sub>i</sub> + 1</sup> * (-1)<sup>2k<sub>i</sub> + 3k<sub>i</sub> + 1</sup> = 1 ==> (-1)<sup>k<sub>i</sub></sup> = 1
<BR>
<BR>donde ancora k<sub>i</sub> ≡ 0 (mod. 2), e quindi: q<sub>i</sub> = 8m<sub>i</sub> + 3, con m<sub>i</sub> ≥ 0, per ogni i = 1, 2, ..., r. In altre parole, tutti i primi che intervengono nella decomposizione canonica di h, quando n = 2h sia soluzione del problema di Talpuz (relativamente al caso qui preso in esame), devono essere necessariamente della forma 8k + 1 (con k > 0) o della forma 8k + 3 (con k ≥ 0). E poiché qui si sta ammettendo (coerentemente con la (iii)) che h sia prodotto di r > 1 numeri primi distinti di valenza dispari, se ne trae (sulla base delle argomentazioni proposte) che necessariamente n = 2h ≥ 2 * (3 * 11) = 66, dacché i più piccoli numeri primi delle forme indicate sono per l\'appunto il 3 e l\'11.
<BR>
<BR>Riassumendo allora il contenuto di questo e del precedente post, possiamo concludere che:
<BR>
<BR>i) n = 1, n = 2 sono soluzioni banali al problema;
<BR>ii) se esistono delle soluzioni per n dispari > 2, allora n dev\'essere il prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti, tutti comunque della forma 4k + 1, con k > 0. Dunque, in questo caso particolare, dovrà essere n ≥ 65;
<BR>iii) le eventuali soluzioni per n pari > 2, sono tutte, ad eccezione del caso singolare n = 6, della forma n = 2h, ove h è un intero positivo di valenza dispari che sia altresì prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti, tutti comunque della forma 8k + 1 (con k ≥ 1) o della forma 8k + 3 (con k ≥ 0). Onde evincerne che, in tal caso, dovrà
<BR>essere necessariamente n ≥ 66.
<BR>
<BR>E per il momento, credo ancora di potermi fermare qui... ciao, buon lavoro e alla prossima! :-)
<BR>
<BR>Salvo Tr. alias euler_25<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 04-01-2004 16:38 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

per \"Jacobi (a,p)\" intendi la caratteristica quadratica di a mod p?
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

Talpuz, scusami tanto se ho tardato nel risponderti, ma stavo perfezionando <!-- BBCode Start --><I>alcuni</I><!-- BBCode End --> dettagli del post precedente! E allora... poiché definire il simbolo di Jacobi presuppone aver preventivamente introdotto il simbolo di Legendre, partiamo da quest\'ultimo, d\'accordo? Ora, se q è un numero intero qualsiasi e p un numero primo > 2, si pone (per definizione):
<BR>
<BR>Legendre(q, p) = 0 se q è multiplo di p;
<BR>Legendre(q, p) = 1 se D(q,p) = 1 e q è residuo quadratico di p;
<BR>Legendre(q, p) = -1 se D(q,p) = 1 e q <!-- BBCode Start --><I>non</I><!-- BBCode End --> è residuo quadratico di p
<BR>
<BR>ove, supposto D(q,p) = 1, diciamo che q è residuo quadratico di p se e soltanto se: q<sup>(p - 1)/2</sup> ≡ 1 (mod. p). In caso contrario, diciamo (senz\'altro) che q non è residuo quadratico di p. Ciò premesso, veniamo finalmente alla definizione del simbolo di Jacobi. Se q e P sono due numeri interi qualsiasi tali che sia comunque P ≡ 1 (mod.2), allora si pone (per definizione):
<BR>
<BR>Jacobi(q,P) = Legendre(q,p<sub>1</sub>)*Legendre(q,p<sub>2</sub>)*...*Legendre(q,p<sub>n</sub>)
<BR>
<BR>ove p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>n</sub> sono numeri primi (> 2) e p<sub>1</sub>* p<sub>2</sub>* ...*p<sub>n</sub> = P.
<BR>
<BR>Ora, tuttavia, Talpuz, per rispondere completamente alla tua domanda, dovresti chiarirmi cio\' che TU intendi parlando del \"carattere quadratico di a (mod.p)\". E\' pacifico che, sulle definizioni, bisogna prima accordarsi per poi poterne dibattere, giusto? Ciao... <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR>P.S.: Germania, è tutto chiaro quel che ho detto? <IMG SRC="images/forum/icons/icon_biggrin.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 21-12-2003 18:53 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
germania2002
Messaggi: 821
Iscritto il: 01 gen 1970, 01:00
Località: Cosenza
Contatta:

Messaggio da germania2002 »

ragazzi scusate l\'ignoranza, ma io su questo forum sono venuto x imparare:
<BR>
<BR>residuo quadratico???
<BR>D(q,p) è un\'insieme o una funzione?[addsig]
"un uomo deve migliorare di qualcosa il mondo, se si vuole sentire realizzato..."
"Deutschland der beste Staat!"
[url:pvcj9bic]http://www.grid.org[/url:pvcj9bic] (pc vs cancro,sars,peste)
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

ah...
<BR>in effetti io pensavo al simbolo di Legendre, non conoscevo quello di Jacobi
<BR>
<BR>x Germania:
<BR>- con D(a,b) penso che Euler intenda l\'MCD (massimo comun divisore)
<BR>- dati un primo p e un naturale a tali che MCD(a,p)=1, a si dice residuo quadratico modulo p se la congruenza a==n<sup>2</sup> (mod p) ha soluzione, ovvero se esiste un quadrato che dà lo stesso resto di a nella divisione per p
<BR>
<BR>se non sai cos\'è una congruenza o vuoi approfondire, chiedi pure!
<BR>bye<BR><BR>[ Questo Messaggio è stato Modificato da: talpuz il 21-12-2003 21:30 ]
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
germania2002
Messaggi: 821
Iscritto il: 01 gen 1970, 01:00
Località: Cosenza
Contatta:

Messaggio da germania2002 »

grazie raga...
<BR>chiederò chiederò[addsig]
"un uomo deve migliorare di qualcosa il mondo, se si vuole sentire realizzato..."
"Deutschland der beste Staat!"
[url:pvcj9bic]http://www.grid.org[/url:pvcj9bic] (pc vs cancro,sars,peste)
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 »

Dopo così tanto tempo dall\'ultimo aggiornamento, finalmente ci ritroviamo per aggiungere qualche nuovo elemento alla soluzione del problema originariamente posto dal buon Talpuz.
<BR>
<BR>Premetto al mio intervento alcune definizioni e un certo numero di risultati teorici di cui ci serviremo diffusamente nel prosieguo:
<BR>
<BR><!-- BBCode Start --><B>Nota 1</B><!-- BBCode End -->: siano n€N<sub>0</sub>, con N<sub>0</sub> := N\\{0}, ed a un qualsivoglia intero primo con n, ovvero tale che: D(n, a) = 1. Posto Ω := {x€N<sub>0</sub>: a<sup>x</sup> ≡ 1 (mod. n)}, osserviamo che Ω rappesenta (per costruzione) un sottoinsieme di N; inoltre, Ω è non vuoto, poiché, coerentemente con il th. di Euler-Fermat: f(n)€Ω, essendo f(-) la funzione di Eulero. Dunque, riassumendo, Ω è un sottoinsieme non vuoto dei naturali; <!-- BBCode Start --><I>ergo</I><!-- BBCode End -->, per il teorema del buon ordine, Ω è dotato d\'elemento minimo (peraltro unico!). Queste considerazioni giustificano pertanto la seguente:
<BR>
<BR><!-- BBCode Start --><B>Definizione 1</B><!-- BBCode End -->: siano n€N<sub>0</sub>, con N<sub>0</sub> := N\\{0}, ed a un qualsivoglia intero primo con n, ovvero tale che: D(n, a) = 1. Si dice allora <!-- BBCode Start --><I>gaussiano di n alla base a</I><!-- BBCode End -->, e si scrive gss(n, a), l\'elemento minimo dell\'insieme Ω := {x€N<sub>0</sub>: a<sup>x</sup> ≡ 1 (mod. n)}; si pone cioè: gss(n, a) = min(Ω).
<BR>
<BR><!-- BBCode Start --><B>Nota 2</B><!-- BBCode End -->: con riferimento alla definizione precedente, è chiaro che, per le proprietà generali di cui gode l\'elemento minimo di un insieme (ovviamente, quando n\'è garantita l\'esistenza!): gss(n, a)€Ω, e dunque (secondo costruzione): a<sup>gss(n, a)</sup> ≡ 1 (mod. n). Non è difficile allora dimostrare la consistenza dei seguenti risultati:
<BR>
<BR><!-- BBCode Start --><B>Teorema 1</B><!-- BBCode End -->: siano n€N<sub>0</sub> ed a un qualsivoglia intero primo con n, ovvero tale che: D(n, a) = 1. C.N.S. affinché s\'abbia: a<sup>m</sup> ≡ 1 (mod. n), essendo m€N, è che risulti m ≡ 0 (mod. gss(n, a)).
<BR>
<BR><!-- BBCode Start --><B>Teorema 2</B><!-- BBCode End -->: siano n€N<sub>0</sub> ed a un qualsivoglia intero primo con n, ovvero tale che: D(n, a) = 1. C.N.S. affinché esista un m€N tale che a<sup>m</sup> ≡ - 1 (mod. n) è che risulti gss(n, a) ≡ 0 (mod. 2); nel qual caso, comunque fissato un r€N, avviene che: a<sup>r</sup> ≡ - 1 (mod. n) se e soltanto se: r = ½ gss(n, a) * (2k + 1), per qualche k€N.
<BR>
<BR>Ciò premesso, prima di procedere oltre, richiamo brevemente (come al solito...) i risultati parziali acquisiti sino a questo punto:
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>i) n = 1, n = 2 sono soluzioni banali al problema;
<BR>ii) se esistono delle soluzioni per n dispari > 2, allora: 2<sup>n</sup> + 1 ≡ 0 (mod. n) ed n è il prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti, tutti comunque della forma 4k + 1, con k > 0. Dunque, in questo caso particolare, dovrà essere n ≥ 65;
<BR>iii) le eventuali soluzioni per n pari > 2, sono tutte, ad eccezione del caso singolare n = 6, della forma n = 2h, ove: 2<sup>2h - 1</sup> + 1 ≡ 0 (mod. h) ed h è un intero positivo di valenza dispari che sia altresì prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti, tutti comunque della forma 8k + 1 (con k ≥ 1) o della forma 8k + 3 (con k ≥ 0). Onde evincerne che, in tal caso, dovrà essere necessariamente n ≥ 66.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Mostreremo nel prosieguo che il caso ii) non conduce ad alcuna soluzione, confermando così a distanza di tanto tempo una <!-- BBCode Start --><I>brillante intuizione</I><!-- BBCode End --> (?) di Caratheodory. Supponiamo infatti per assurdo che esista un n > 2 tale che:
<BR>2<sup>n</sup> + 1 ≡ 0 (mod. n). Allora, dal th. fondamentale dell\'Aritmetica e sulla base delle condizioni riferite al punto ii), n è il prodotto di r > 1 numeri primi distinti di valenza dispari p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>r</sub> secondo la rappresentazione canonica (peraltro, univocamente definita):
<BR>
<BR>n = p<sub>1</sub><sup>a<sub>1</sub></sup> * p<sub>2</sub><sup>a<sub>2</sub></sup> * ... * p<sub>r</sub><sup>a<sub>r</sub></sup>
<BR>
<BR>ove a<sub>i</sub> > 0 è la molteplicità con cui il generico p<sub>i</sub> interviene nella relazione precedente quale fattore della decomposizione in primi di n, per ogni i = 1, 2, ..., r. Senza essere lesivi di generalità, possiamo sempre supporre: p<sub>1</sub> < p<sub>2</sub> < ... < p<sub>n</sub>. Dacché: 2<sup>n</sup> + 1 ≡ 0 (mod. n), allora in particolare: 2<sup>n</sup> + 1 ≡ 0 (mod. p<sub>1</sub>); per cui, stante il teorema 2: n ≡ 0 (mod. g), avendo posto g := gss(p<sub>1</sub>, 2). Ora, dev\'essere g > 1, poiché: 2<sup>1</sup> - 1 = 1 < p<sub>1</sub>. <!-- BBCode Start --><I>Ergo</I><!-- BBCode End -->, per il teorema fondamentale dell\'Aritmetica, esistono (univocamente determinati) s > 0 numeri primi q<sub>1</sub>, q<sub>2</sub>, ..., q<sub>s</sub>, tutti minori di p<sub>1</sub>, essendo 1 < g < n, tali che sia:
<BR>
<BR>g = q<sub>1</sub><sup>b<sub>1</sub></sup> * q<sub>2</sub><sup>b<sub>2</sub></sup> * ... * q<sub>s</sub><sup>b<sub>s</sub></sup>
<BR>
<BR>ove b<sub>k</sub> > 0 è la molteplicità con cui il generico q<sub>i</sub> interviene nella relazione precedente quale fattore della decomposizione in primi di g, per ogni k = 1, 2, ..., s. Ne fa seguito che, per ogni k = 1, 2, ..., s: n ≡ 0 (mod. q<sub>k</sub>), ovvero:
<BR>
<BR> p<sub>1</sub><sup>a<sub>1</sub></sup> * p<sub>2</sub><sup>a<sub>2</sub></sup> * ... * p<sub>r</sub><sup>a<sub>r</sub></sup> ≡ 0 (mod. q<sub>k</sub>)
<BR>
<BR>e quindi: p<sub>i</sub> ≡ 0 (mod. q<sub>k</sub>), per un qualche i = 1, 2, ..., r. Ciò che palesemente è assurdo! Difatti, come si è detto, p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>r</sub> sono numeri primi tali che: p<sub>1</sub> < p<sub>2</sub> < ... < p<sub>r</sub> e a sua volta: 1 < q<sub>k</sub> < p<sub>1</sub>, perciocché q<sub>k</sub> non può certo dividere alcuno dei p<sub>i</sub> ≡ 0 (mod. q<sub>k</sub>), qualunque sia i = 1, 2, ..., r. L\'assurdo, insorto dall\'aver supposto che un n > 2 tale che fosse: 2<sup>n</sup> + 1 ≡ 0 (mod. q<sub>k</sub>), induce conversamente a concludere che il caso ii) non conduce ad alcuna soluzione, q.e.d.
<BR>
<BR>Dunque, riassumendo quanto stabilito sino a questo punto, possiamo concludere (trascendo come sempre dalle restrizioni imposte dalla traccia originaria del problema posto da Talpuz) che:
<BR>i) n = 1, n = 2 sono soluzioni banali al problema;
<BR>ii) ogni altra eventuale soluzione, ad eccezione del caso singolare n = 6, si presenta nella forma n = 2h, ove: 2<sup>2h - 1</sup> + 1 ≡ 0 (mod. h) ed h è un intero positivo di valenza dispari che sia altresì prodotto delle potenze (eventualmente a esponente unitario) di almeno due primi distinti, tutti comunque della forma 8k + 1 (con k ≥ 2, dacché per k = 0 e k = 1 non si ottengono dei numeri primi) o della forma 8k + 3 (con k ≥ 0). Onde evincerne che, in tal caso, dovrà essere necessariamente n ≥ 66.
<BR>
<BR>P.S.: in effetti, alla luce del risultato di cui ho inteso qui discutere, mi sarei potuto risparmiare molte delle considerazioni con cui ho letteralmente <!-- BBCode Start --><I>riempito</I><!-- BBCode End --> le pagine precedenti di questo medesimo topic, ma mi piace pensare che comunque qualcuno le abbia trovate, se non istruttive, quantomeno un valido spunto di riflessione...<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 18-01-2004 23:37 ]
<center>Le cose cambiano... e i sentimenti pure...</center>
Bloccato