# Prove that if $ac$ has a square root modulo $p$ and if…

Let $p$ be a prime and suppose $\gcd(a,p)=\gcd(c,p)=1$. Prove that if $ac$ has a square root modulo $p$ and if $a$ has a square root modulo $p$ then $c$ has a square root modulo $p$.

-

So $ac\equiv m^2(\mod p)$ and $a\equiv n^2(\mod p)$. Since $(a,p)=1$, $a^{p-1}\equiv 1(\mod p)$ by Fermat's little theorem. So,

$c\equiv a^{p-2}m^2\pmod{p}\equiv n^{2(p-2)}m^2\pmod{p}\equiv (n^{(p-2)}m)^2\pmod{p}$

-
Just a friendly $\LaTeX$ tip: artofproblemsolving.com/Wiki/index.php/LaTeX:Commands#Mods – JavaMan Oct 25 '12 at 15:25
@JavaMan: Thanks I forgot about these – Alex R. Oct 25 '12 at 15:28
Thanks, should these all be $\equiv$ instead of $=$? – student.llama Oct 25 '12 at 15:51
@student.llama: corrected – Alex R. Oct 25 '12 at 16:00

More is true. Suppose that $\gcd(a,m)=1$, and $a\equiv x^2\pmod{m}$, and $ac\equiv y^2\pmod{m}$.

Since $\gcd(a,m)=1$, we have $\gcd(x,m)=1$. It follows that there is a $z$ such that $zx\equiv 1\pmod{m}$. But then $z^2a\equiv z^2x^2\equiv 1\pmod{m}$.

It follows that $$c\equiv z^2ac\equiv z^2y^2=(zy)^2\pmod{m}.$$

-