2.1: Problem 12: Prove that 19 is not a divisor of \(4n^2 + 4\) for any integer \(n\).
Proof
Observe that \(4n^2 + 4 = 4(n^2 + 1)\). since \(10 \not\mid 4\), then we want to show that \(19 \not\mid (n^2 + 1)\). This means that
$$
\begin{align*}
(n^2 + 1) \equiv 0 \pmod{19}
\end{align*}
$$
has no solution for any \(n\). This simplifies to
$$
\begin{align*}
n^2 \equiv -1 \pmod{19}
\end{align*}
$$
We have \(18\) residue classes to check
| \(n\) | \(n^2\) | \(n^2 \bmod 19\) |
|---|---|---|
| \(1\) | \(1\) | \(1\) |
| \(2\) | \(4\) | \(4\) |
| \(3\) | \(9\) | \(9\) |
| \(4\) | \(16\) | \(16\) |
| \(5\) | \(25\) | \(6\) |
| \(6\) | \(36\) | \(17\) |
| \(7\) | \(49\) | \(11\) |
| \(8\) | \(64\) | \(7\) |
| \(9\) | \(81\) | \(5\) |
| \(10\) | \(100\) | \(5\) |
| \(11\) | \(121\) | \(7\) |
| \(12\) | \(144\) | \(11\) |
| \(13\) | \(169\) | \(17\) |
| \(14\) | \(196\) | \(6\) |
| \(15\) | \(225\) | \(16\) |
| \(16\) | \(256\) | \(9\) |
| \(17\) | \(289\) | \(4\) |
| \(18\) | \(324\) | \(1\) |
We can see here that \(-1\) or \(18\) is not in any row. Therefore, \(19\) can’t divide \(n^2 + 1\). \(\ \blacksquare\)
Side Note: We actually only needed to check \(1\) to \(9\) Why?