5.2: Euler's Method

Definition 5.2

A complete set of residues \(C\) modulo \(b\) is a set \(b\) integers in \(\mathbb{Z}\), such \(C\) has exactly one integer in each congruence class (modulo \(b\)).

A reduced set of residues \(R\) modulo \(b\) is a set \(\varphi (b)\) integers in \(\mathbb{Z}\), such \(R\) has exactly one integer in each class congruent to \(p \in \{1, \cdots b-1\}\) (modulo \(b\)) such that \(p\) is relatively prime to \(b\).

Lemma 5.3

Suppose \(\gcd (a,b) = 1\). If the numbers \(\{x_{i}\}\) form a complete set of residues modulo \(b\) (a reduced set of residues modulo \(b\)), then \(\{ax_{i}\}\) is a complete set of residues modulo \(b\) (\(a\) reduced set of residues modulo \(b\)).

Proof

Let \(\{x_{i}\}\) be a complete set of residues modulo \(b\). Then the \(b\) numbers \(\{ax_{i}\}\) form complete set of residues unless two of them are congruent. But that is impossible by Theorem 2.7.

Let \(\{x_{i}\}\) be a reduced set of residues modulo \(b\). Then, as above, no two of the \(\varphi (b)\) numbers \(\{ax_{i}\}\) are congruent modulo \(b\). Furthermore, Lemma 2.18 implies that if \(\gcd (a,b) = 1\) and \(\gcd (x_{i}, b) = 1\), then \(\gcd (ax_{i}, b) = 1\). Thus the set \(\{ax_{i}\}\) is a reduced set of residues modulo \(b\).

Theorem 5.4 (Euler)

Let \(a\) and \(b\) greater than \(0\) and \(\gcd(a, b) = 1\). Then \(a^{\varphi (b)} = _{b} 1\), where \(\varphi\) denotes Euler’s phi or totient function (Definition 4.9).

Proof

Let \(\{x_{i}\}_{i=1}^{\varphi(b)}\) be a reduced set of residues module \(b\). Then by Lemma 5.3, \(\{ax_{i}\}_{i=1}^{\varphi(b)}\) be a reduced set of residues module \(b\). Because multiplication is commutative, we got

\[\prod_{i=1}^{\varphi (b)} x_{i} = b \prod_{i=1}^{\varphi (b)} ax_{i} = _{b} a^{\varphi(b)} \prod_{i=1}^{\varphi (b)} x_{i} \nonumber\]

Since \(\gcd (x_{i}, a) = 1\), Lemma 2.18 implies that \(\gcd (\prod_{i=1}^{\varphi (b)} x_{i}, a) = 1\). The cancelation theorem applied to the equality between the first and third terms proves the result.

Euler's theorem says that \(\varphi (b)\) is a multiple of \(\mbox{Ord}_{b}^{\times} (a)\). But it does not say what multiple. In fact, in practice, that question is difficult to decide. It is of theoretical importance to decide when the two are equal.

Definition 5.5

Let \(a\) and \(b\) positive intgers with \(\gcd (a,b) = 1\). If \(\mbox{Ord}_{b}^{\times} a = \varphi (b)\), then \(a\) is called a primitive root of \(b\) (or a primitive root module \(b\)).

For example, the smallest integer \(k\) for which \(3^k = _{7} 1\) is \(6\). Since \(\varphi (7) = 6\), we see that \(3\) is primitive root of \(7\). Since multiplication is well-defined in \(\mathbb{Z}_{7}\), it follows that \((3+7k)^{6} = _{7} 3^{6} = _{7} 1\). Thus, \(\{\cdots, -4, 3, 10, \cdots \}\) are all primitive roots of \(7\). The only other non-congruent primitive root of \(7\) is \(5\). Not all numbers have primitive roots. For instance, \(8\) has none.

This has interesting connection with day-to-day arithmetic, namely the expression of rational numbers in base \(10\).

Proposition 5.6

Let \(a\) and \(n\) greater than \(0\) and \(\gcd (a,n) = \gcd (10,n) = 1\). The decimal expansion of \(\frac{a}{n}\) is non-terminating and eventually periodic with a period \(p\), where \((1) p = \mbox{Ord}_{n}^{\times} (10)\) and \((2) p | \varphi (n)\).

Proof

The proof proceeds by excuting a long division, each step of which uses the division algorithm, Start by reducing \(a\) module \(n\) and call the result \(r_{0}\).

\[a = n q_{0}+r_{0} \nonumber\]

where \(r_{0} \in \{0, \cdots, n-1\}\). Lemma 3.1 implies that \(\gcd (a,n) = \gcd (r_{0}, n) = 1\). So in particular, \(r_{0} \ne 0\). The integer part of \(\frac{a}{n}\) is \(q_{0}\). The next step of the long division is:

\[10 r_{0} = nq_{1}+r_{1} \nonumber\]

where again we choose \(r_{1} \in \{0, \cdots, n-1\}\).

Note that \(0 \le 10r_{0} < 10n\) and so \(q_{1} \in \{0,\cdots 9\}\). We now record the first digit “after the decimal point” of the decimal expansion: \(q_{1}\). By Lemma 3.1, we have \(\gcd (10r_{0}, n) = \gcd(r_{1}, n)\). In turn, this implies via Lemma 2.18 that \(\gcd (r_{0}, n) = \gcd (r_{1}, n)\). And again, we see that \(r_{1} \ne 0\).

The process now repeats itself.

\[\underbrace{10(10r_{0}-nq_{1})}_{r_{1}} = nq_{2}+r_{2} \nonumber\]

and we record the second digit after the decimal dot, \(q_{2} \in \{0, \cdots 9\}\). By the same reasoning, \(\gcd (r_{2}, n) = 1\) and so \(r_{2} \ne 0\). One continues and proves by induction that \(\gcd (r_{i}, n) = 1\). In particular, \(r_{i} \ne 0\), so the expansion does not terminate.

Since the remainders \(r_{i}\) are in \(\{1, \cdots n-1\}\), the sequence must be eventually periodic with (least positive) period \(p\). At that point, we have

\[10^{k+p}r_{0} = _{n} 10^{k}r_{0} \nonumber\]

By Theorem 2.7, we can cancel the common factors \(10^k\) and \(r_{0}\), and we obtain that \(10^{p} = _{n} 1\). Since \(p\) is the least such (positive) number, we have proved part (1). Part (2) follows directly from Euler’s Theorem.

Of course, this proposition easily generalizes to computations in any other base \(b\). As an en example, we mention that if \(\gcd (a, n) = 1\) and \(b\) is a primitive root of \(n\), then the expansion of \(\frac{a}{b}\) has period \(\varphi (n)\).

The next result is an immediate consequence of Euler’s theorem. It follows by setting \(y = x+k \varphi (b)\). It has important applications in cryptography.

Corollary 5.7

Let \(a\) and \(b\) be coprime with \(b \ge 0\). If \(x = _{\varphi (b)} y\), then \(a^{x} = _{b} a^y\).