Chapter 7 Euler’s Function

In this short section, we consider one of the most important functions in number theory, namely Euler’s function \(\phi(n)\).

We shall study how to evaluate this function, its basic properties, and see how it can be applied to various problems such as the calculation of large powers and the design and implementation of cipher systems.

Although perhaps not immediately obvious, many of the results in Chapter 6 depended on the simple but important fact that if \(p\) is prime, and \(ab\equiv 0\text{ mod }(p)\), then \(a\equiv 0\) or \(b\equiv 0\text{ mod }(p)\). This makes the arithmetic of \({\mathbb Z}_p\) similar to that of \({\mathbb Z}\), in which the equation \(ab=0\) implies that \(a=0\) or \(b=0\). Unfortunately, this property fails when the modulus is composite. For example, if \(n=12\) then \(3\times4\equiv 0\text{ mod }(12)\) but \(3, 4\not\equiv 0\text{ mod }(12)\).

In Chapter 6 we proved Fermat’s Little Theorem, that if \(p\) is prime then \(a^{p-1}\equiv 1\text{ mod }(p)\) for all integers \(a\not\equiv 0\text{ mod }(p)\).

It would be useful if we had a similar result for composite moduli. However, if \(n=4\) and \(a=3\) then \(a^{n-1}=27\not\equiv 1\text{ mod }(4)\), so the result does not extend to composite values in a straightforward way.

We shall replace \(n-1\) with a different exponent \(e(n)\) such that \(a^{e(n)}\equiv 1\text{ mod }(n)\) for all \(a\) coprime to \(n\).

The simplest function with this property turns out to be Euler’s function \(\phi(n)\), one of the most important functions in number theory.