﻿ Euler's theorem

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.