Computing

28 ◾ Computing

In 1736 Leonhard Paul Euler (1707–1783) was the rst to document a

proof of Fermat’s little theorem. Here we give a proof of Fermat’s little

theorem using modern algebra [2].

Proof

First, we dene Euler’s totient function (also called the Euler phi-function).

For n within positive natural numbers, φ(n) is the number of integers k

coprime to n such that 1 ≤ k ≤ n. is is equivalent to p – 1 if n is a prime

p. Let Z

n

* = {k | k is a positive integer coprime to n and less than n}, and

let the multiplication of any pair of elements of Z

n

* be the multiplication

of the elements modulo n. en Z

n

* is a multiplicative group of order ...