Euler's theorem is a generalization of Fermat's little theorem and states that

where is *Euler's function* and .

## Euler's function

Euler's function , where , is defined as number of integers less than , which are *relatively prime* to (i.e. their greatest common divisor is equal to ). is defined as .

## Computing Euler's function

To compute Euler's function of , we factorize to its prime factors and plug them into the following formula:

## Proof of Euler's theorem

For each number greater than and less or equal to , which is relatively prime to and has an inverse in , there exist according to Euler's function exactly invertible elements. Let's denote them as .

For every two elements and , where and are integers from set , it holds that:

because , and are defined as numbers relatively prime to .

Now suppose we have two following sequences:

The sequences contain identical numbers (regardless their order). So let's factor out from the first sequence:

Finally we can cancel out the whole second sequence and we get the desired expression:

## Example

Calculate in .

## Sources

- VELEBIL, Jiří. Diskrétní matematika : Text k přednášce. Praha : [s.n.], 2007. 193 p.