5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Isn't $m=9$ a solution? Do you need to find all such $m$? $\endgroup$ – J.Gudal Dec 7 '15 at 23:32
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This approach makes a lot of sense to me, but I'm still confused on how to prove that, for instance, $3^2=9$ works. $\endgroup$ – MathQuestion Dec 8 '15 at 2:21
  • $\begingroup$ @mathquestion: just try each possibility for x. You only have to try x=1 to x=9. $\endgroup$ – 6005 Dec 8 '15 at 2:22
  • $\begingroup$ Oh, of course, I didn't notice that... Thank you! In that case, $2^2=4$ would also work since each of $1^2,2^2,3^2,4^2\not\equiv -1\pmod4$. $\endgroup$ – MathQuestion Dec 8 '15 at 2:24
  • 1
    $\begingroup$ @MathQuestion $3^2$ works because the prime $3$ is of the form $4k+3$. See Quadratic Reciprocity. $4$ works because it's divisible by $4$. More generally, $-1$ is a quadratic residue mod $n$ if and only if $n$ is not divisible by $4$ and all the prime divisors of $n$ are either of the form $4k+1$ or $2$. $\endgroup$ – user236182 Dec 8 '15 at 5:00
1
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.