# Euler's Totient Theorem

**Euler's Totient Theorem** is a theorem closely related to his function of the same name.

## Contents

## Theorem

Let be Euler's totient function. 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 that is prime. For this reason it is known as Euler's generalization and Fermat-Euler as well.

## Proof

Consider the set of numbers {} (mod m) such that the elements of the set are the numbers relatively prime to each other. It will now be proved that this set is the same as the set {} (mod m) where . All elements of are relatively prime to so if all elements of are distinct, then has the same elements as . This means that (mod m) => (mod m) => (mod m) as desired.