Radici primitive

[_luca.barletta]

Mostrare che $7$ è una radice primitiva per tutti i primi $p$ della forma $2^(2^k)+1$, $k in NN$.

[rubik2]

scusate l'ignoranza ma cosa si intende per radice primitiva?

[_luca.barletta]

$g$ si dice radice primitiva modulo $p$ se il più piccolo $k>=1$ tale che $g^(k)-=1 (modp)$ è $k=p-1$

[TomSawyer1]

Prima dimostro che $7$ non è un residuo quadratico $mod F_k=2^{2^k}+1$. Si ha che $F_k\equiv 3,5 (mod 7)$, a seconda della parità di $k$, usando il teorema di Euler. Quindi $(F_k/7)=(3/7)=(5/7)=-1$, con $(*/*)$ il simbolo di Legendre. E per la legge di reciprocità quadratica, siccome $F_k\equiv 1 (mod4)$, abbiamo $(7/F_k)= -1$. Ora sappiamo che $F_k|7^{(F_k-1)/2}+1$, quindi l'ordine di $7$ deve essere una potenza di $2$, cioè $F_k-1$, quindi $7$ è una radice primitiva $mod F_k$.

[_luca.barletta]

@TomSawyer

Ok. Oppure dopo aver mostrato che 7 non è un residuo quadratico modp, potevi osservare che $phi(phi(p))=(p-1)/2$

[TomSawyer1]

Sì, da lì è facile concludere. Tu hai un'altra soluzione, luca? Dimostrare prima che non è un residuo quadratico è abbastanza standard, comunque.

[_luca.barletta]

Il procedimento che ho seguito è quello che ho scritto nell'ultimo post.