Fermat’s, Wilson’s and Euler’s theorems, Euler’s function

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.

Sources:

Theory:

First, we define the Euler’s function \varphi. Let n be a natural number. Then the Euler’s function of n, denoted by \varphi(n), is defined as the number of m\in\mathbb{N} such that 1\leq m\leq n-1 and gcd(m,n)=1, and we also define \varphi(1)=1. So, the Euler’s function actually determines the amount of numbers that are less than and relatively prime to a given number. Therefore, \varphi(n) is always equal to |\mathbb{Z}_n|.

Hmmm, what is the value of \varphi(p), where p is a prime number? Obviously, gcd(a,p)=1 for every a such that p\nmid a. Hence of course, every natural number a that is less than p is coprime to p. This gives us that \varphi(p)=p-1.   

How to compute \varphi(n) in general? Well, suppose that n=p_1^{r_1}\cdot\ldots \cdot p_k^{r_k} is the prime decomposition of n. It can be proved that

    \[\varphi(n)=p_1^{r_1-1}\cdot(p_1-1)\cdot\ldots \cdot p_k^{r_k-1}\cdot(p_k-1)\]

    \[=n\cdot\Big(1-\frac{1}{p_1}\Big)\cdot\ldots\cdot\Big(1-\frac{1}{p_k}\Big).\]

How is \varphi(n) related to any of the above theorems? The answer is as follows:

Euler’s theorem: Let gcd(a,n)=1 be two coprime naturals. Then a^{\varphi(n)}\equiv 1 mod n.

Immediate consequence of the Euler’s theorem and of the fact that \varphi(p)=p-1 is the following Fermat’s little theorem:

Fermat’s little theorem: Let p be a prime number and suppose that p\nmid a. Then a^{p-1}\equiv 1 mod p.

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 p is a prime number, then (p-1)!\equiv -1 mod p.
  • If n>4 is composed, then (n-1)!\equiv 0 mod n.
  • For n=4 we have (n-1)!=(4-1)!=3!=6\equiv 2 mod 4.

Properties:

We already know that the Euler’s function is closely related to properties of groups \mathbb{Z} and \mathbb{Z}^*_n. We mentioned that \varphi(n)=|\mathbb{Z}_n|. The following group theory proposition yields another appearance of \varphi.

Let n,a\in\mathbb{N}, n\geq 2, 0<a<n. Then the following statements are equivalent:

  • gcd(a,n)=1;
  • a\cdot\mathbb{Z}_n=\mathbb{Z};
  • a\in\mathbb{Z}^*_n;
  • A map \psi_a:\mathbb{Z}_n\to\mathbb{Z}_n; x\mapsto a\cdot x is an isomorphism.

Moreover, \mathbb{Z}_n is a (commutative) field if and only if n is prime.

Note that a subgroup of \mathbb{Z}_n(+) generated by an element a is of the form \{0\cdot a=0,1\cdot a=a,2\cdot a,\ldots \}=a\cdot\mathbb{Z}_n.  

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 |\{generators\ of\  \mathbb{Z}_n\}|=|\{a|0<a<n; gcd(a,n)=1\}|=\varphi(n). So, \mathbb{Z}_n has \varphi(n) generators.

Let n\in\mathbb{N}. Then n=\sum_{d|n}\varphi(d).

Examples:

Example 1:

Prove that if 17\nmid a, then 17|a^{80}-1.

Solution:

Since 17 is a prime number and 17 \nmid a, we can use the Fermat’s theorem to receive a^{16}\equiv 1 mod 17. We are almost done, because 80=5\cdot 16, so a^{80}=(a^{16})^5\equiv 1^5=1 mod 17.

Example 2:

Show that p|(2^{2^n}+1)\Longrightarrow 2^{n+1}|(p-1).

Solution:

If we rewrite the assumption, we get that 2^{2^n}\equiv -1 mod p. It follows that 2^{2^{n+1}}\equiv 1 mod p. Moreover, it also means that the order of 2 in \mathbb{Z}_p* is exactly 2^{n+1}: 2^{2^{n+1}}\equiv 1 gives us that ord(2)|2^{n+1}, but 2^{n+1} is dividable only by some powers of 2, so ord(2)=2^k for some k\in\{1,\ldots,n+1\}. Now, the assumption tells us that k>n, so k=n+1.

We also see that p\neq 2, because otherwise p\nmid(2^{2^n}+1), a contradiction. The Fermat’s theorem then gives us that 2^{p-1}\equiv 1 mod p. Consequently, 2^{n+1}|(p-1).

Example 3:

Compute \varphi(60).

Solution:

What is the prime decomposition of 60? Easy-peasy, 60=2^2\cdot 3\cdot 5. Using the formula from the beginning, \varphi(60)=2^1\cdot(2-1)\cdot 3^0\cdot(3-1)\cdot 5^0\cdot(5-1)=2\cdot 2\cdot 4=16.

Example 4:

Compute 4^{1001} mod 33.

Solution:

Although we cannot use the Fermat’s theorem (33=3\cdot 11), we can still use the Euler’s theorem, since gcd(4,33)=1. We have \varphi(33)=2\cdot 10=20, thus 4^{20}\equiv 1 mod 33. So,

    \[4^{1001}=4^{1000}\cdot 4=(4^{20})^{50}\cdot 4\equiv 1^{50}\cdot 4=4\ mod\ 33.\]

Problems:

Problem 1:

Compute (10^{10})^{10} mod 7.

Problem 2:

Determine the last digit of 99^{99}.

Problem 3:

Compute \varphi(100).

Problem 4:

Is there any element of G=\mathbb{Z}_{15} such that a\cdot\mathbb{Z}_{15}=\mathbb{Z}_{15}? If yes, find them all.

Leave a Reply

Your email address will not be published. Required fields are marked *