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.