Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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 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 at 16:42
    
I guess I should've said "if and only if", let me edit that. –  Zafer Cesur Feb 2 at 16:45

2 Answers 2

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

share|improve this answer
    
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 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 

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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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