20-CS-122 |
Computer Science II |
Spring 2011 |
---|---|---|

Roots in Modulo Arithmetic |

**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, *m ^{n}* mod

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.