3
$\begingroup$

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$, i.e., if $p=7$ for $x=4$ we have $y_1=2,y_2=7-2=5,y=\pm2 $.

Let's 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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Mar 25, 2015 at 20:25
  • $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Mar 25, 2015 at 20:34

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .