1
$\begingroup$

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

2 Answers 2

1

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

  • 0
    @student.llama: corrected2012-10-25
1

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