Show that $x^2+1$ is not divisible by 19 using modular arithmetic

Question

I am learning how to use modular arithmetic and am struggling. I approached the problem by letting $x=19k+r$ and then showing we cannot factor out 19 when considering all the remainders. What is a more efficient solution using modular arithmetic?

Answer 1

You want to show that $x^2\not \equiv -1 (mod19)$, for any $x \in \mathbb{Z}/19\mathbb{Z}$.

You have $x\equiv 0, \pm1, \pm2, \pm3, \pm4, \pm5, \pm6, \pm7, \pm8, \pm9 (mod19).$

Squaring, you get that $x^2 \equiv 0, 1, 4, 9, 16, 6, 17, 11, 7, 5 (mod19)$.

So, $-1$ is not a quadratic residue.

A more general/less tedious approach:

You can notice that $19$ is a prime that satisfies $19 \equiv 3 (mod4)$ and use the following proposition:

If $p$ is a prime such that $p \equiv 3 (mod4)$ and $p | x^2+y^2$, then $p|x$ and $p|y$.

To prove this, notice that $p | x^2+y^2 \Rightarrow x^2 \equiv -y^2 (modp) (*)$.

Since $p \equiv 3 (mod4)$, you know that $\frac{p-1}{2}$ is an odd number. So, raising $(*)$ to the $(\frac{p-1}{2})^{th}$ power, you get that: $x^{p-1} \equiv -y^{p-1} (modp)$.

Now, using Fermat's Little Theorem, if $p\not| y$, you get that $x^{p-1} \equiv -1 (modp)$, which is impossible (by Fermat's Little Theorem).

So, $p|y$ and thus $p|x$.

In our case, you can apply this for $p=19$ and $y=1$ to conclude that $19|1$, which is obviously a contradiction.

Answer 2

This is the same as proving that $-1\equiv x^2\mod 19$ has no solutions. So, you want to prove that $-1$ is not quadratic residue mod $19$ one way is just to check that $0^2,1^2,2^2,\dots,18^2$ are not congruent to $-1\bmod 19$. But this is long and not efficient.

If you know about theory of characters, to be more precise, the Legendre symbol. Then, one of the properties is that $\left(\frac{-1}{19}\right)=(-1)^{(19-1)/2}=-1$. The Legendre symbol $\left(\frac{-1}{19}\right)$ being equal to $-1$ means that $-1$ is a quadratic non-residue, so we are done.

Edit: So, just to show you the power of Legendre symbols: If the problem were mod a big prime like $523$, then again, since $\left(\frac{-1}{523}\right)=(-1)^{(523-1)/2}=(-1)^{261}=-1$, we have that $-1$ is not a quadratic residue mod $523$, which implies that $x^2+1$ is never divisible by $523$.

As you can see the solvability of the equation $x^2+1\equiv 0\mod p$ just reduces to know if the prime $p$ satisfies $p\equiv 1\mod 4$ or $p\equiv 3\mod 4$

Answer 3

Remainders in dividing $x$ by $19$ are $$ \pm 1, \pm 2,...,\pm9$$

Squaring and adding $1$ to these remainders will not produce a multiple of $19$

We get $$\{2,5,10,17,...,82\} $$ None of them a is a multiple of $19$

Answer 4

$x^2\cong-1\pmod{19}\implies (x^2)^9\cong (-1)^9\pmod{19}\implies x^{18}\cong -1\pmod {19}$.

But, by Fermat's little theorem, $x^{18}\cong1\pmod{19}\implies 1\cong -1\pmod{19}\Rightarrow \Leftarrow $.