Divisibility of a Polynomial

Question

Prove that for all $n$, $121\mid n^2+3n+5$.

I thought proving $n^2 +3n+5\pmod{121}\equiv 0$ had no solutions would be a good start, so I completed the square of $n^2+3n+5($, and arrived at $(n+62)^2 \pmod{121} \equiv 3718$. Replacing $n+62$ by $x$, I lastly arrived at $x^2 \equiv 88\pmod{121}$. Now, Im stuck. Any hints would be appreciated.

Answer 1

I think you want to prove that $121\nmid(n^2+3n+5)$, that is, $121$ does not divide $n^2+3n+5$.

First of all ask yourself whether $n^2+3n+5$ is a multiple of $11$. The equation $n^2+3n+5\equiv0\pmod{11}$ can be rewritten $$ n^2-8n+16=(n-4)^2\equiv0\pmod{11} $$ which only holds for $n\equiv4\pmod{11}$.

Now we know that a possible solution of $n^2+3n+5\equiv0\pmod{121}$ should have $n=11k+4$, so $$ n^2+3n+5=121k^2+88k+16+33k+12+5=121(k^2+k)+33 $$ which is never $\equiv0\pmod{121}$

Answer 2

I think I got it! No last digit raised to the second power produces a last digit of $8.$ Thus, there are no solutions to $x^2 \equiv 88\pmod{121}$!

Answer 3

Just consider the case n=1, for which the polynomial is equal to 9. This is a sufficient counterexample.

Answer 4

I'll assume that you are in fact trying to show the exact opposite of what you state. That is, for all $n\in \mathbb Z$ we have $$120\,\nmid \,n^2+3n+5$$

To see this:

First, we solve the problem $\pmod {11}$. It is easy to see that $$n^2+3n+5\equiv 0\pmod {11}\implies n\equiv 4\pmod {11}$$

So, it suffices to consider only $n$ of the form $11k+4$. Suppose we had a counterexample of that form. Then we'd have $$(11k+4)^2+3(11k+4)+5\equiv 0 \pmod {121}$$ But it is easy to see that this would imply $$16+12+5\equiv 0\pmod {121}$$ which is false, hence we have a contradiction. Thus no such $n$ exists.