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

Firstly, note that 12769 = 113^{2}, and that 113 is a prime number.

Any integer which is divisible by 113^{2} must also be divisible by 113.

We will show that, if n is an integer, and n^{2} + 11n + 2 is divisible by 113, it cannot be divisible by 113^{2}.

Consider n^{2} + 11n + 2 | = (n − 51)(n + 62) + 3164. |

= (n − 51)(n + 62) + 28×113. |

If n^{2} + 11n + 2 is divisible by 113^{2}, 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^{2}.

Therefore n^{2} + 11n + 2 is not divisible by 12769, for any integer n.

Consider n^{2} + 11n + 2 | = (n + 62)^{2} − (113n + 3842). |

= (n + 62)^{2} − 113(n + 34). |

If n^{2} + 11n + 2 is divisible by 113^{2}, 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 113^{2}, while 113(n + 34) is not. (Since (n + 34) is not divisible by 113.)

Therefore n^{2} + 11n + 2 is not divisible by 12769, for any integer n.

Completing the square, we find that n^{2} + 11n + 2 (n + 62)^{2} (modulo 113).

Hence, since 113 is prime, n^{2} + 11n + 2 0 n −62 51 (mod 113).

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

But (51 + 113t)^{2} + 11(51 + 113t) + 2 | 51^{2} + 102·113t + 11·51 + 11·113t + 2 (mod 113^{2}), since (113t)^{2} 0 (mod 113^{2}). |

62·51 + 2, since 113·113t 0 (mod 113^{2}). | |

0 (mod 113^{2}). |

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

Therefore n^{2} + 11n + 2 is not divisible by 12769, for any integer n.

Source: Original