# Thread: Solving a congruence modulo p

1. ## Solving a congruence modulo p

$\displaystyle p \equiv 2 (mod 3)$ and $\displaystyle p-1 = 4q$ with p and q distinct primes.

Show that:

$\displaystyle 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??

2. ## Re: Solving a congruence modulo p

Since $\displaystyle p\equiv1\mod4,$ quadratic reciprocity gives $\displaystyle 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 $\displaystyle \left(\frac**\right)$ denotes the Legendre symbol). In other words $\displaystyle 3$ is not a quadratic residue modulo $\displaystyle p;$ by Euler’s criterion, $\displaystyle -1 = \left(\frac3p\right) \equiv 3^{\frac{p-1}2} = 3^{2q}\mod p.$