# $4(n^2+1)$ is never divisible by $11$

I found this exercise in Beachy and Blair: Abstract algebra:

Prove that $$4(n^2+1)$$ is never divisible by $11$.

(I assume $n\in\mathbb{Z}$ although this is not given in the book)

I tried with contradiction, that is assuming that $$4(n^2+1)\equiv 0 \quad (\mathrm{mod} \ 11)$$ which we can write as $$4(n^2+1)=11k\qquad k\in\mathbb{Z}$$ and I tried to reduce this modulo to reach a contradiction but I failed to arrive at any contradiction. Maybe I tried wrong moduli or I missed something or maybe there is a better way to tackle this.

Can someone provide me some HINTS?

Thank you!

• HINT: quadratic reciprocity. – Kenny Lau Oct 25 '17 at 8:04
• Start by solving the equation $4(x + 1) = 0$ modulo $11$. You'll need to decide if $4$ has a multiplicative inverse modulo $11$. – Theo Bendit Oct 25 '17 at 8:07
• solve $n^2\equiv 10 \pmod {11}$ – MCCCS Oct 25 '17 at 8:11

For any modulus $m$ there are at most $m/2+1$ different possibilities for $n^2$ (mod $m$). This is because $n^2\equiv(m-n)^2$, so the numbers mod $m$ (other than $0$ and $m/2$) divide into pairs with the same square.

Your equation has a solution if and only if $n^2+1\equiv 0$ mod $11$ has a solution, i.e. if and only if $n^2\equiv 10$ (mod $11$) has a solution. You can check that this isn't the case by working out $0^2,1^2,...,5^2$ mod $11$ (you don't need to check $6^2,...10^2$ because these are the same as $5^2,...1^2$).

$4(n^2+1)$ is divisible by $11$ if and only if $n^2+1$ is divisible by $11$ (because $4$ is invertible), which happens if and only if $n^2 \equiv -1 \pmod {11}$, which happens if and only if $-1$ is a quadratic residue $\pmod {11}$, which (by Euler's criterion) happens if and only if $(-1)^{(11-1)/2}$ is congruent to $1$, which it isn't.

The justification behind Euler's criterion is that there is a primitive root modulo any prime, meaning that you can always find $a$ such that for any non-zero number there is an $n$ such that $a^n$ is congruent to the number. Then, being a quadratic residue $\pmod p$ is equivalent to being congruent to $a^m$ for some even $m$. By Fermat's little theorem, $a^{p-1} \equiv 1 \pmod p$. We know that an even number, when multiplied by $\dfrac{p-1}2$ is a multiple of $p-1$, while an odd number has no such property. Hence, if $m$ is even, then $a^{m(p-1)/2} \equiv (a^{p-1})^{m/2} \equiv 1^{m/2} = 1$ (the middle step is permissible because $m/2$ is an integer).

For a number to be divisible by $11$ it must be a multiple of $11$.
$$4(n^2+1)$$.
clearly the product of this would be even, because of the standing $4$.
if this was even and $n$ was a real positive integer.
then $(n^2+1)$ must be a multiple of $11$.
say.
\begin{align} (n^2 + 1) = 11x\\ n^2 = 11x - 1\\ n = \sqrt{11x - 1} \end{align}.
so we are left to prove whether $(11x-1)$ is a perfect square or not.

Once you have got to seeing whether $-1$ is a square modulo $11$, you might note that the multiplicative group of residues ("units") modulo $11$ has order $10$ and that if $a^2\equiv -1$ then $a^4\equiv 1$ and $a$ has order $4$, which is a contradiction - a group of order $10$ can't have an element of order $4$.
If $p$ is a prime $\equiv 3 \bmod 4$ you can use a similar argument to show that $-1$ is not a square modulo $p$.