Lets say we have $\mathbb{Z}_p$, where p is prime.

For each element(x) we have two squares(y) so that $y^2=x$

ie if $p=7$ for $x=4$ we have $y_1=2,y_2=7-2=5,y=\pm2 $

ok, lets have $\mathbb{Z}_{3*5},\mathbb{Z}_{15}$

for $x=4$, $2$ and $15-2=13$ are trivial, besides all squareroots will be $y_1=2 y_2=-2=13$, also $y_3=7$, $y_4=-7=8$

it is easily observable that if $s$ is amount of factors in group order, amount of square roots is $2^s$. it is also mentionable here - s is amount of distinct primes, group of order $3^3=27$ has two squareroots same way as $3^2=9$. For 4 it will always be 2 and $order-2$ for trivial reasons.

any other proof, besides empirical induction, that $2^s$ is amount of squares for group of order, where $s$ is amount of distinct prime factors of?

Supporting module in Sage

  • The Chinese remainder theorem is your friend. Basically what happens is that modulo an (odd) prime power you get two square roots (or none). CRT then tells you that the total number of square roots is $2^s$ (or none). The prime $2$, if a factor of your modulus, complicates matters further. – Jyrki Lahtonen Mar 25 '15 at 20:25
  • In this thread there are worked out examples finding square roots of $-1$ modulo an odd integer. Two things are explained there: A) if you know a square root modulo $p^k$, you can "lift" it to a square root modulo $p^{k+1}$. B) the CRT technique of combining the square roots modulo different prime powers. – Jyrki Lahtonen Mar 25 '15 at 20:34

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.