# Quadratic residue of $-1$ in composite modulus

It is true for each odd prime number p that if $x^2\equiv-1 \pmod p$ then $p\equiv1\pmod 4$

I've observed that it should be true for all composite integers, whose prime factors are congruent to $1$ modulo $4$. However I couldn't find any remark on the internet whether it's true.

In other words, if it is correct, how do we prove that $x^2\equiv-1\pmod n$ has a solution if and only if $n=\prod_{p|n}p$ such that $p_i=4k_i+1$

P.S: My level is pretty elementary.

-
If $x^2 \equiv a \pmod{n}$, then also $x^2\equiv a \pmod{p}$ for all primes dividing $n$. Note that you have to allow one factor $2$ or restrict to odd $n$, as for example $3^2 \equiv -1 \pmod{10}$. –  Daniel Fischer Feb 2 '14 at 16:32
This implies if $x^2\equiv -1\pmod n$ has a solution, then all of the prime factors must be congruent to $1$. But does it imply the reverse? –  Zafer Cesur Feb 2 '14 at 16:42
I guess I should've said "if and only if", let me edit that. –  Zafer Cesur Feb 2 '14 at 16:45

For an odd $n$, there are $x$ with $x^2 \equiv 1 \pmod{n}$ if and only if all prime divisors of $n$ are of the form $p = 4m+1$.

The necessity follows from $x^2 \equiv -1 \pmod{n} \Rightarrow x^2 \equiv -1 \pmod{d}$ for all divisors $d$ of $n$, in particular its prime divisors.

The sufficiency follows from the Chinese Remainder Theorem, and the fact that for any prime $p$ and $k \geqslant 1$ the group of units in $\mathbb{Z}/(p^k)$ is cyclic.

Since the group is cyclic and its order is a multiple of $4$ for $p \equiv 1 \pmod{4}$, it contains elements of order $4$, and these satisfy $x^2 \equiv -1 \pmod{p^k}$ (since $$x^4-1 = (x^2-1)(x^2+1) = (x-1)(x+1)(x^2+1) \equiv 0 \pmod{p^k},$$ and neither $x-1$ nor $x+1$ can be divisible by $p$).

Once you have solutions $x_i$ modulo each prime power $p_i^{k_i}$ dividing $n$, the Chinese Remainder Theorem asserts the existence of $x$ with

$$x \equiv x_i \pmod{p_i^{k_i}},\quad 1\leqslant i \leqslant r,$$

where $n = \prod\limits_{i=1}^r p_i^{k_i}$, and such an $x$ satisfies $x^2 \equiv -1\pmod{n}$. Since for each prime power $p_i^{k_i}$ there are exactly $2$ solutions, there are $2^r$ solutions of $x^2\equiv -1\pmod{n}$.

-
To emphasize the first statement, we can find a counterexample by picking a product of primes that is $1 \bmod 4$, but includes at least one prime that is $3 \bmod 4$. The simplest is a product of two primes that are $3 \bmod 4$: e.g. $21 = 3 \cdot 7$. –  Hurkyl Feb 2 '14 at 21:14

To draw a distinction: for any (positive) prime $p \equiv 1 \pmod 4,$ there is always a solution in integers to $$x^2 - p y^2 = -1.$$ There is a short proof in Mordell's book, Diophantine equations.

As Daniel has shown, $-1$ remains a quadratic residue for the product of such primes. However, sometimes the "negative Pell equation" has roots then, sometimes not. There is no solution in integers to $$x^2 - 205 y^2 = -1$$ or $$x^2 - 221 y^2 = -1.$$ Go Figure.

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./Pell Input n for Pell 205 0 form 1 28 -9 delta -3 1 form -9 26 4 delta 6 2 form 4 22 -21 delta -1 3 form -21 20 5 delta 4 4 form 5 20 -21 delta -1 5 form -21 22 4 delta 6 6 form 4 26 -9 delta -3 7 form -9 28 1 delta 28 8 form 1 28 -9 disc 820 Pell automorph 39689 568260 2772 39689 Pell unit 39689^2 - 205 * 2772^2 = 1 ========================================= jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell
221

0  form   1 28 -25   delta  -1
1  form   -25 22 4   delta  6
2  form   4 26 -13   delta  -2
3  form   -13 26 4   delta  6
4  form   4 22 -25   delta  -1
5  form   -25 28 1   delta  28
6  form   1 28 -25

disc   884

Pell automorph
1665  24752
112  1665

Pell unit
1665^2 - 221 * 112^2 = 1

=========================================


=-=-=-=-=-=-=-=-=-=-=-=-=

-