Infiniti [tex]n[/tex]

[Sky]

Salve, vi propongo questo problema perché vorrei un giudizio sul mio stile dimostrativo (e perché non riesco a giustificare bene un passaggio).

Dimostrare che dato [tex]p[/tex] primo esistono infiniti [tex]n[/tex] interi positivi tali che [tex]p|2^n-n[/tex]

Soluzione:

Testo nascosto:

Dimostriamo innanzitutto che per ogni [tex]p[/tex] primo esiste almeno un [tex]n[/tex] che rispetta le condizioni.

Definiamo [tex]a_n[/tex] e [tex]b_n[/tex] tali che:
[tex]a_n=2^n[/tex] e
[tex]b_n=n[/tex]

Lemma: [tex]a_n[/tex] è periodica modulo [tex]p[/tex] con periodo [tex]t=ord_p(2)[/tex]

Dimostrazione: per divisione euclidea possiamo scrivere:

[tex]n=mt+k[/tex] con [tex]m,k \in \mathbb{N}[/tex] e [tex]0 \leq k \leq t-1[/tex]

Quindi:

[tex]2^n=2^{mt+k}=(2^t)^m 2^k \equiv 1^m 2^k \equiv 2^k \pmod{p}[/tex]

Da cui la tesi.

Ora, il periodo di [tex]b_n \pmod{p}[/tex] è chiaramente [tex]p[/tex], inoltre, visto che [tex]t|p-1[/tex], [tex]gcd(t,p)=1[/tex]
Visto che [tex]a_n[/tex] e [tex]b_n[/tex] hanno periodi coprimi e [tex]b_n[/tex] assume tutti i valori tra [tex]0[/tex] e [tex]p-1[/tex], esiste un j tale che [tex]a_j=b_j[/tex], quindi tale che [tex]2^j \equiv j \pmod{p}[/tex].

Dimostriamo ora che se esiste un [tex]n[/tex] che rispetta le condizioni, ne esistono infiniti.

Dato [tex]n[/tex] tale che [tex]2^n \equiv n \pmod{p}[/tex], consideriamo [tex]m=n+p(p-1)[/tex].
Allora:

[tex]2^m=2^{n+p(p-1)}=2^n(2^{p-1})^p \equiv 2^n \pmod{p}[/tex]

per il piccolo teorema di Fermat.
Inoltre,

[tex]m=n+p(p-1) \equiv n \pmod{p}[/tex]

Quindi:

[tex]2^m \equiv m \pmod{p}[/tex]

Quindi se esiste un [tex]n[/tex] che rispetta le condizioni, esiste un [tex]m[/tex] strettamente più grande che le rispetta anch' esso, quindi ne esistono infiniti.

EDIT: Errore nel testo

[ElPaso98]

Possibilie ci sia un errore nel testo del problema? Non capisco che fine fa quel [tex]p[/tex]

[Sky]

Ho sbagliato a scrivere corretto ora.

[ElPaso98]

Comunque se il problema è equivalente a [tex]2^n \equiv n \pmod p[/tex] credo sia sufficiente porre [tex]n=(kp-1)(p-1)[/tex] con k naturale.
Edit: errore di battitura

[Sky]

Ouch, è vero, comunque la soluzione torna? (Non riuscivo a spiegare meglio la parte dei periodi coprimi)

[ElPaso98]

Premetto che non sono di certo la persona più adatta a commentare soluzioni altrui, però ci provo.
Una cosa che mi ha fatto un po' incasinare è stata la tua scelta di sostiture [tex]2^n[/tex] e [tex]n[/tex] con nomi di [tex]a_n, b_n[/tex]; non so quanto questa cosa faccia simpatia ad un correttore considerato che comunque si tratta di variabili (mi riferisco a [tex]2^n , n[/tex]) che si scrivono in un attimo e non risultano fastidiose nella lettura o nella stesura di una soluzione, detto ciò l'unico appunto che faccio alla dimostrazione in sè riguarda il momento in cui affermi che il periodo di [tex]2[/tex] è sempre [tex]p[/tex], con questo credo tu affermi che [tex]2^p \equiv 1 \pmod p[/tex] ma non è così, e più in generale non è vero che un numero intero ([tex]2[/tex] nel nostro caso) coprimo con [tex]p[/tex], elevato a opportune potenze prende tutte le classi di resto di [tex]p[/tex] (che giustamente sono [tex]p-1[/tex]), questa è una proprietà di alcuni interi particolari detti generatori modulo p di cui forse hai sentito parlare, comunque ti consiglio di aspettare il parere di qualcuno più attendibile, spero di averti aiutato

[Sky]

Infatti il periodo di [tex]2^n \mod p[/tex] è [tex]ord_p2[/tex], non [tex]p[/tex]. Ho usato le due successioni perché non avevo nessun' altra idea per esprimere il concetto dei periodi coprimi, qualche consiglio su questo?

[ElPaso98]

EDIT: puoi spiegare meglio cosa intendi dire quando affermi che il periodo di [tex]b_n[/tex] è [tex]p-1[/tex]?

[Sky]

Se intendi perché è [tex]p[/tex], è perché la successione é [tex]1,2,3,...,p-1,0,1,2...[/tex]