# solvable congruent

• Apr 20th 2012, 06:48 AM
alexandrabel90
solvable congruent
How do you proof that -1 congruent to x^4 mod p is solvable iff (-1)^(p-1/d) is congruent to 1 mod p where d= gcd(4,p-1)?

i was trying to use euler theorem that (-1)^(p-1) is congruent to 1 mod p then how else can i continue?
• Apr 20th 2012, 05:39 PM
Sylvia104
Re: Solvable congruent
I take it you want $\displaystyle p$ to be prime. The case $\displaystyle p=2$ is trivial, so we'll assume $\displaystyle p$ to be odd. Then $\displaystyle d=2$ if $\displaystyle p\equiv3\mod4$ and $\displaystyle d=4$ if $\displaystyle p\equiv1\mod 4.$

If $\displaystyle p\equiv3\mod4$ then by Euler's criterion $\displaystyle \left(\frac{-1}p\right)=(-1)^{\frac{p-1}2}=-1.$ In this case $\displaystyle x$ is not a quadratic residue modulo $\displaystyle p$ (and so it certainly can't be a quartic residue modulo $\displaystyle p);$ we also have $\displaystyle (-1)^{\frac{p-1}d}=(-1)^{\frac{p-1}2}=-1\not\equiv1\mod p.$

Consider $\displaystyle p\equiv1\mod4.$

(i) Suppose $\displaystyle x^4\equiv-1\mod p.$ As $\displaystyle d=4$ in this case, $\displaystyle -1\equiv x^d\mod p$ $\displaystyle \implies$ $\displaystyle (-1)^{\frac{p-1}d}\equiv x^{p-1}\mod p\equiv1\mod p$ by Fermat's little theorem.

(ii) Conversely suppose $\displaystyle (-1)^{\frac{p-1}d}=(-1)^{\frac{p-1}4}\equiv1\mod p.$ Then $\displaystyle \frac{p-1}4$ is even, i.e. $\displaystyle 8\mid p-1.$ Let $\displaystyle k$ be a primitive root $\displaystyle \mod p$ and set $\displaystyle x=k^{\frac{p-1}8}.$ Then $\displaystyle x^8\equiv1\mod p$ $\displaystyle \implies$ $\displaystyle p$ divides $\displaystyle x^8-1=\left(x^4+1\right)\left(x^4-1\right).$ But $\displaystyle p$ cannot divide $\displaystyle x^4-1$ otherwise $\displaystyle k^{\frac{p-1}2}\equiv1\mod p$ which would contradict the fact that, as a primitive root, $\displaystyle k$ has order $\displaystyle p-1$ in the multiplicative group of the integers modulo $\displaystyle p.$ Hence $\displaystyle p$ divides $\displaystyle x^4+1$ and we are done.