1.6: Diophantine Equations

Volume 2 of Dickson’s History of the Theory of Numbers deals with Diophantine equations. It is as large as the other two volumes combined. It is therefore clear that we shall not cover much of this ground in this section. We shall confine our attention to some problems which are interesting though not of central importance.

One such problem is the Diophantine equation \(n! + 1 = x^2\) mentioned in an earlier section. The problem dates back to 1885 when H. Brochard conjectured that the only solutions are \(4!+1 = 52, 5!+1 = 112\) and \(7!+1 = 712\). About 1895 Ramanujan made the same conjecture but no progress towards a solution of the problem. About 1940 the problem appeared as an elementary (!!) problem in the Monthly. No solutions were offered. However in 1950 an incorrect solution was published and since that time several faulty attempts to prove the result have been made. Again, about 1950 someone took the trouble to check, by brute force, the conjecture up to \(n = 50\). However, earlier, in his book on the theory of numbers Kraitchik already had proved the result up to 5000. As far as we know that is where the problems stands. We shall now give an indication of Kraitchik’s method.

Suppose we want to check \(100! + 1\). Working (mod 103) we have

\(100! (-2)(-2) \equiv -1,\) \(100! + \dfrac{1}{2} \equiv 0\), \(100! + 1 \equiv \dfrac{1}{2} \equiv 52.\)

If now 52 is a nonresidue of 103 we have achieved our goal. Otherwise we could carry out a similar calculation with another \(p > 100\), say 107. Note that \(100! + 1 \equiv 0\) (mod 101) gives no information. Variations of this method can be used to eliminate many numbers wholesale and this is what Kraitchik did. We now outline a proof that \(n! + 1 = x^8\) has only a finite number of solutions. This proof depends on two facts which we have not proved:

(1) Every odd prime divisor of \(x^2 + 1\) is of the form \(4n + 1\);

(2) There are roughly as many primes \(4n + 1\) as \(4n + 3\).

Now \(n! + 1 = x^8\) gives \(n! = x^8 - 1= (x^4 + 1) (x^2 + 1) (x^2 - 1)\); on the right the contribution of primes \(4k + 1\) and \(4k − 1\) is about the same while on the left all the odd prime factors of \((x^4 + 1) (x^2 + 1)\) i.e., about \((n!)^{3/4}\) of the product, are of the form \(4n + 1\).

We now go on to quite a different problem. Has the equation

\(1^n + 2^n + \cdot\cdot\cdot + (m - 1)^n = m^n\)

any solutions in integers other than 1 + 2 = 3? Here are some near solutions:

\(3^2 + 4^2 = 5^2\),

\(3^3 + 4^3 + 5^3 = 6^3\),

\(1^6 + 2^6 + 4^6 + 7^6 + 9^6 + 12^6 + 13^6 + 15^6 + 16^6 + 18^6 + 20^6 + 22^6 + 23^6 = 28^6\).

We now outline a proof that if other solutions exist then \(m > 10^{1000000}\). The rest of this section appeared originally as the paper “On the Diophantine Equation \(1^n + 2^n + \cdot\cdot\cdot + (m - 1)^n = m^n\)," Scripta Mathematica, 19 (1953), pp. 84–88. (Pieter Moree discusses this theorem and proof in “A top hat for Moser’s four mathematical rabbits,” The American Mathematical Monthly, 118 (2011), 364– 370.)

A number of isolated equations expressing the sum of the \(n^{\text{th}}\) powers of integers as an \(n^{\text{th}}\) power of an integer have long been known. Some examples are:

\(3^3 + 4^3 + 5^3 = 6^3\)

\(\sum_{i = 1}^{100} i^4 - 1^4 - 2^4 - 3^4 - 8^4 - 10^4 - 72^4 = 212^4\)

\(1^6 + 2^6 + 4^6 + 5^6 + 6^6 + 7^6 + 9^6 + 12^6 + 13^6 + 15^6 + 16^6 + 18^6 + 20^6 + 21^6 + 22^6 + 23^6 = 28^6\)

Further examples and references to such results are given in [1, p. 682]. On the other hand the only known solution in integers to the equation in the title is the trivial one 1 + 2 = 3. In a letter to the author, P. Erd\(\ddot{o}\)s conjectured that this is the only solution. The object of this note ts to show that if the equation has a solution with \(n > 1\), then \(m > 10^{1000000}\).

Let \(S_n(m)\) denote \(\sum_{i = 1}^{m - 1} i^n\). In what follows we assume

\[S_n(m) \equiv m^n, n > 1.\]

It is possible to examine (6.1) with various moduli and thereby obtain restrictions on \(m\) and \(n\). This is essentially our method, but the moduli are so chosen that we are able to combine the resulting congruences so as to obtain extremely large bounds for \(m\) without laborious computation.

We use the following lemma.

Lemma 1. If \(p\) is a prime and \(\epsilon_n(p)\) is defined by \(\epsilon_n (p) = -1\) when \((p - 1)\ |\ n\) and \(\epsilon_n (p) = 0\) when \((p - 1)\) does not divide \(n\) then

\[S_n(p) \equiv \epsilon_n(p)\ \ \ \ (\text{mod } p).\]

A simple proof of (2) is given in [2, p. 90].

Now suppose \(p\ |\ (m - 1)\), then

\(s_n(m) = \sum_{i = 0}^{\dfrac{m - 1}{p} - 1} \sum_{j = 1}^{p} (j + ip)^n \equiv \dfrac{m - 1}{p} \cdot \epsilon_n (p)\) (mod \(p\)).

On the other hand \(m \equiv 1\) (mod \(p\)) so that by (6.1)

\[\dfrac{m - 1}{p} \cdot \epsilon_n (p) \equiv 1\ \ \ \ (\text{mod } p).\]

Hence \(\epsilon(p) \not\equiv 0\) (mod \(p\)) so that from the definition of \(\epsilon_n (p)\) it follows that \(\epsilon_n(p) = -1\) and

\[p\ |\ (m - 1)\ \ \text{implies } (p - 1)\ |\ n.\]

Thus (6.3) can be put in the form

\[\dfrac{m - 1}{p} + 1 \equiv 0\ \ \ \ (\text{mod } p)\]

or

\[m - 1 + p \equiv 0 \ \ \ \ (\text{mod } p^2).\]

From (6.6) it follows that \(m - 1\) is squarefree. Further, since it is easily checked that \(m - 1 \ne 2\) it follows that \(m - 1\) must have at least one prime divisor, so by (6.4) \(n\) is even.

We now multiply together all congruences of the type (6.5), that is one for each prime dividing \(m − 1\). Since \(m − 1\) is squarefree, the resulting modulus is \(m − 1\). Furthermore, products containing two or more distinct factors of the form \((m − 1)/p\) will be divisible by \(m − 1\). Thus we obtain

\[(m - 1) \sum_{p\ |\ (m - 1)} \dfrac{1}{p} + 1 \equiv 0\ \ \ (\text{mod } m - 1)\]

or

\[\sum_{p\ |\ (m - 1)} \dfrac{1}{p} + \dfrac{1}{m - 1} \equiv 0\ \ \ (\text{mod } 1).\]

The only values of \(m \le 1000\) which satisfy (6.8) are 3, 7, 43.

We proceed to develop three more congruences, similar to (6.8), which when combined with (6.8) lead to the main result. Equation (6.1) can be written in the form

\[S_n (m + 2) = 2m^n + (m + 1)^n.\]

Suppose that \(p\ |\ (m + 1)\). Using (6.2) and the facto that \(n\) is even, we obtain as before

\[p\ |\ (m + 1)\text{ implies } (p - 1)\ |\ n\]

and

\[\dfrac{m + 1}{p} + 2 \equiv 0 \ \ \ \ (\text{mod } p).\]

From (6.11) it follows that no odd prime appears with the exponent greater than one in \(m + 1\). The prime 2 however, requires special attention. If we examine (1) with modulus 4, and we use the fact that n is even, then we find that \(m + 1 \equiv 1\) or 4 (mod 8). Thus \(m + 1\) is odd or contains 2 exactly to the second power. If we assume the second of these possibilities then (6.11) can be put in the form

\[\dfrac{m + 1}{2p} + 1 \equiv 0\ \ \ \ (\text{mod }p).\]

We multiply together all the congruences of the type (12). This modulus then becomes \(\dfrac{m + 1}{2}\). Further any term involving two or more distinct factors \(\dfrac{m + 1}{2p}\) will be divisible by \(\dfrac{m + 1}{2}\) so that on simplification we obtain

\[\sum_{p\ |\ (m + 1)} \dfrac{1}{p} + \dfrac{2}{m + 1} \equiv 0\ \ \ \ (\text{mod } 1).\]

We proceed to find two or more congruences similar to (6.13) without using the assumption that \(m + 1\) is even. Suppose that \(p\ |\ 2m - 1\) and let \(t = \dfrac{1}{2} (\dfrac{2m-1}{p} - 1)\). Clearly \(t\) is an integer and \(m - 1 = tp + \dfrac{p - 1}{2}\). Since \(n\) is even \(a^n = (-a)^n\) so that

\(S_n (\dfrac{p - 1}{2}) \equiv \dfrac{\epsilon_n (p)}{2}\) (mod \(p\)).

Now

\[S_n (m) = \sum_{i = 0}^{t - 1} \sum_{j = 1}^{p - 1} (j + ip)^n + \sum_{i = 1}^{(p - 1)/2} i^n \equiv (t + \dfrac{1}{2}) \epsilon_n (p) \text{ (mod } p).\]

On the other hand \(m^n \equiv 0\) (mod \(p\)) so that (6.1) and (6.14) imply \(\epsilon_n (p) \not\equiv 0\). Hence \(p - 1/n\) and by Fermat's theorem \(m^n \equiv 1\) (mod \(p\)). Thus (6.1) and (6.14) yield \(-(t + \dfrac{1}{2}) \equiv 1\) (mod \(p\)). Replacing \(t\) by its value and simplifying we obtain

\[\dfrac{2m - 1}{p} + 2 \equiv 0\ \ \ \ (\text{mod } p).\]

Since \(2m - 1\) is odd (6.15) implies that \(2m - 1\) is squarefree. Multiplying congruences of type (6.15), one for each of the \(r\) prime divisors of \(2m - 1\) yields

\(2^{r - 1} ((2m - 1) \sum_{p\ |\ (2m - 1)} \dfrac{1}{p} + 2) \equiv 0\) (mod \(2m - 1\)).

Since the modulus is odd this gives

\[\sum_{p\ |\ (2m - 1)} \dfrac{1}{p} + \dfrac{2}{2m - 1} \equiv 0 \ \ \ \ (\text{mod } 1).\]

Finally we obtain a corresponding congruence for primes dividing \(2m + 1\). For this purpose we write (6.1) in the form

\[S_n(m+1) = 2m^n.\]

Suppose \(p\ |\ 2m + 1\). Set \(v = \dfrac{1}{2} (\dfrac{2m + 1}{p} - 1)\). Using again an argument similar to that employed to obtain (6.16) we find that \((p - 1)\ |\ n\) and \(2m + 1\) is squarefree. Finally we obatin

\[\sum_{p\ |\ (2m + 1)} \dfrac{1}{p} + \dfrac{4}{2m + 1} \equiv 0\ \ \ \ (\text{mod } p).\]

We assume again that \(m + 1\) is even so that (6.13) holds. If we now add the left hand sides of (6.8), (6.13), (6.16), and (6.18) we get an integer, at least 4. No prime \(p > 3\) can divide more than one of the numbers \(m - 1\), \(m + 1\), \(2m - 1\), \(2m + 1\). Further, 2 and 3 can divide st most two of these numbers. Hence if \(M = (m - 1) (m + 1)(2m - 1) (2m + 1)\) then

\[\sum_{p\ |\ M} \dfrac{1}{p} + \dfrac{1}{m - 1} + \dfrac{2}{m + 1} + \dfrac{2}{2m - 1} + \dfrac{4}{2m + 1} \ge 4 - \dfrac{1}{2} - \dfrac{1}{3}.\]

We have already seen that the only possibilities for \(m\) with \(m \le 1000\) are 3, 7, and 43. These are easily ruled out by (6.16). Thus (6.19) yields

\[\sum_{p\ |\ M} \dfrac{1}{p} > 3.16.\]

From (6.20) it follows that if \(\sum_{p \le x} \dfrac{1}{p} < 3.16\) then \(M > \prod_{p \le x} p\). We shall prove the following lemma.

lemma 2

\(\sum_{p \le 10^7} \dfrac{1}{p} < 3.16.\)

Proof

By direct computation

\[\sum_{p \le 10^8} \dfrac{1}{p} < 2.18.\]

From Lehmer's table [3] and explicit estimates for \(\pi (x)\) due to Rosser [4] it can easily be checked that for \(10^3 < x < 10^7\)

\[\pi(x) < \dfrac{1.2x}{\log x}.\]

Now in [2, p. 339] it is shown that

\[\sum_{p \le x} \dfrac{1}{p} = \dfrac{\pi (x)}{x} + \int_2^{\pi} \dfrac{\pi (x)}{x} dx.\]

combining (6.21), (6.22) and (6.23) gives the required result.

In [4] it is proved that

\[sum_{p \le x} \log p > (1 - \dfrac{1}{\log x}) x, x < e^{100}.\]

Hence

\(\log M > \log \prod_{p \le 10^7} p = \sum_{p \le 10^7} \log p > (1 - \dfrac{1}{7 \log 10}) 10^7 > (.93) 10^7.\)

Now \(M < 4n^2\) so that

\(\log m > (\dfrac{\log M - \log 4}{2}) > (.231)10^7\)

and \(m > e^{(.231) 10^7} > 10^{1000000}\).

Returning to the case \(m - 1\) odd, we note that in this we cannot use (6.13). Letting \(N = (m - 1) (2m - 1) (2m + 1)\) we get from (6.8), (6.16) and (6.18)

\[\sum_{p\ |\ N} \dfrac{1}{p} + \dfrac{1}{m - 1} + \dfrac{2}{2m - 1} + \dfrac{4}{2m + 1} > 3 - \dfrac{1}{3}.\]

However, since the prime 2 does not appear on the left side (6.25) is actually a stronger condition on m than is (6.19) so that in any case \(m > 10^{1000000}\).

References

[1] L.E. Dickson, History of the Theory of Numbers, vol. 2

[2] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers.

[3] D.H. Lehmer, “List of Prime Numbers from 1 to 10,006,721.”

[4] B. Rosser, “Explicit Bounds for Some Functions of Prime Numbers”, Amer. Jour. of Math., 63 (1941), 211–232.