Next: Public Key Cryptography Up: The classical sets of Previous: Systems of congruences   Contents

# Euler's Phi Function

Definition 6.9.1   For , define to be the number of nonnegative integers less than which are coprime to .

. If is prime then and .

Lemma 6.9.2   If with then . is said to be multiplicative.

Let , the reduced set of residues or set of invertible elements. Note that .

Proof. If and then there exists a unique . with and (by theorem (8.1)). Such a is prime to , since it is prime to and to . Conversely, any arises in this way, from the and such that , . Thus as required.

An immediate corollary of this is that for any ,

Theorem 6.9.3 (Fermat-Euler Theorem)   Take and in such that . Then .

Proof. Multiply each residue by and reduce modulo . The numbers thus obtained are prime to and are all distinct. So the new numbers are just in a different order. Therefore

Since we can divide to obtain the result.

Corollary 6.9.4 (Fermat's Little Theorem)   If is a prime and such that then .

Remark 6.9.5 (For algebraists)   This can also be seen as a consequence of Lagrange's Theorem, since is a group under multiplication modulo .

Fermat's Little Theorem can be used to check that is prime. If there exists an coprime to such that then is not prime.

Subsections

Next: Public Key Cryptography Up: The classical sets of Previous: Systems of congruences   Contents
root 2002-06-10