Euler's theorem is a generalization of Fermat's little theorem and states that
where is Euler's function and .
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:
Calculate in .
- VELEBIL, Jiří. Diskrétní matematika : Text k přednášce. Praha : [s.n.], 2007. 193 p.