Number Theory: Find $m\equiv 1\pmod4$ so that $x^2\equiv -1\pmod{m}$ has no solution.

Question

I have this problem that I'm a bit stuck on:

Find $m\equiv 1\pmod4$ so that $x^2\equiv -1\pmod{m}$ has no solution in $\mathbb{Z}$.

So far, I know that $m$ can't be prime because $(\frac{-1}{p})=1$, $p$ prime, whenever $p\equiv 1\pmod4$, where $(\frac{}{})$ is the legendre symbol.

Also, I've considered the following: $m=4k+1$, so

$(\frac{-1}{m})=(\frac{4k}{m})=(\frac{4}{m})(\frac{k}{m})=(\frac{k}{m})$, but again I get stuck here since $m$ is composite.

I think that there is no such $m$, but I'm unsure how to prove it.

My Proof So Far

Note that if $m=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$, $p_i$ prime, $k_i\geq 1$ then by the Chinese Remainder Theorem, $x^2\equiv -1\pmod{m}$ has a solution $\iff x^2\equiv -1\pmod{p_i^{k_i}}$ for all $1\leq i\leq r$.

So, let us take $m=p^k$, $p$ prime, $k\geq 1$.

Note that we must have $k>1$ since $k=1\implies m=p\implies (\frac{-1}{m})=1$ since $m\equiv1\pmod4$.

...

Now, I know that $m=3^2=9$ works, but I'm not sure how to prove that $({-1\over9})=-1$ since $9$ is composite. I'm also not allowed to use the fact that $x^2\equiv a\pmod{p^n}$ has a solution $\iff ({a\over p})=1$ since we haven't covered this theorem in class.

Answer 1

Hint: If $m = p_1^{x_1} p_2^{x_2} \ldots p_k^{x_k}$, then $a$ is a square mod $m$ if and only if $a$ is a square mod $p_i^{x_i}$, for all $i$, by the chinese remainder theorem. So if $-1$ is not a square mod $m$, then $-1$ is not a square mod $p^i$ for some prime $p$ and positive integer $i$. So you might as well just take $m = p^i$ for some $i$.

As you've observed, by looking at the Legendre symbol, $i = 1$ doesn't work. What about $i \ge 2$? Try some specific primes.

Answer 2

If $m$ is prime, this is impossible, since $\biggl(\dfrac{-1}p\bigr)=(-1)^{\tfrac{p-1}2}$. Hence the idea is to take $m=pq$, where $p\neq q\equiv3\mod4$. By the Chinese remainder theorem: $$\mathbf Z/m\mathbf Z\simeq\mathbf Z/p\mathbf Z\times\mathbf Z/q\mathbf Z$$ $-1$ cannot be a square modulo $m$ since it is not a square modulo $p$ nor $q$.

The smallest $m$ obtained in this way is $m=\color{red}{21}$.

Answer 3

It is well known that $x^2\equiv -1\bmod m$ has a solution when $m$ is prime of the form $4k+1$ but not when it is of the form $4k+3$.

So, $m$ cannot be prime. But it can be the product of two primes of the form $4k+3$. The smallest such $m$ is $3 \cdot 7 = 21$.