Solving a congruence modulo p

**Ant** · April 10th 2012, 04:12 AM

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

**Sylvia104** · April 13th 2012, 11:33 PM

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.$

Thread: Solving a congruence modulo p

LinkBack

Thread Tools

Display

Solving a congruence modulo p

Re: Solving a congruence modulo p

Similar Math Help Forum Discussions

[SOLVED] Modulo and congruence

congruence modulo 2^n

Solving for x in a quadratic congruence modulo problem

congruence modulo m

congruence modulo m

Search Tags