# Solving a congruence modulo p

• Apr 10th 2012, 04:12 AM
Ant
Solving a congruence modulo p
$p \equiv 2 (mod 3)$ and $p-1 = 4q$ with p and q distinct primes.

Show that:

$3^{2q} \not\equiv 1 (mod p)$

I've tried various thing but I can't seem to find a contradiction (after assuming 3^(2q) == 1 mod p).

Can anyone point me in the right direction please??
• Apr 13th 2012, 11:33 PM
Sylvia104
Re: Solving a congruence modulo p
Since $p\equiv1\mod4,$ quadratic reciprocity gives $1 = (-1)^{\left(\frac{p-1}2\right)\left(\frac{3-1}2\right)} = \left(\frac p3\right)\left(\frac3p\right) = (-1)\left(\frac3p\right)$ (where $\left(\frac**\right)$ denotes the Legendre symbol). In other words $3$ is not a quadratic residue modulo $p;$ by Euler’s criterion, $-1 = \left(\frac3p\right) \equiv 3^{\frac{p-1}2} = 3^{2q}\mod p.$