Show that $n^2+11n+2$ is not divisible by $113^2$ ( n is integer)

Question

Show that $n^2+11n+2$ is not divisible by $113^2$ ( n is integer)
It's obvious that if we show $113$ doesn't divide $n^2+11n+2$ we are done...

Answer 1

Judge my simple solution:(Many thanks to @Miracle173 )
$$n^2+11n+2=(n+62)^2-113(n+34)$$ Now since $113$ is prime ,if $\ n^2+11n+2$ is divisible by $113^2$ then it's also divisible by $113$ so $(n+62)^2$ must also be divisible by $113$,so $n+62$ is also divisible by $113$.
Now we infer that $(n+62)^2$ is divisible by $113^2$.
So $113(n+34)$ must also be divisible by $113^2$ which means $n+34$ is divisible by $113$ which is IMPOSSIBLE!
Because $n+62$ is divisible by $113$ , so $n^2+11n+2$ is not divisible by $113^2$

Answer 2

Working in $ \mathbb{Z}/113\mathbb{Z} $, we want to investigate the roots of $ X^2 + 11X + 2 $. Its discriminant is $ 11^2 - 4 \cdot 2 = 113 = 0 $, so it is a perfect square, and using the quadratic formula we see that the double root is $ X = 51 $. Now, let $ X = 51 + 113k $ for $ 0 \leq k < 113 $ and expand: (If it has a root modulo $ 113^2 $, it has to be of this form.)

$$ (113k + 51)^2 + 11(51 + 113k) + 2 = 113^2 k^2 + 2\cdot 51 \cdot 113k + 51^2 + 11\cdot 51 + 11\cdot 113k + 2 $$

Collecting like terms, we have

$$ 113^2 k^2 + 113^2 k + 62 \cdot 51 + 2 $$

Now, reduce mod $ 113^2 $ to get $ 62 \cdot 51 + 2 $. As this expression is clearly smaller than $ 113^2 $, it cannot be zero modulo $ 113^2 $, so the original equation has no roots and we are done.

Answer 3

A good start would be to find if the equation $n^2 + 11n + 2 \equiv 0$ has any solutions modulo 113. We can do this by completing the square, so we want to find $a,b \in \mathbb{Z}/113\mathbb{Z}$ such that

$$ n^2 + 11n + 2 \equiv (n-a)^2 + b \pmod{113}. $$

By expanding we see that $-2a \equiv 11 \pmod{113}$, so $a \equiv (-2)^{-1}\cdot 11 \equiv 51 \pmod{113}$. If we fill this in we find that actually $b \equiv 0 \pmod{113}$ so

$$ n^2 + 11n + 2 \equiv (n-51)^2 \pmod{113}. $$

This shows that $n\equiv51 \pmod{113}$ is the only solution to the equation $$n^2 + 11n + 2 \equiv 0 \pmod{113}.$$

Now let $n = 51 + 113k$, we know the expression is divisible by $113$ for all $k$, which we can also calculate:

$$ \frac{(51 + 113k)^2 + 11(51 + 113k) + 2}{113} = 113 k^2+113 k+28 \equiv 28 \pmod{113}. $$

So we see that $n^2 + 11n + 2$ is never divisible by $113$ twice.

Answer 4

The discriminant of $p(x)=x^2+11x+2$ is $11^2-8 = 113$, hence $p(x)$ is a square in $\mathbb{F}_{113}$, namely: $$ p(x)\equiv (x-51)^2 \pmod{113} $$ It follows that $113^2\mid p(x)$ implies $x=113k+51$, but $$ p(113k+51) = 113\cdot\left(\color{red}{28}+113k+113k^2\right) $$ hence there are no values of $x\in\mathbb{Z}$ such that $p(x)\equiv 0\pmod{113^2}$.

Answer 5

$113$ is prime.

$$n^2+11n+2\equiv 0\pmod{113^2}$$

$$\stackrel{\cdot 4}\iff (2n+11)^2\equiv 113\pmod{113^2}$$

$$\implies 113\mid (2n+11)^2\iff 113\mid 2n+11$$

$$\iff 113^2\mid (2n+11)^2$$

$$\iff (2n+11)^2\equiv 0\not\equiv 113\pmod{113^2}$$

It's useful to know that you can always multiply both sides of a quadratic congruence by $4a$ to complete the square: If $\gcd(n,2a)=1$, then $$ax^2+bx+c\equiv 0\pmod{n}$$

$$\iff (2ax+b)^2\equiv b^2-4ac\pmod{n}$$

If $\gcd(n,2a)\neq 1$, then use $\implies$ instead of $\iff$.