Problema al contrario: n | 2^n+1

[darkcrystal]

Determinare per quali valori di n si ha $ n | 2^n+1 $

Per gli stagisti: W sempre il P.P.P!
Davide

[piever]

Secondo il teorema di Fermat, questo funziona in tutti i primi p in cui 1 mod p=-2 mod p ma l'unico primo con queste caratteristiche è 3. Quindi si escludono tutti i numeri che contengono almeno un fattore primo diverso da 3: quindi per esclusione i numeri che cerchi sono le potenze di 3 (il fatto che funzioni con le potenze di 3 diverse da 3 non lo so dimostrare, ma sono giunto a questa conclusione per il fatto che non funziona con tutti gli altri numeri e che con 9 e 27 il conto torna).
"Dimostrazione" antimatematica come sempre, ma spero giusta almeno stavolta.
Come si dimostra che, essendo n una potenza di 3, $ n | 2^n+1 $?

[darkcrystal]

Per induzione...
se $ 2^{3^k}\equiv-1 (3^k) $, vuol dire che $ 2^{3^k}=b\cdot3^k-1 $ per qualche b.
Allora si ha, elevando al cubo, che $ (b\cdot3^k-1)^3=b^3\cdot3^{3k}-3\cdot b^2\cdot3^{2k}+b\cdot3^{k+1}-1 $
Che dovrebbe essere congruo a -1 modulo $ 3^{k+1} $, poichè questo divide tutti i primi 3 termini.

Sempre sperando di non dire sciocchezze,
Davide
Ciao!

[darkcrystal]

Tra l'altro, piever, non sono convinto al 100% della tua soluzione... quello che dici è perfettamente vero se n è primo, ma se non lo è?
Forse sono solo io che non capisco... comunque ci dovrebbe essere un'altra soluzione... però sul fatto che 3 debba comparire nella scomposizione hai ragione:
Prendiamo p, il più piccolo primo che divide n.
Abbiamo che
$ 2^n\equiv-1 (\mod n) $
quindi, a maggior ragione,
$ 2^n\equiv-1 (\mod p) $
Elevando al quadrato
$ 2^{2n}\equiv1 (\mod p) $
Quindi l'ordine moltiplicativo di 2 modulo p divide 2n, ma non n; inoltre divide (p-1).
Poichè $ \gcd((p-1),2n)=2 $ l'ordine moltiplicativo è 1 o 2.
Non può essere 1, perchè altrimenti dividerebbe n. Quindi è 2, e quindi il primo p è 3.
Sempre sperando di non dire sciocchezze, visto che oggi non sono molto lucido,
Davide

[frengo]

questo problema non ha una soluzione:
i valori di n sono infiniti,e non seguono un criterio logico(o meglio,sì,ma non è certo una cosa che può essere chiesta alle olimpiadi della matematica).
dopo aver scoperto che il più piccolo primo è 3, si va avanti scoprendo il secondo(29),poi il terzo,ecc.
alle IMO 2000 il quinto problema era di determinare che esiste un numero tale che $ n|2^n+1 $ e che sia il prodotto di 2000 numeri primi distinti...
comunque rilancio con un altro problema,simile:

determinare tutti gli n tali che
$ n^2|2^n+1 $

ciao ciao

[piever]

Grazie per la dimostrazione, in effetti potevo arrivarci da solo, ma vabbè.
Non penso che possano esserci n diversi da potenze di 3.
Il mio ragionamento si basa sul fatto che n deve contenere 3 (fin qui siamo d'accordo) ma se n non fosse una potenza di 3 dovrebbe avere all'interno almeno un numero primo p diverso da 3.
$ p | 2^{3p}+1 $ è impossibile. Infatti se $ p | 2^{3p}+1 $ vuol dire anche che $ p | 2^p+1 $ ma l'unico primo con questa caratteristica è 3.
Mi accorgo ora dal messaggio di frengo che la mia teoria è confutata dai fatti e in effetti l'ultimo passaggio non è dimostrabile
Grazie per avermi corretto.

[frengo]

ehm...credo di non essere stato chiaro:
le soluzioni sono ben più di tutte le potenze di 3,infinite e imprevedibili.
esempio:prova $ 3^2\cdot 19 $:

$ 3^2\cdot 19|3^3\cdot 19=513=2^9+1|2^{9\cdot 19}+1 $