How do I solve Euler's theorem

Theorems of Euler and Fermat


We once dealt with problems of form mod concerned, for example with the question of what the last decimal place of a power is ( mod ) or similar problems ( mod ). The trick was trying to get the potency in this way to disassemble that mod (or e.g. alternatively mod ... just something simple). However, the decomposition is not always easy (e.g. mod ). In this section we will learn a few tricks to find out which powers are congruent in certain cases mod are.


  1. Two numbers and are called coprime if and only if
  2. If mod and , then also applies mod

Euler's phi function

We define Euler's phi function as follows:


Euler's theorem


Proof: video

Note from student Flo1860: Additional evidence - which is missing in the video (on: PH Heidelberg / Number Theory / Theorems of Euler and Fermat - SoSe2012) - is it really missing? The discussion is open! :-)

In general, of course, now it's interesting: How do you get it now just out?

For a prime number is it still easy: . But what if is not a prime number? But before we think about it, we can quickly write down Fermat's Little Theorem. As a special case, this results directly from Euler's theorem:

Fermat's Little Theorem

For and prime numbers With applies: mod

Theorems on Euler's phi function

So, now ... we decide for different cases:

  1. If prim, then
  2. Error during parsing (PNG conversion failed. Please check the correct installation of LaTeX and dvipng (or dvips + gs + convert)): n = \ prod_ {i = 1} ^ r p_i ^ k_i

Evidence: video

One more sentence

For and Prime number applies: mod

Proof: Mmm ... but here we need a case distinction ...

Fermat's great theorem

At this point we should perhaps say a few words about the "great theorem of Fermat" which says:

There is none showing the equation With to solve.

For is available in addition to the well-known solution also infinitely many other solutions in the natural numbers (so-called Pythagorean number triples), as one can easily prove if one uses the numbers for With constructed as follows: , ,

But to prove it for no solution to the equation is not quite as simple as the history of mathematics has shown ...

Additional evidence