Solution to puzzle 58: Fifth power plus five

Let d, a, and b be integers. We will make use of the result that if d | a (d divides a) and d | b, then d | ax + by, where x and y are arbitrary integers. By judicious choice of x and y, we will successively reduce the degree of the expression which d divides, until it is simply an integer.

Determining possible values for the greatest common divisor

Suppose d | n⁵ + 5 and d | (n + 1)⁵ + 5. That is, d is a common divisor, but not necessarily the greatest common divisor.
Then d | (n + 1)⁵ + 5 − (n⁵ + 5) = 5n⁴ + 10n³ + 10n² + 5n + 1.
Similarly, d | 5(n⁵ + 5) − (n − 2)(5n⁴ + 10n³ + 10n² + 5n + 1) = 10n³ + 15n² + 9n + 27.
d | 4(5n⁴ + 10n³ + 10n² + 5n + 1) − (2n + 1)(10n³ + 15n² + 9n + 27) = 7n² − 43n − 23.
d | 98(10n³ + 15n² + 9n + 27) − (140n + 1070)(7n² − 43n − 23) = 50112n + 27256.
d | 1569507840(7n² − 43n − 23) − (219240n − 1466005)(50112n + 27256) = 3858751960.

The prime factorization of 3858751960 is 2³ · 5 · 7² · 1968751.

Now, n⁵ + 5 and (n + 1)⁵ + 5 are alternately even and odd, and therefore cannot be congruent in any even modulus.
Similarly, by Fermat's Little Theorem, or by inspection, n⁵ = n (mod 5), and therefore n⁵ + 5 and (n + 1)⁵ + 5 cannot be congruent in any modulus that is a multiple of 5.
Finally, by inspection, n⁵ (n + 1)⁵ (mod 7), and so n⁵ + 5 and (n + 1)⁵ + 5 cannot be congruent in any modulus that is a multiple of 7.
This leaves as possibilities d = 1 or d = 1968751.

When is the greatest common divisor > 1?

Note that, from above, d is a common divisor of 50112n + 27256 and 1968751.
Since 1968751 is prime, if 50112n + 27256 0 (mod 1968751), we must have d = 1.

To solve this congruence, we will find the modular inverse of 50112. (We can speak of a unique modular inverse because the modulus, 1968751, is prime.) In general, we would use the Euclidean algorithm to calculate a modular inverse. However, in this case, the prime factors of 50112 are small, and we can proceed by inspection.

In fact, we have 50112 = 2⁶ · 3³ · 29. The following calculations are understood to be performed modulo 1968751.

2 · 984376 = 1968751 + 1 2⁻¹ 984376.
Then 2⁻³ 984376/4 246094.
So 2⁻⁶ 246094² 1507325.

3 · 1312501 = 2 · 1968751 + 1 3⁻¹ 1312501.
Then 3⁻³ 1312501³ 1239584.

Finally, 29 · 67888 = 1968751 + 1 29⁻¹ 67888.

Therefore 50112⁻¹ 2⁻¹ · 3⁻¹ · 29⁻¹ 1507325 · 1239584 · 67888 1731811.

We have 50112n + 27256 = 0, and so 50112n = 1941495.
Hence n = 1731811 · 1941495 533360 (mod 1968751.)

Conclusion

We conclude that n⁵ + 5 and (n + 1)⁵ + 5 are relatively prime if n 533360 (mod 1968751).
If n 533360 (mod 1968751), their greatest common divisor is 1968751.

(In fact, 533360⁵ + 5 = 5 · 78803 · 1968751 · 55641478729429717, and
533361⁵ + 5 = 2 · 31 · 1968751 · 549756587 · 643210846049.)

Source: Law of Small Numbers