||Computer Science II
||Roots in Modulo Arithmetic
Data Abstraction, Class Hierarchies and Inheritance, Virtual Functions, Friends, Reusable Code, ...
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.
- 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.
- 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).
- 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.