Project 6, 2015 Research Experience for Teachers Project 4, 2016
Roots in Modulo Arithmetic

Secret Key, Public Key, Hash Algorithms, Protocols, Authentication, Integrity, Confidentiality, Availability

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:
 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. If p is a prime number and n is p-1 then all the numbers in the bottom row are 1. This is a demonstration of Fermat's Little Theorem. For example, set p to 19 and n to 18. Try a non-prime for p, such as 14, and try all values of n from 1 to p. For p non-prime, and any n less than p, why must some number in the bottom row be different from 1?