# Euler's Totient Theorem

**Euler's Totient Theorem** is a theorem closely related to his totient function.

## Contents

## Theorem

Let be Euler's totient function. If is a positive integer, is the number of integers in the range which are relatively prime to . If is an integer and is a positive integer relatively prime to ,Then .

## Credit

This theorem is credited to Leonhard Euler. It is a generalization of Fermat's Little Theorem, which specifies it when is prime. For this reason it is also known as Euler's generalization or the Fermat-Euler theorem.

## Proof

Consider the set of numbers {} such that the elements of the set are the numbers relatively prime to . It will now be proved that this set is the same as the set {} where . All elements of are relatively prime to so if all elements of are distinct, then has the same elements as . In other words, each element of is congruent to one of .This means that → → as desired. Note that dividing by is allowed since it is relatively prime to .