Skip to main content.

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 congruent to (n + 62)2 (modulo 113).
Hence, since 113 is prime, n2 + 11n + 2 congruent to 0 implies n congruent to −62 congruent to 51 (mod 113).

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

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

That is, no value of t gives a solution for n2 + 11n + 2 congruent to 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