Olderrimo ma utile: n²|2^n+1

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

Olderrimo ma utile: n²|2^n+1

Messaggio da salva90 »

Trovare tutti gli interi $ ~n>1 $ tali che $ \displaystyle n^2|2^n+1 $



Troppo istruttivo per non essere postato... :wink:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
Avatar utente
Gufus
Messaggi: 54
Iscritto il: 08 ago 2007, 17:25
Località: BS

Messaggio da Gufus »

Resuscitiamolo! :)
Divido il problema considerando n primo, pari e poi dispari.
Prima di tutto, si cerca qualche $ $n>1$ $ tale che: $ $ 2^n+1=n^2k$ $ per qualche $ $k\geq1$ $
Per n=p primo:
1_Per il teorema di Fermat $ $2^p+1\equiv 3 (p)$ $, mentre $ $p^2k \equiv 0 (p)$ $. Si deve quindi avere che $ $ 3\equiv 0 (p)$ $, il che accade solo se p=3, n=3.
Per n=2t pari:
2_Si ha che $ $2^{2t}+1 \equiv 1 (4)$ $ e che $ ${2t}^2k \equiv 0 (4)$ $ essendo $ $2^{2t}$ $ e $ $(2t)^2$ $ quadrati pari, quindi in questo caso non si hanno n.
Per n=2t+1 dispari:
3_Ci dormo sopra! :D (Intanto un 3 c'è già...)
[url]http://www.aif.it/[/url]
Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein »

Ho provato a scriverla bene, ma diventava una cosa troppo grossa per tex forse perchè nn me la faceva passare: allora scrivo il procedimento.
Prendiamo n monocomposto: n sarà 3. Ora si prova facilmente con l'induzione che $ 2^{3^k}\equiv{ 3^{k+1}-1} \pmod{3^{2k}} $ che ci porta all'unica soluzione intera pos di k+1>=2k ovvero k=1. Ora poniamo n composto: $ n=p_1^{a_1}...p_s^{a_s} $,ponendo p_1<....<p_s ora si consideri che $ 2^{2n} \equiv 1 \pmod {p_1} $ma dato che l'ordine tra 2 e $ p_1 $ è minore di $ p_1 $ si ha che l'ordine è coprimo con tutti i fattori di n: l'ordine è 2: $ p_1=3 $. Ora ragionando modulo $ 3^{2a_1} $ possiamo riscrivere $ 2^{3^{a_1}}+1\equiv 3^{a_1+1} \pmod {3^{2a_1}} $ dunque lo sostituiamo nella potenza generale e chiamando $ j=n/(3^a_1) $ si ha $ 2^n \equiv (3^{a_1+1}-1)^j \pmod {3^{2a_1}} $ ma ora si svolga quel binomio: rimane $ 2^n \equiv 3^{a_1+1}-1 \pmod {3^{2a_1 }} $ il che ci dice che come prima $ a_1=1 $. Ma ora perveniamo all'assurdo passando a $ p_2 $. Per le stesse ragioni di prima si ha che l'ordine è 1,2,3 o 6: possiamo escludere i dispari(perchè altrimenti ce li porteremo in n) e dunque l'unico caso è 6: ma allora l'unica cosa che ci rimane è $ p_2=7 $ però $ 2^3 \equiv 1 \pmod 7 $ dunque sarebbe $ 2^n \equiv 1\pmod 7 $ e $ 2^n \equiv -1\pmod 7 $ ma allora $ 1\equiv -1 \pmod 7 $ ovvero 2=7: assurdo. Dunque l'unica soluzione è 3. E' dunque morto il novello lazzaro? oppure c'è qualche falla pesante:distrazione e/o idiozie di fondo?
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Avatar utente
Algebert
Messaggi: 330
Iscritto il: 31 lug 2008, 20:09
Località: Carrara
Contatta:

Messaggio da Algebert »

Ma sbaglio o è un problema del Naoki Sato :roll: ?
"[i]What is a good Olympiad problem?[/i] Its solution should not require any prerequisites except cleverness. A high scool student should not be at a disadvantage compared to a professional mathematician."
Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein »

Si c'è pure lì : io che lo sto leggendo non lo sapevo, perchè non sono ancora arrivato lì dove dici:sono andato a cercare se effettivamente c'era e ho appena letto la soluzione e sono lieto che è la stessa che ho fatto io :D , anche se non proprio in tempi olimpici : al contrario di gufus io c'ho passato su una buona parte dell'altra notte :D :lol:
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Rispondi