20-CS-472 Design and Analysis of Algorithms 2 Winter 2011
Fermat's Little Theorem

Complexity classes, Divide-and-Conquer, Dynamic Programming, Greedy, Matroids, more

Instructions: This applet shows that ap-1 = 1 mod p, where p is prime and 0< a< p. Enter a number in box a: and a number in box p:. Click Doit to see the result of ap-1 mod p which is displayed in the unlabeled box. Click Next to increment a by 1 (mod p) and repeat the calculation.

Observe:

  1. What happens when p is non-prime?
  2. What happens when a > p?