20-CS-122 Computer Science II Spring 2011
Roots in Modulo Arithmetic

Data Abstraction, Class Hierarchies and Inheritance, Virtual Functions, Friends, Reusable Code, ...

Instructions: Select a number from the drop down menu labeled n and call it n. Select a number from the drop down menu labeled mod and call it p. The set of all integers from 1 to p-1 is displayed in the row labeled m. For each number m in that row, mn mod p is shown in the same column in the row below it.

Observe:

1. If n is 2 and p is a prime number, then only half the numbers from 1 to p-1 appear in the bottom row and each number that does appear, appears twice. Hence, half the numbers have square roots and half have no square roots.
2. If n is 2 and p is a prime number, the numbers in the bottom row form a palindrome (hence square roots are +/- some number).
3. If n is 2 and p is a prime number then 1 shows up only at the extreme left and extreme right of the bottom row. This means the square root of 1 is only +1 mod p and -1 mod p. If p is not a prime, then 1 may show up elsewhere in the bottom row. But this is not always the case. For example, if p is 6,8,9,10,12,14,15,16,18,20,21 then 1 doesn't, does, doesn't, doesn't, does, doesn't, does, does, doesn't, does, does show up elsewhere in the bottom row, repectively. Hence, 1 mod p has only trivial roots of unity if p is a prime number but about half the time has non trivial roots if p is not prime.