# 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 | n5 + 5 and d | (n + 1)5 + 5.  That is, d is a common divisor, but not necessarily the greatest common divisor.
Then d | (n + 1)5 + 5 − (n5 + 5) = 5n4 + 10n3 + 10n2 + 5n + 1.
Similarly, d | 5(n5 + 5) − (n − 2)(5n4 + 10n3 + 10n2 + 5n + 1) = 10n3 + 15n2 + 9n + 27.
d | 4(5n4 + 10n3 + 10n2 + 5n + 1) − (2n + 1)(10n3 + 15n2 + 9n + 27) = 7n2 − 43n − 23.
d | 98(10n3 + 15n2 + 9n + 27) − (140n + 1070)(7n2 − 43n − 23) = 50112n + 27256.
d | 1569507840(7n2 − 43n − 23) − (219240n − 1466005)(50112n + 27256) = 3858751960.

The prime factorization of 3858751960 is 23 · 5 · 72 · 1968751.

Now, n5 + 5 and (n + 1)5 + 5 are alternately even and odd, and therefore cannot be congruent in any even modulus.
Similarly, by Fermat's Little Theorem, or by inspection, n5 = n (mod 5), and therefore n5 + 5 and (n + 1)5 + 5 cannot be congruent in any modulus that is a multiple of 5.
Finally, by inspection, n5 (n + 1)5 (mod 7), and so n5 + 5 and (n + 1)5 + 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 = 26 · 33 · 29.  The following calculations are understood to be performed modulo 1968751.

2 · 984376 = 1968751 + 1 2−1 984376.
Then 2−3 984376/4 246094.
So 2−6 2460942 1507325.

3 · 1312501 = 2 · 1968751 + 1 3−1 1312501.
Then 3−3 13125013 1239584.

Finally, 29 · 67888 = 1968751 + 1 29−1 67888.

Therefore 50112−1 2−1 · 3−1 · 29−1 1507325 · 1239584 · 67888 1731811.

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

## Conclusion

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

(In fact, 5333605 + 5 = 5 · 78803 · 1968751 · 55641478729429717, and
5333615 + 5 = 2 · 31 · 1968751 · 549756587 · 643210846049.)

Source: Law of Small Numbers