# primitive root of a prime

• Dec 13th 2009, 06:55 PM
jimmyjimmyjimmy
primitive root of a prime
Hi,

let p be a prime congruent to 1 mod 3
let a be a prim root of p
suppose a is not congruent to 0 mod p

show that there is no solution x for the congruence x^2 = a mod p

i know by some theorem about primitive roots of primes that x^2 - a = 0 mod p has at most 2 solutions

i also know that the order of a modulo p is phi(p) = p -1, and so a^(p - 1) = 1 mod p, and p - 1 = 3k for some k, since p = 1 mod 3.

anyone have any hints? i started also by noting that (x^2)^(p - 1) = a^(p -1) mod p, and tried factoring some stuff with that, that is after assuming for a contradiction that in fact there is a solution x
• Dec 13th 2009, 08:39 PM
Bruno J.
$\displaystyle x^{p-1}\equiv 1 \mod p$ holds for all $\displaystyle x$ relatively prime to $\displaystyle p$, not just for primitive roots. So if $\displaystyle x^2 \equiv a \mod p$, what do you get if you raise both side to the power $\displaystyle (p-1)/2$?