Math Origins: The Totient Function

Leonhard Euler's totient function, \(\phi (n)\), is an important object in number theory, counting the number of positive integers less than or equal to \(n\) which are relatively prime to \(n\). It has been applied to subjects as diverse as constructible polygons and Internet cryptography. The word totient itself isn't that mysterious: it comes from the Latin word tot, meaning "so many." In a way, it is the answer to the question "Quot?" ("how many"?). In The Words of Mathematics, Steven Schwartzman [Sch] notes that question/answer pairings like Quo/To are common linguistic constructions, similar to the Wh/Th pairing in English ("Where? There. What? That. When? Then."). Beyond that, there are two key questions: (1) how did the notation emerge and develop, and (2) what questions was it originally intended to answer?

Perhaps the best way to begin this investigation is to consult some of the standard mathematical reference works. We begin with Leonard Dickson's 1919 text, History of the Theory of Numbers [Dic]. At the beginning of Chapter V, titled "Euler's Function, Generalizations; Farey Series", Dickson had two things to say about Euler:

[Euler] investigated the number \(\phi (n)\) of positive integers which are relatively prime to \(n\), without then using a functional notation for \(\phi (n)\)... Euler later used \(\pi N\) to denote \(\phi (N)\).

Each of these claims contains a footnote, the first one to Euler's paper "Demonstration of a new method in the theory of arithmetic" ([E271], written in 1758) and the second to "Speculations about certain outstanding properties of numbers" ([E564], written in 1775). So we turn to Euler.

Two Papers From Leonhard Euler

In the "Demonstration," Euler was interested in the proof of Fermat's little theorem. Interestingly, this was not the first time he had published a proof of it—his article "A proof of certain theorems regarding prime numbers" ([E54], written 1736) came first, and that proof relied on mathematical induction. Returning to the subject some 20 years later, Euler expanded on Fermat's original statement with a proof of what is today known as "Euler's theorem" or the "Euler-Fermat theorem."

Along the way, Euler effectively defined the totient function—though he did not use a mathematical notation for it. It is instead described in words, as "the multitude of numbers less than \(N\) which are prime to \(N\)." He then proved some basic facts about it, including that \(\phi(p^m) = p^{m-1}(p-1)\) for prime \(p\) [Theorem 3] and \(\phi(AB) = \phi(A)\phi(B)\) when \(A\) and \(B\) are relatively prime [Theorem 5].

Figure 1. Theorems 3 and 5 from Leonhard Euler's paper, "Theoremata arithmetica nova methodo demonstrate" ("Demonstration of a new method in the theory of arithmetic"), published 1763. Images courtesy of the Euler Archive.

This paper is in Latin, and while Euler used the words totidem ("just as many") and tot ("so many"), they don't seem to hold any special mathematical significance. The primary result of the paper came in Theorem 11, the famed "Euler-Fermat theorem."

Figure 2. The Euler-Fermat theorem, appearing as Theorem 11 in Leonhard Euler's paper, "Theoremata arithmetica nova methodo demonstrate" ("Demonstration of a new method in the theory of arithmetic"), published 1763. Image courtesy of HathiTrust Digital Library.

Again, Euler only described the totient function in words, "\(n\) numerus partium ad \(N\) primarum" ("[let] \(n\) [be] the number of parts that are prime to \(N\)"). Using his terminology, \(N\) and \(x\) are relatively prime, and \(n = \phi(N)\) is the number of positive integers up to \(N\) that are relatively prime to \(N\). Theorem 11 states that \(x^n\) always has a remainder of 1 when it is divided by \(N\). Unlike Euler's earlier proof of Fermat's little theorem, the proof of this theorem relies on the factorization of polynomials.

Specifically, Euler defined \(x^\nu\) as the smallest power of \(x\) that gives remainder 1 when divided by \(N\). Relying on his previous theorem (Theorem 10), he claimed next that either \(\nu = n\) or \(\nu = \frac{n}{m}\) for some integer \(m > 1\); in other words, \(\nu\) divides \(n\). Euler then noted that, for any positive integer \(m\), \(x^\nu-1\) divides \(x^{\nu m}-1\), since 
\[
x^{\nu m}-1 = (x^\nu -1)(x^{\nu(m-1)}+x^{\nu(m-2)}+\cdots+x^\nu+1). \] Since \(n\) must be a multiple of \(\nu\) (here, \(n = \nu m\)) and \(x^\nu-1\) is divisible by \(N\), this factorization means that \(x^n - 1\) is also divisible by \(N\), which completes the proof. Immediately after this, Euler gave Fermat's original theorem as a corollary. All told, this paper lives up to its name—Euler indeed gave a demonstration of his new method for the theory of arithmetic, which produced proofs for many of the properties of the totient function.

In the "Speculations," Euler's goal was to count the number of fractions between 0 and 1 with denominators bounded above by some number \(D\). (Today this set of fractions is called a Farey sequence after the geologist John Farey, though he was almost certainly not the first to describe it.) For example, if \(D = 6\) then the list of fractions is \(\frac{1}{6},\) \(\frac{1}{5},\) \(\frac{1}{4},\) \(\frac{1}{3},\) \(\frac{2}{5},\) \(\frac{1}{2},\) \(\frac{3}{5},\) \(\frac{2}{3},\) \(\frac{3}{4},\) \(\frac{4}{5},\) \(\frac{5}{6}\), giving a total of \(11\) fractions. Since this requires one to count the number of reduced fractions for each possible denominator, the question naturally leads back to the totient function. Having decided by this time to use \(\pi\) to represent it, Euler immediately provided a table of values of \(\pi D\) for \(D\) up to 100.

Figure 3. Euler's definition of the "character" \(\pi\), along with a table of values for \(\pi 1\) to \(\pi 100\). From "Speculationes circa quasdam insignes proprieties numerorum" ("Speculations about certain outstanding properties of numbers"), published 1784. Images courtesy of HathiTrust Digital Library.

Unlike the previous paper, here we see a clearer definition of a mathematical object. In Euler's words, "... let the character \(\pi D\) denote that multitude of numbers which are less than \(D\) and which have no common divisor with it." The reason for the extensive table is to generate a new table, this one consisting of totient sums. For example, given \(D = 6\), we find from the table that \(\pi 1 + \pi 2 + \pi 3 + \pi 4 + \pi 5 + \pi 6 = 0+1+2+2+4+2 = 11\), thus giving the number of reduced fractions between 0 and 1 which have denominator bounded above by 6. Euler compiled a table of totient sums for \(D = 10, 20, \ldots, 90, 100\).

Figure 4. Euler's computation of totient sums for \(D = 10, 20, \ldots, 100\), each of which counts Farey fractions of denominator up to \(D\). From "Speculationes circa quasdam insignes proprieties numerorum" ("Speculations about certain outstanding properties of numbers"), published 1784. Images courtesy of HathiTrust Digital Library.

Euler explained the problem in general terms as follows:

... if \(D\) were the maximum denominator which we would admit, the number of all fractions will plainly be \[=1+2+3+4+\cdots+(D-1) = \frac{DD-D}{2}.\] Then all the fractions should be excluded whose value is \(\frac{1}{2}\), aside from \(\frac{1}{2}\) itself. To this end, \(D\) is divided by 2 and the quotient, either exactly or [rounded down], shall be \(=\alpha\), and it is clear that the number of fractions which are to be excluded is \(=\alpha-1\). Then for the fractions \(\frac{1}{3}\) and \(\frac{2}{3}\), let \(\frac{D}{3} = \beta\), with \(\beta\) denoting the quotient, either exactly or [rounded down], and the number of fractions to be excluded will be \(2(\beta-1) = (\beta-1)\pi 3\). In a similar way if we put \(\frac{D}{4} = \gamma\); then indeed likewise \(\frac{D}{5}=\delta\), \(\frac{D}{6} = \epsilon\), etc., as long as the quotients exceed 1, ... the multitude of fractions which are being searched for which remain will be: \[\frac{DD-D}{2} - (\alpha-1)\pi 2 - (\beta-1)\pi 3 - (\gamma-1)\pi 4 - (\delta-1)\pi 5 - etc.\]

We can see here that Euler's strategy was to begin by counting all fractions up to a given denominator, including equivalent fractions such as \(\frac{1}{2}\) and \(\frac{2}{4}\). The next step, then, would be to remove the duplicates. Euler began with those fractions equivalent to \(\frac{1}{2}\), then those equivalent to \(\frac{1}{3}\) and \(\frac{2}{3}\), and so on.

As an example, take \(D = 6\) again, so that the total number of fractions is \(1+2+3+4+5 = \frac{6^2-6}{2} = 15.\) However, the fractions \(\frac{2}{4}\), \(\frac{3}{6}\), \(\frac{2}{6}\), \(\frac{4}{6}\) all need to be removed. The first two are equal to \(\frac{1}{2}\), and can be counted using Euler's formula as \(\left(\left\lfloor\frac{D}{2}\right\rfloor - 1\right) \pi 2 = 2\cdot 1 = 2\) and \(\left(\left\lfloor\frac{D}{3}\right\rfloor - 1\right) \pi 3 = 1\cdot 2 = 2\), with \(\lfloor\cdot\rfloor\) denoting the greatest integer function. Thus, the total number of distinct fractions is \(15 - 2 - 2 = 11\), as we knew it would be. In modern terminology, we would write Euler's solution as
\[
\frac{D(D-1)}{2} - \sum_{k=2}^{\lfloor D/2\rfloor} \left(\left\lfloor\frac{D}{k}\right\rfloor - 1\right) \phi(k).
\] There is much more in this paper! Ultimately, as Euler noted, "... all of this investigation rests on this point, that, for any given number \(D\), the value of the character \(\pi D\) needs to be found." Accordingly, he repeated many of the same proofs for the totient function that he had in the "Demonstration," and improved on these results by providing a fully general formula for computing it. The interested reader can find more in Jordan Bell's English translation, which is also available via the Euler Archive.

Carl Gauss and J. J. Sylvester

Our next stop is Disquisiones Arithmeticae, Carl Gauss' 1801 number theory textbook. He conceived of this work as a thorough treatment of "higher arithmetic," accomplished by collecting together works of Euclid, Diophantus, Fermat, Euler, Lagrange, and others, and then advancing the field with new results of his own.

Gauss quickly introduced the notation \(\phi N\) to indicate the value of the totient of \(N\). On page 30, at the beginning of problem 38, he wrote:

For brevity we will designate the number of positive numbers which are relatively prime to the given number and smaller than it by the prefix \(\phi\).

This definition is immediately followed by a list of properties, including the general formula from Euler's "Speculations." 

Figure 5. Gauss' general formula in Disquisitiones Arithmeticae for computing the totient function for a given \(A\), taken from Euler's original formula in "Speculationes circa quasdam insignes proprietates numerorum" ("Speculations about certain outstanding properties of numbers"). Gauss cited Euler's work at the bottom. Image courtesy of HathiTrust Digital Library.

Gauss gave the example \(A = 60\) to illustrate the general formula. Since the factorization \(60 = 2^2\cdot 3\cdot 5\) shows that 2, 3, and 5 are the prime divisors of \(60\), the totient may be computed as 
\[
\phi\, 60 = 60 \cdot\frac{2-1}{2}\cdot\frac{3-1}{3}\cdot\frac{5-1}{5} = 60\cdot\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{4}{5} = 16. \] Interestingly, this is the same example Euler gave in the "Demonstration," though to be fair, Gauss gave Euler credit for all of it.

Figure 6. Euler's example from "Theoremata arithmetica nova methodo demonstrata" ("Demonstration of a new method in the theory of arithmetic"), which Gauss repeated in Disquisitiones Arithmeticae (see above). Image courtesy of the Euler Archive.

After working out the basic ideas behind his \(\phi\), Gauss' very next step was to consider a totient sum similar to Euler's. In his own words,

If \(a\), \(a'\), \(a''\) etc. are all the divisors of \(A\) (unity and \(A\) not excluded), it will be \(\phi a + \phi a' + \phi a'' + etc. = A\).

Figure 7. Gauss' totient sum from Disquisitiones Arithmeticae. Image courtesy of HathiTrust Digital Library.

Obviously, this differs from Euler's sum since Gauss only computed the sum over the divisors of \(A\). The outcome, though, is surprisingly elegant: adding the totients of a given number's divisors equals the number itself! Of course, it is Gauss' totient sum, not Euler's, that appears in most number theory textbooks today.

At this point, we should ask why Gauss used the letter \(\phi\) over Euler's \(\pi\). It's quite possible that he chose it for no particular reason. While Gauss introduced \(\phi\) for the totient early in the text, by then he had already used numerous other Greek letters. In the pages leading up to this point (at the beginning of Section II), he used \(\alpha\), \(\beta\), \(\gamma\), \(\kappa\), \(\lambda\), \(\mu\), \(\pi\), \(\delta\), \(\varepsilon\), \(\xi\), \(\nu\), \(\zeta\)—and only after these did he use \(\phi\). It is quite possible that Gauss chose the letter \(\phi\) arbitrarily, though all of the Greek letters used up to this point in the text were in service of larger ideas, and only used in the middle of a larger argument. The use \(\phi\) was new, intended to represent a general concept in number theory, so it is reasonable to wonder what Gauss' reasoning was here, especially if he had a motive for rejecting Euler's \(\pi\) notation. Unfortunately, it is impossible to determine this from the text itself.

The last major change came nearly a century later in J. J. Sylvester's article "On Certain Ternary Cubic-Form Equations," published in the American Journal of Mathematics in 1879. On page 361 Sylvester examined the specific case \(n = p^i\), where \(p\) is prime, and wrote

... \(p^{i-1}(p-1)\) is what is commonly designated as the \(\phi\) function of \(p^i\), the number of numbers less than \(p^i\) and prime to it (the so-called \(\phi\) function of any number I shall here and hereafter designate as its \(\tau\) function and call its Totient).

It is easy to miss the fact that Gauss never referred to his \(\phi\) as a function, but rather a symbol (literally, a "character"). Here we see that while Sylvester did not use today's parenthesis notation, he did refer to the totient as a function. Furthermore, while Sylvester's totient terminology has become commonplace, mathematicians continue to use \(\phi\) instead of \(\tau\). This appears to have happened in spite of Sylvester's strong preference for \(\tau\). In an 1888 paper in Nature, "Note on a Proposed Addition to the Vocabulary of Ordinary Arithmetic", Sylvester said the following about his choice of terminology for the totient function:

Figure 8. J. J. Sylvester's reasoning (p. 589) behind the use of \(\tau\) for the totient function. Image courtesy of the University of Michigan Historical Mathematics Collection.

Along the way, we see here that Sylvester misattributed the use of \(\phi\) to Euler, while Gauss was the true culprit. In the end, as with many things in mathematics, a well-established notation can be difficult to change even when the proposed notation is more sensible.

Conclusion

And this is where the story ends. Returning to our two original questions, we now know that the concept of a totient was due to Euler, the notation selected by Gauss, and the language for it established by Sylvester. We also know that Euler's original goals were very specific—to prove Fermat's little theorem and count fractions on the unit interval—and he proved the basic properties of the phi function as a means to these ends. More generally, we now see that the development of the totient function took quite a long time. Even though Euler's original definition appeared in 1763, it wasn't until 1801 that Gauss introduced the \(\phi\) notation and 1879 that Sylvester used the word totient to describe it—a concept 116 years in the making. Ultimately, while the original phi function was neither phi nor a function, it was undoubtedly Euler's.

References

[Dic] Dickson, Leonard. History of the Theory of Numbers, Volume I: Divisibility and Primality. Washington, DC: Carnegie Institution, 1919. (All three volumes of this text are available in paperback from Dover Publications.)

[E54] Euler, Leonhard. "Theorematum quorundam ad numeros primos spectantium demonstratio" ("A proof of certain theorems regarding prime numbers"). Commentarii academiae scientiarum Petropolitanae 8 (1741), 141–146. Numbered E54 in Eneström's index. The original text, along with an English translation by David Zhao, is available via the Euler Archive.

[E271] Euler, Leonhard. "Theoremata arithmetica nova methodo demonstrata" ("Demonstration of a new method in the theory of arithmetic"). Novi commentarii academiae scientiarum Petropolitanae 8 (1763), pp. 74–104. Numbered E271 in Eneström's index. The original text is available via the Euler Archive.

[E564] Euler, Leonhard. "Speculationes circa quasdam insignes proprietates numerorum" ("Speculations about certain outstanding properties of numbers"). Acta academiae scientarum imperialis Petropolitinae 4 (1784), pp. 18–30. Numbered E564 in Eneström's index. The original text, along with an English translation by Jordan Bell, is available via the Euler Archive.

[Gau] Gauss, Carl. Disquisitiones Arithmeticae. Leipzig: Gerhard Fleischer, 1801. An English translation by Arthur A. Clarke is available from Yale University Press, 1965.

[Sch] Schwartzman, Steven. The Words of Mathematics. Washington, DC: Mathematical Association of America, 1994.

[Syl1] Sylvester, J. J. "On Certain Ternary Cubic-Form Equations." American Journal of Mathematics 2 (1879), 357–393.

[Syl2] Sylvester, J. J. "Note on a Proposed Addition to the Vocabulary of Ordinary Arithmetic." Nature 37 (1888), 152–153.