Finding the square roots of $1$ modulo $52$ and $9$ modulo $52$.

148 Views Asked by At

I can do both of these by eye and with a bit of trial and error, knowing 1 for example will have square roots 1 and 51 and then the others will be roughly in the middle of the elements in $\mathbb{Z}_{52}$ so typing into my calculator $25^2$ and $27^2$ both give me a remainder $1$ modulo $52$ so I know these are all the square roots of 1. I then did the same thing for the square roots of 9 and got 3, 49, 23 and 29 by using the same method as I did for 1.

I know if it was modulo a prime then the only roots of 1 are $p$ and $p-1$ and if we have modulo $2^e$ then to find the four roots you would have $2^e$ and then the other square roots of 1 would be one above and one below. But what about when $n$ is composite like this 52, I wondered if there was a more methodical way like the other cases to follow other than just by eye?

1

There are 1 best solutions below

1
On

Yes, there is: use the Chinese remainder theorem: \begin{align} \mathbf Z/52\mathbf Z&\longrightarrow \mathbf Z/4\mathbf Z\times\mathbf Z/13\mathbf Z\\ x\bmod52&\longmapsto(x\bmod4,x\bmod13) \end{align} is an isomorphism. If $4u+13v=1$ is a Bézout's relation between $4$ and $13$, the inverse isomorphism is given by $$(x\bmod 4, y\bmod 13)\longmapsto 4uy+13vx\bmod52.$$ Thus all you have to do is computing the square roots mod. $4$ and mod. $13$, then deducing the elements in $\mathbf Z/52\mathbf Z$ which correspond to all pairs of square roots mod. $4$ and mod. $13$.