*p*is a prime number, then for any integer

*a*, the number

*a*

^{ p}−

*a*is divisible by

*p*

**:**

*a*

^{ p}≡

*a*(mod

*p*).

An alternative version of Fermat's little theorem states that if

*a*is not divisible by

*p*, then the number

*a*

^{ p − 1}− 1 is a multiple of

*p*:

*a*

^{ p − 1}≡ 1 (mod

*p*).

Fermat's little theorem was proved by Euler and can be generalized by Euler's theorem: if

*a*and

*n*are relatively prime, then

*a*

^{ φ(n)}≡ 1 (mod

*n*),

where φ(

*n*) is the number of integers between 1 and

*n*that are relatively prime with

*n*. Euler's theorem form the basis of the RSA encryption system.

## No comments:

## Post a Comment