Solution to puzzle 66: Quadratic divisibility

Show that, if n is an integer, n² + 11n + 2 is not divisible by 12769.

Firstly, note that 12769 = 113², and that 113 is a prime number.
Any integer which is divisible by 113² must also be divisible by 113.
We will show that, if n is an integer, and n² + 11n + 2 is divisible by 113, it cannot be divisible by 113².

Solution 1

Consider n² + 11n + 2	= (n − 51)(n + 62) + 3164.
	= (n − 51)(n + 62) + 28×113.

If n² + 11n + 2 is divisible by 113², it is divisible by 113, and therefore (n − 51)(n + 62) is divisible by 113.
Since 113 is prime, (n − 51) is divisible by 113 or (n + 62) is divisible by 113 (or possibly both.)
In fact, since (n + 62) − (n − 51) = 113, both (n − 51) and (n + 62) are divisible by 113, and so (n − 51)(n + 62) is divisible by 113².

Therefore n² + 11n + 2 is not divisible by 12769, for any integer n.

Solution 2

Consider n² + 11n + 2	= (n + 62)² − (113n + 3842).
	= (n + 62)² − 113(n + 34).

If n² + 11n + 2 is divisible by 113², it is divisible by 113, and therefore (n + 62)² is divisible by 113.
Since 113 is prime, (n + 62) must be divisible by 113.
But then (n + 62)² is divisible by 113², while 113(n + 34) is not. (Since (n + 34) is not divisible by 113.)

Therefore n² + 11n + 2 is not divisible by 12769, for any integer n.

Solution 3

Completing the square, we find that n² + 11n + 2 (n + 62)² (modulo 113).
Hence, since 113 is prime, n² + 11n + 2 0 n −62 51 (mod 113).

Any solution of n² + 11n + 2 0 (mod 113²) must be of the form n = 51 + 113t, where t is an integer.

But (51 + 113t)² + 11(51 + 113t) + 2	51² + 102·113t + 11·51 + 11·113t + 2 (mod 113²), since (113t)² 0 (mod 113²).
	62·51 + 2, since 113·113t 0 (mod 113²).
	0 (mod 113²).

That is, no value of t gives a solution for n² + 11n + 2 0 (mod 113²); so there is no solution.

Therefore n² + 11n + 2 is not divisible by 12769, for any integer n.

Source: Original