Il test di Pepin (1877): 2^n + 1 è primo sse...
Essendo $q$ un intero $\ge 2$, mostrare che $n = 2^q + 1$ è primo se e soltanto se $3^{(n-1)/2} \equiv -1 $ mod n.
Risposte
Allora, sia $g$ una radice primitva di $p$, primo. Vale la congruenza $(p-1)!-=g*g^2*...*g^(p-1)-=g^(p(p-1)/2)-=g^((p-1)/2)$ mod $p$, in quanto la successione dei minimi residui positivi $g^k$ mod $p$, $k=1,2,...,p-1$ è una permutazione degli interi $1,2,3,...,p-1$.
Quindi $g^(p-1)-=1$ mod $p$, per il teorema di Fermat, cioè $g^((p-1)/2)-=-1$ mod $p$, e, sostituendo nella congruenza iniziale, si ha $(p-1)!-=-1$ mod $p$, che, per il teorema di Wilson, è vera solo se $p$ è primo. Dunque, se vale $g^((p-1)/2)-=-1$ mod $p$, allora $p$ è primo.
Nel nostro caso, $g=3$ e $p=2^q+1$: $3^(2^(q-1))-=-1$ mod $2^q+1$. A questo punto, basta dimostrare che $3$ è una radice primitiva di tutti i primi della forma $2^q+1$, con $q>=2$, ma non saprei come fare..
Quindi $g^(p-1)-=1$ mod $p$, per il teorema di Fermat, cioè $g^((p-1)/2)-=-1$ mod $p$, e, sostituendo nella congruenza iniziale, si ha $(p-1)!-=-1$ mod $p$, che, per il teorema di Wilson, è vera solo se $p$ è primo. Dunque, se vale $g^((p-1)/2)-=-1$ mod $p$, allora $p$ è primo.
Nel nostro caso, $g=3$ e $p=2^q+1$: $3^(2^(q-1))-=-1$ mod $2^q+1$. A questo punto, basta dimostrare che $3$ è una radice primitiva di tutti i primi della forma $2^q+1$, con $q>=2$, ma non saprei come fare..
"Crook":
Allora, sia $g$ una radice primitva di $p$, primo. Vale la congruenza $(p-1)!-=g*g^2*...*g^(p-1)-=g^(p(p-1)/2)-=g^((p-1)/2)$ mod $p$, in quanto la successione dei minimi residui positivi $g^k$ mod $p$, $k=1,2,...,p-1$ è una permutazione degli interi $1,2,3,...,p-1$.
Quindi $g^(p-1)-=1$ mod $p$, per il teorema di Fermat, cioè $g^((p-1)/2)-=-1$ mod $p$, e, sostituendo nella congruenza iniziale, si ha $(p-1)!-=-1$ mod $p$, che, per il teorema di Wilson, è vera solo se $p$ è primo. Dunque, se vale $g^((p-1)/2)-=-1$ mod $p$, allora $p$ è primo.
A me dà tanto l'impressione che il tuo sia un argomento perfettamente circolare, Crook: per concludere che $g^{(p-1)/2} \equiv -1 $mod p, stai già supponendo che $p$ sia un numero primo, poiché altrimenti non avresti che l'insieme ${1, g, ..., g^{p-2}}$ percorre un sistema completo di residui minimi mod p. Sbaglio?
A me sembra che $g^((p-1)/2)-=-1$ mod $p$ sia equivalente a $(p-1)!-=-1$ mod $p$, che vale solo per $p$ primo, quindi pensavo non facesse differenza la supposizione iniziale, perché volevo mostrare il "sse" della prima congruenza.
"Crook":
A me sembra che $g^((p-1)/2)-=-1$ mod $p$ sia equivalente a $(p-1)!-=-1$ mod $p$, che vale solo per $p$ primo, quindi pensavo non facesse differenza la supposizione iniziale, perché volevo mostrare il "sse" della prima congruenza.
Perciò vuoi dirmi che, se $p$ è un intero positivo dispari ed esiste $g \in ZZ$ tale che $g^{(p-1)/2} \equiv -1$ mod p, allora $p$ è primo? Se è così, provalo!
Se $p$ è un intero e ha una radice primitiva $g$, allora la sequenza $g,g^2,...,g^(p-1)$ è una permutazione degli interi nell'intervallo $[1,p-1]$, solo se $p$ è primo. Quindi $(p-1)!-=g*g^2*...*g^(p-1)-=g^((p-1)/2) (modp)$, solo se $p$ è primo. E dato che $(p-1)!-=-1(modp)$, allora anche $g^((p-1)/2)-=-1(modp)$, (ancora) solo se $p$ è primo. O non ho ancora evitato l'argomento circolare?
"Crook":
Se $p$ è un intero e ha una radice primitiva $g$, allora la sequenza $g,g^2,...,g^(p-1)$ è una permutazione degli interi nell'intervallo $[1,p-1]$, solo se $p$ è primo.
Sì, vero.
"Crook":
Quindi $(p-1)!-=g*g^2*...*g^(p-1)-=g^((p-1)/2) (modp)$, solo se $p$ è primo.
Anche questo è vero, ma non capisco come tu possa farlo dipendere in toto dal precedente, senza coinvolgere già a questo punto il teorema di Wilson. Nel senso... Se $g$ è una radice primitiva mod p e $p \ge 3$ è primo, allora $-1 \equiv (p-1)! \equiv g^{(p-1)/2}$ mod p, e fine. Se $p \ge 3$ è composto e dispari, allora $0 \equiv (p-1)! \ne g^{(p-1)/2}$ mod p, posto che $g$ sia un intero qualsiasi coprimo con $p$. In entrambi i casi, sto usando il fatto che i) $(p-1)! \equiv -1$ mod p sse $p$ è primo; ii) $(p-1)! \equiv 0$ mod p, se $p \ge 6$ è composto. I.e., il teorema di Wilson!
Purtroppo non ho tempo per leggere attentamente la tua risposta, comunque provo a buttare due parole su un altro approccio:
Per il criterio di Lucas, $n$ è primo sse esiste un qualche $b$ primo con $n$ tale che:
$b^(n-1)-=1$ mod n, e
$b^((n-1)/p)!-=1$ mod n,
per ogni divisore primo $p$ di $n-1$.
Se $2^n+1$ è primo, allora $n=2^m$, per qualche $m in NN$, quindi consideriamo solo i numeri di Fermat.
Ora osserviamo che $(F_i,3)=1$, poiché dal teorema di Fermat $2^(2k)-=1$ mod 3, quindi $2^(2k)!-=-1$ mod 3.
Essendo che l'unico divisore primo di $F_i$ è $2$, abbiamo che $F_i$ è primo sse esiste un qualche $b$ primo con $F_i$, tale che:
$b^(F_i-1)-=1$ mod $F_i$, e
$b^((F_i-1)/2)!-=1$ mod $F_i$.
Nel caso in cui $b=3$, possiamo riassumere le ultimi due condizioni in una sola, cioè in $3^((F_i-1)/2)-=-1$ mod $F_i$, perché la prima implica la seconda e viceversa.
Le mie difficoltà sono di dimostrare il "sse" per il $3$..
EDIT: con $!-=$ intendo non congruente.
Per il criterio di Lucas, $n$ è primo sse esiste un qualche $b$ primo con $n$ tale che:
$b^(n-1)-=1$ mod n, e
$b^((n-1)/p)!-=1$ mod n,
per ogni divisore primo $p$ di $n-1$.
Se $2^n+1$ è primo, allora $n=2^m$, per qualche $m in NN$, quindi consideriamo solo i numeri di Fermat.
Ora osserviamo che $(F_i,3)=1$, poiché dal teorema di Fermat $2^(2k)-=1$ mod 3, quindi $2^(2k)!-=-1$ mod 3.
Essendo che l'unico divisore primo di $F_i$ è $2$, abbiamo che $F_i$ è primo sse esiste un qualche $b$ primo con $F_i$, tale che:
$b^(F_i-1)-=1$ mod $F_i$, e
$b^((F_i-1)/2)!-=1$ mod $F_i$.
Nel caso in cui $b=3$, possiamo riassumere le ultimi due condizioni in una sola, cioè in $3^((F_i-1)/2)-=-1$ mod $F_i$, perché la prima implica la seconda e viceversa.
Le mie difficoltà sono di dimostrare il "sse" per il $3$..
EDIT: con $!-=$ intendo non congruente.
Devo dedurre che non c'è niente di buono? D'accordo, non è completa, per "causa" del 3...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo