# Solution to puzzle 66: Quadratic divisibility

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

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

## Solution 1

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

If n2 + 11n + 2 is divisible by 1132, 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 1132.

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

## Solution 2

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

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

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

## Solution 3

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

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

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

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

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

Source: Original

Back to top