Latest Tweets

Euler’s and Fermat’s theorem

The Euler’s theorem is very useful in the number theory:

Theorem 1. If $a$ and $m$ are relatively prime numbers, then

$$a^{\varphi(m)} \equiv 1 \pmod m.$$

Proof.

Let $m$ be a natural number and let

$$s_1, s_2, \ldots, s_r, \quad r = \varphi(m),$$

be a reduced residue system modulo $m$. Then

$$as_1, as_2, \ldots, as_r$$

is one complete residue system modulo $m$. This means that each of the numbers $s_1, s_2, \ldots, s_r$ is congruent with exactly one of the numbers $as_1, as_2, \ldots, as_r$, however, not necessarily in the same order. Therefore, there exist numbers $i_1, i_2, \ldots, i_r \in \{1, 2, \ldots, r \}$ such that

$$as_1 \equiv s_{i_1} \pmod m,$$

$$as_2 \equiv s_{i_2} \pmod m,$$

$$\vdots$$

$$as_r \equiv s_{i_r} \pmod m$$

is valid.

By multiplying the above congruences, we obtain:

$$a^rs_1s_2 \cdots s_r \equiv s_{i_1} s_{i_2} \cdots s_{i_r} \pmod m.$$

Since $r = \varphi (m)$ and $s_1s_2 \cdots s_m = s_{i_1}s_{i_2} \cdots s_{i_r}$ (this numbers are the same numbers as above, but multiplied in another order), that follows:

$$a^{\varphi(m)} \equiv 1 \pmod m,$$

and the statement of a theorem is proven.

From the Euler’s theorem follows the Fermat’s Little theorem:

Theorem 2.  If $p$ is a prime number and the number $a$ is relatively prime with $p$, then

$$a^{p -1} \equiv 1 \pmod p.$$

The statement  of a theorem directly follows from the fact that for every prime number $p$, $\varphi(p) = p-1$ is valid.

The converse of the Fermat’s Little theorem is not valid, that is, if $a$ and $p$ are relatively prime numbers and if $a^{p-1} \equiv 1 \pmod m$, then not follows that the number $p$ is a prime number.

We will show now how to use Euler’s and Fermat’s Little theorem.

Example 1. Find the remainder when the number $119^{120}$ is divided by $9$.

Solution.

Since $119 \equiv 2 \pmod{9}$, that $119^{221} \equiv 2^{221} \pmod 9$. By the Euler’s theorem now follows

$$2^{\varphi(9)} \equiv 1 \pmod 9.$$

Since $\varphi(9) = 6$, we have

$$2^{6} \equiv 1 \pmod 9.$$

By the remainder theorem, the number $221$ we write as $221 = 36 \cdot 6 + 5$, so $2^{221} = (2^6)^{36} \cdot 2^5$. Now it follows

$$2^{221} = (2^6)^{36} \cdot 2^5 \equiv \pmod 9.$$

Since $2^{6} \equiv 1 \pmod 9$, now it follows

$$2^{221} \equiv 1^{36} \cdot 2^5 \pmod 9,$$

that is,

$$2^{221} \equiv 32 \equiv 5 \pmod 9.$$

Therefore, the requested remainder is $5$.

Example 2. Find the remainder when the number $2^{30}$ is divided by $13$.

Solution.

By the Fermat’s Little theorem, we have:

$$2^{12} \equiv 1 \pmod{13}.$$

After squaring the above congruence, we obtain:

$$2^{24} \equiv 1 \pmod{13}.$$

Now this congruence we multiply with the congruence $2^6 \equiv -1 \pmod{13}$, and we obtain:

$$2^{30} \equiv -1 \pmod{13}.$$

Since $-1 \equiv 12 \pmod{13}$, that by substituting it in the previous congruence we obtain:

$$2^{30} \equiv 12 \pmod{13}.$$

Therefore, the requested remainder is $12$.

In the end, let’s just note how the Fermat’s Little theorem can be used to test weather a “large” natural number is a prime or composite number.

Let $m$ be some natural number. We choose some number $a$ (it is good to choose a prime number) that is not a divisor of $m$. Usually we choose $2, 3$ or $5$.

If

$$a^{m-1} \equiv 1 \pmod m$$

is valid, then the number $m$ is a prime number. Otherwise, $m$ is a composite number.