8.10: Euler's Theorem

The RSA cryptosystem examined in the next section, and other current schemes for encoding secret messages, involve computing remainders of numbers raised to large powers. A basic fact about remainders of powers follows from a theorem due to Euler about congruences.

Definition \(\PageIndex{1}\)

For \(n > 0\), define ¹¹

\[\nonumber \phi (n) ::= \text{the number of integers in } [0..n), \text{ that are relatively prime to } n.\]

This function \(\phi\) is known as Euler’s \(\phi\) function.¹²

For example, \(\phi (7) = 6\) because all 6 positive numbers in \([0..7)\) are relatively prime to the prime number 7. Only 0 is not relatively prime to 7. Also, \(\phi (12) = 4\) since 1, 5, 7, and 11 are the only numbers in \([0..12)\) that are relatively prime to 12.

More generally, if \(p\) is prime, then \(\phi (p) = p - 1\) since every positive number in \([0..p)\) is relatively prime to \(p\). When \(n\) is composite, however, the \(\phi\) function gets a little complicated. We’ll get back to it in the next section.

Euler’s Theorem is traditionally stated in terms of congruence:

Theorem

(Euler’s Theorem). If n and k are relatively prime, then

\[\label{8.10.1} k^{\phi (n)} \equiv 1 \pmod n \]

The Riemann Hypothesis

The formula for the sum of an infinite geometric series says:

\[\nonumber 1+x+x^{2}+x^{3}+\cdots=\dfrac{1}{1-x}\]

Substituting \(x=\frac{1}{2^{s}}, x=\frac{1}{3^{s}}, x=\frac{1}{5^{s}}\), and so on for each prime number gives a sequence of equations:

\[\begin{aligned}
1+\frac{1}{2^{s}}+\frac{1}{2^{2 s}}+\frac{1}{2^{3 s}}+\cdots &=\frac{1}{1-1 / 2^{s}} \\
1+\frac{1}{3^{s}}+\frac{1}{3^{2 s}}+\frac{1}{3^{3 s}}+\cdots &=\frac{1}{1-1 / 3^{s}} \\
1+\frac{1}{5^{s}}+\frac{1}{5^{2 s}}+\frac{1}{5^{3 s}}+\cdots &=\frac{1}{1-1 / 5^{s}} \\ & etc.
\end{aligned}\]

Multiplying together all the left sides and all the right sides gives:

\[\nonumber \sum_{n=1}^{\infty} \dfrac{1}{n^{s}}=\prod_{p \in \text { primes }}(\dfrac{1}{1-1 / p^{s}})\]

The sum on the left is obtained by multiplying out all the infinite series and applying the Fundamental Theorem of Arithmetic. For example, the term \(1/300^s\) in the sum is obtained by multiplying \(1/2^{2s}\) from the first equation by \(1/e^{s}\) in the second and \(1/5^{2s}\) in the third. Riemann noted that every prime appears in the expression on the right. So he proposed to learn about the primes by studying the equivalent, but simpler expression on the left. In particular, he regarded \(s\) as a complex number and the left side as a function, \(\xi (s)\). Riemann found that the distribution of primes is related to values of \(s\) for which \(\xi (s) = 0\), which led to his famous conjecture:

Definition 8.9.6.

The Riemann Hypothesis: Every nontrivial zero of the zeta function \(\xi (s)\) lies on the line \(s = 1/2 + ci\) in the complex plane.

A proof would immediately imply, among other things, a strong form of the Prime Number Theorem.

Researchers continue to work intensely to settle this conjecture, as they have for over a century. It is another of the Millennium Problems whose solver will earn $1,000,000 from the Clay Institute.

Things get simpler when we rephrase Euler’s Theorem in terms of \(\mathbb{Z}_n\).

Definition \(\PageIndex{2}\)

Let \(\mathbb{Z}_{n}^{*}\) be the integers in \((0 . . n)\), that are relatively prime to \(n\): ¹³

\[\label{8.10.2} \mathbb{Z}_{n}^{*}::=\{k \in(0 . . n) \mid \text{gcd}(k, n)=1\}. \]

Consequently,

\[\nonumber \phi(n)=|\mathbb{Z}_{n}^{*}|\]

Theorem \(\PageIndex{3}\)

(Euler's Theorem for \(\mathbb{Z}_{n}\) ). For all \(k \in \mathbb{Z}_{n}^{*}\),

\[\label{8.10.3} \k^{\phi(n)}=1(\mathbb{Z}_{n})\]

Theorem 8.10.3 will follow from two very easy lemmas.

Let's start by observing that \(\mathbb{Z}_{n}^{*}\) is closed under multiplication in \(\mathbb{Z}_{n}\):

Lemma 8.10.4. If \(j, k \in \mathbb{Z}_{n}^{*}\), then \(j \cdot n k \in \mathbb{Z}_{n}^{*}\).

There are lots of easy ways to prove this (see Problem 8.67).

Definition \(\PageIndex{5}\)

For any element \(k\) and subset \(S\) of \(\mathbb{Z}_{n}\), let

\[\nonumber k S::=\{k \cdot _n s \mid s \in S\}\]

Lemma 8.10.6. If \(k \in \mathbb{Z}_{n}^{*}\) and \(S \subseteq \mathbb{Z}_{n}\), then

\[\nonumber |k S|=|S|.\]

Proof. Since \(k \in \mathbb{Z}_{n}^{*}\), by Theorem 8.9.5. it is cancellable. Therefore,

\[\nonumber [k s=k t\left(\mathbb{Z}_{n}\right)] \quad \text { implies } \quad s=t.\]

So mulitplying by \(k\) in \(\mathbb{Z}_{n}\) maps all the elements of \(S\) to distinct elements of \(k S\), which implies \(S\) and \(k S\) are the same size. \(\blacksquare\)

Corollary 8.10.7. If \(k \in \mathbb{Z}_{n}^{*}\)

\[\nonumber k \mathbb{Z}_{n}^{*}=\mathbb{Z}_{n}^{*}.\]

Proof. A product of elements in \(\mathbb{Z}_{n}^{*}\) remains in \(\mathbb{Z}_{n}^{*}\) by Lemma 8.10.4. So if \(k \in \mathbb{Z}_{n}^{*}\), then \(k \mathbb{Z}_{n}^{*} \subseteq \mathbb{Z}_{n}^{*}\). But by Lemma 8.10.6, \(k \mathbb{Z}_{n}^{*}\) and \(\mathbb{Z}_{n}^{*}\) are the same size, so they must be equal. \(\quad \blacksquare\)

Proof. (of Euler's Theorem 8.10.3 for \(\mathbb{Z}_{n}\))

Let

\[\nonumber P::=k_{1} \cdot k_{2} \cdots k_{\phi(n)}(\mathbb{Z}_{n})\]

be the product in \(\mathbb{Z}_{n}\) of all the numbers in \(\mathbb{Z}_{n}^{*}\). Let

\[\nonumber Q::=(k \cdot k_{1}) \cdot (k \cdot k_{2} ) \cdots (k \cdot k_{\phi(n)}) (\mathbb{Z}_{n})\]

for some \(k \in \mathbb{Z}_{n}^{*}\). Factoring out \(k\) 's immediately gives

\[\nonumber Q=k^{\phi(n)} P(\mathbb{Z}_{n}).\]

But \(Q\) is the same as the product of the numbers in \(k \mathbb{Z}_{n}^{*}\), and \(k \mathbb{Z}_{n}^{*}=\mathbb{Z}_{n}^{*}\), so we realize that \(Q\) is the product of the same numbers as \(P\), just in a different order. Altogether, we have

\[\nonumber P=Q=k^{\phi(n)} P(\mathbb{Z}_{n}).\]

Furthermore, \(P \in \mathbb{Z}_{n}^{*}\) by Lemma 8.10.4, and so it can be cancelled from both sides of this equality, giving

\[\nonumber 1=k^{\phi(n)}(\mathbb{Z}_{n}).\]

Euler’s theorem offers another way to find inverses modulo \(n\): if \(k\) is relatively prime to \(n\), then \(k^{\phi (n) - 1}\) is a \(\mathbb{Z}_{n}\)-inverse of \(k\), and we can compute this power of \(k\) efficiently using fast exponentiation. However, this approach requires computing \(\phi(n)\). In the next section, we’ll show that computing \(\phi(n)\) is easy if we know the prime factorization of \(n\). But we know that finding the factors of \(n\) is generally hard to do when \(n\) is large, and so the Pulverizer remains the best approach to computing inverses modulo \(n\).

Fermat’s Little Theorem

For the record, we mention a famous special case of Euler’s Theorem that was known to Fermat a century earlier.

Corollary 8.10.8 (Fermat’s Little Theorem). Suppose \(p\) is a prime and \(k\) is not a multiple of \(p\). Then:

\[\nonumber k^{p-1} \equiv 1 \pmod p\]

Computing Euler’s \(\phi\) Function

RSA works using arithmetic modulo the product of two large primes, so we begin with an elementary explanation of how to compute \(\phi(pq)\) for primes \(p\) and \(q\):

Lemma 8.10.9.

\[\nonumber \phi(pq) = (p - 1)(q - 1)\]

for primes \(p \neq q\).

Proof. Since \(p\) and \(q\) are prime, any number that is not relatively prime to \(pq\) must be a multiple of \(p\) or a multiple of \(q\). Among the \(pq\) numbers in \([0..pq)\), there are precisely \(q\) multiples of \(p\) and \(p\) multiples of \(q\). Since \(p\) and \(q\) are relatively prime, the only number in \([0..pq)\) that is a multiple of both \(p\) and \(q\) is 0. Hence, there are \(p + q - 1\) numbers in \([0..pq)\) that are not relatively prime to \(n\). This means that

\[\begin{aligned} \phi(pq) &= pq - (p + q - 1) \\ &= (p - 1)(q - 1). \end{aligned}\]

as claimed.¹⁴ \(\quad \blacksquare\)

The following theorem provides a way to calculate \(\phi(n)\) for arbitrary \(n\).

Theorem \(\PageIndex{10}\)

(a) If \(p\) is a prime, then \(\phi(p^{k})=p^{k}-p^{k-1}\) for \(k \geq 1\).
(b) If \(a\) and \(b\) are relatively prime, then \(\phi(a b)=\phi(a) \phi(b)\).

Here's an example of using Theorem 8.10.10. to compute \(\phi(300)\) :

\[\begin{aligned}
\phi(300) &=\phi\left(2^{2} \cdot 3 \cdot 5^{2}\right) & & \\
&=\phi\left(2^{2}\right) \cdot \phi(3) \cdot \phi\left(5^{2}\right) & & \text { (by Theorem 8.10.10.(b)) } \\
&=\left(2^{2}-2^{1}\right)\left(3^{1}-3^{0}\right)\left(5^{2}-5^{1}\right) & & \text { (by Theorem 8.10.10.(a)) } \\
&=80.
\end{aligned}\]

Note that Lemma 8.10.9 also follows as a special case of Theorem 8.10.10.(b), since we know that \(\phi(p)=p-1\) for any prime, \(p\).

To prove Theorem 8.10.10.(a), notice that every \(p\)th number among the \(p^{k}\) numbers in \([0 . . p^{k})\) is divisible by \(p\), and only these are divisible by \(p\). So \(1 / p\) of these numbers are divisible by \(p\) and the remaining ones are not. That is,

\[\nonumber \phi(p^{k})=p^{k}-(1 / p) p^{k}=p^{k}-p^{k-1}.\]

We'll leave a proof of Theorem 8.10.10.(b) to Problem 8.62.

As a consequence of Theorem 8.10.10, we have

Corollary 8.10.11. For any number \(n\), if \(p_1, p_2, \ldots, p_j\) are the (distinct) prime factors of \(n\), then

\[\nonumber \phi(n) = n (1 - \dfrac{1}{p_1}) (1 - \dfrac{1}{p_2}) \cdots (1 - \dfrac{1}{p_j}).\]

We’ll give another proof of Corollary 8.10.11 based on rules for counting in Section 14.9.5.

 

¹¹Since 0 is not relatively prime to anything, \(\phi (n)\) could equivalently be defined using the interval \((0..n)\) instead of \([0..n)\).

¹²Some texts call it Euler’s totient function.

¹³Some other texts use the notation \(n^*\) for \(\mathbb{Z}_{n}^{*}\).

¹⁴This proof previews a kind of counting argument that we will explore more fully in Part III.