Conditions Under Which we can Solve x2 ≡ a (mod n)
Suppose that we know that a given number, a, is a perfect square (mod n), where n = pq. Can we solve
x2 ≡ a (mod n)? In this video, we claim that we can under a certain condition, and make a further observation about the number of solutions.
An Example: n = 77
In this video, we look at an example where n = 77, and using the CRT, determine how many roots there are, and find them all.
Supplementary Discussion
We now have seen that we have a way to determine whether or not the number a is a perfect square: the CRT and Euler’s criterion can be used to determine whether or not it is.
[previous] [next]