All three theorems mentioned in the heading of this post are important tools for dealing with congruences and they are really useful for practical computing, because they can simplify your terms significantly if certain conditions are met. Nevertheless, we start with a notion of the Euler’s function.
- Drapal, parts 2.4, 2.5, and 2.11
- Wiki posts on Fermat’s theorem, Wilson’s theorem and Euler’s function
First, we define the Euler’s function . Let be a natural number. Then the Euler’s function of , denoted by , is defined as the number of such that and , and we also define . So, the Euler’s function actually determines the amount of numbers that are less than and relatively prime to a given number. Therefore, is always equal to .
Hmmm, what is the value of , where is a prime number? Obviously, for every such that . Hence of course, every natural number that is less than is coprime to . This gives us that .
How to compute in general? Well, suppose that is the prime decomposition of . It can be proved that
How is related to any of the above theorems? The answer is as follows:
Euler’s theorem: Let be two coprime naturals. Then mod
Immediate consequence of the Euler’s theorem and of the fact that is the following Fermat’s little theorem:
Fermat’s little theorem: Let be a prime number and suppose that . Then mod .
This theorem of Fermat can be used for primality testing in the so called Fermat primality test. Read this post to find out more!
Another quite immediate consequence of the Euler’s theorem is Wilson’s factorial theorem:
- If is a prime number, then mod .
- If is composed, then mod .
- For we have mod .
We already know that the Euler’s function is closely related to properties of groups and . We mentioned that . The following group theory proposition yields another appearance of .
Let . Then the following statements are equivalent:
- A map is an isomorphism.
Moreover, is a (commutative) field if and only if is prime.
Note that a subgroup of generated by an element is of the form .
Where is the Euler’s function in the previous preposition? Well, my friend, take a look: The equivalence between the second point and the third one actually says that So, has generators.
Let . Then .
Prove that if , then .
Since is a prime number and , we can use the Fermat’s theorem to receive mod . We are almost done, because , so mod .
Show that .
If we rewrite the assumption, we get that mod . It follows that mod . Moreover, it also means that the order of in is exactly : gives us that , but is dividable only by some powers of , so for some . Now, the assumption tells us that , so .
We also see that , because otherwise , a contradiction. The Fermat’s theorem then gives us that mod . Consequently, .
What is the prime decomposition of ? Easy-peasy, . Using the formula from the beginning, .
Compute mod .
Although we cannot use the Fermat’s theorem (), we can still use the Euler’s theorem, since . We have , thus mod . So,
Compute mod .
Determine the last digit of .
Is there any element of such that ? If yes, find them all.