Burt Kaliski Jr. (@modulomathy)
3/13/12 7:42 AM
#math trivia for #March13: #73 as a modulus gives square roots to -1. Solve x^2+1 = 0 (mod 73) where x is an integer between 0 and 72.
One way to find the square root is by trial and error, looking for the smallest integer congruent to 72 modulo 73 that is a square:
– 72 — no
– 145 — no
– 218 — no
– 291 — no
– 364 — no
– 437 — no
– 510 — no
– 583 — no
– 656 — no
– 729 — yes, 27^2
So, one of the square roots of 72 modulo 73 is 27. The other is -27, which in modular terms is 73-27 = 46. We can check this as follows:
46^2 mod 73 = 2116 mod 73 = (28*73+72) mod 73
Another approach to finding the square root that may be more efficient is to take advantage of Fermat’s Little Theorem, which states that if p is a prime and x is not divisible by p, then
x^(p-1) mod p = 1 .
If x is a random number modulo p, then with some probability, x^((p-1)/2) mod p will be -1. When p-1 is divisible by 4 as in the present example, x^((p-1)/4) mod p will then be a square root of -1. Concretely, we have (p-1)/4 = 18, so let’s compute x^18 mod 73 for small values of x and see what happens when we enumerate successive powers up to 18:
— x = 2: 2, 4, 8, 16, 32, 64, 55, 37, 1, 2, 4, 8, 16, 32, 64, 55, 37, 1
— x = 3: 3, 9, 27, 8, 24, 72, 69, 64, 46, 65, 49, 1, 3, 9, 27, 8, 24, 72
For x = 2, the successive powers go directly to 1; the square root is not exposed. For x = 3, the successive powers go to -1, so we still don’t have a square root of -1 at the 18th power. However, the 9th power will give is what we’re looking for: the square root of -1 mod 73 is 46, just as above. (So is 27, which is the 3rd power here; note that the 6th is also -1.)
modulomathy.com 