# Square Roots and Su mof Two Squares (involves modulos)

#### 1337h4x

Hello all,

I have a few questions about how squares affect mods. Here they are:

1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).

How is that proven?

2. Assume there are two numbers c and d where GCD[c,d]=1. If p is any prime number and p|((c^2)+(d^2)), then p = 1 (mod 4),

How is this also proven ?

Any help is greatly appreciated!

#### chiph588@

MHF Hall of Honor
Hello all,

I have a few questions about how squares affect mods. Here they are:

1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).

How is that proven?

2. Assume there are two numbers c and d where GCD[c,d]=1. If p is any prime number and p|((c^2)+(d^2)), then p = 1 (mod 4),

How is this also proven ?

Any help is greatly appreciated!
2.) This follows directly from 1.):

$$\displaystyle p\mid c^2+d^2 \iff c^2+d^2\equiv 0\bmod{p}\iff c^2\equiv-d^2\bmod{p}\implies p\equiv1\bmod{4}$$

Now I'll help you out with 1.) if no one else does after a while.

• 1337h4x

#### 1337h4x

2.) This follows directly from 1.):

$$\displaystyle p\mid c^2+d^2 \iff c^2+d^2\equiv 0\bmod{p}\iff c^2\equiv-d^2\bmod{p}\implies p\equiv1\bmod{4}$$

Now I'll help you out with 1.) if no one else does after a while.

So how did you get 1 and 4 out of that expression? I'm sure its really simple, but trial and error is the only way I've shown it thus far. Isn't there a more "concrete" way to get 1 and 4 and not using guess & check?

I will certainly appreciate it if you help me with 1.) . Much thanks will be given!

#### chiph588@

MHF Hall of Honor
So how did you get 1 and 4 out of that expression? I'm sure its really simple, but trial and error is the only way I've shown it thus far. Isn't there a more "concrete" way to get 1 and 4 and not using guess & check?

I will certainly appreciate it if you help me with 1.) . Much thanks will be given!
I got it from applying what #1 says.

#### chiph588@

MHF Hall of Honor
1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).

How is that proven?
One way is easy:

Assume $$\displaystyle p\equiv 1\bmod{4}$$.

Consider $$\displaystyle \left(\frac{p-1}{2}\right)! = (2n)!$$ since $$\displaystyle \frac{p-1}{2}$$ is even.

I'm assuming you're familiar with Wilson's Theorem that states $$\displaystyle (p-1)!\equiv -1 \bmod{p}$$ when $$\displaystyle p$$ is prime.

So $$\displaystyle -1\equiv (p-1)! = (1\cdot2\cdots2n)((2n+1)\cdots(4n)) = (1\cdot2\cdots2n)((p-2n)\cdots(p-1))$$ $$\displaystyle \equiv (1\cdot2\cdots2n)((-2n)\cdots(-1)) = (-1)^{2n}\left(\left(\frac{p-1}{2}\right)!\right)^2 \bmod{p}$$.

Thus given $$\displaystyle p\equiv -1\bmod{4}$$, the solution to $$\displaystyle x^2\equiv -a^2\bmod{p}$$ is $$\displaystyle x\equiv a\cdot\left(\frac{p-1}{2}\right)!$$

-------

I'll post the other direction later.

Last edited:

#### chiph588@

MHF Hall of Honor
1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).

How is that proven?
Now for the other direction:

-------

Lemma: Given $$\displaystyle (a,p)=1$$, suppose $$\displaystyle n$$ is the smallest number greater than $$\displaystyle 0$$ such that $$\displaystyle a^n\equiv1\bmod{p}$$ and $$\displaystyle a^m\equiv1\bmod{p}$$ where $$\displaystyle m>n$$, then $$\displaystyle n\mid m$$.

Proof: By the division algorithm, $$\displaystyle m=qn+d$$ where $$\displaystyle 0\leq d <n$$. So we then get $$\displaystyle 1\equiv a^m=a^{qn+d}=\left(a^n\right)^q\cdot a^d \equiv 1\cdot a^d=a^d\bmod{p}$$. Since $$\displaystyle d<n$$ and $$\displaystyle a^d\equiv1\bmod{p}$$, by the minimality of $$\displaystyle n$$ this forces $$\displaystyle d=0$$. So we see that $$\displaystyle m=qn\implies n\mid m$$.

-------

Suppose $$\displaystyle x^2\equiv-a^2\bmod{p}$$ is solvable. This implies $$\displaystyle \left(a^2\right)^{-1}\cdot x^2=\left(xa^{-1}\right)^2\equiv-1\bmod{p}\implies y^2\equiv-1\bmod{p}$$ is solvable. So observe that it's equivalent to show $$\displaystyle x^2\equiv-1\bmod{p}$$ solvable implies $$\displaystyle p\equiv1\bmod{4}$$.

Since $$\displaystyle p$$ is odd, $$\displaystyle x\neq1$$, so we have the following:
$$\displaystyle x^1\not\equiv1\bmod{p}$$
$$\displaystyle x^2\equiv-1\not\equiv1\bmod{p}$$
$$\displaystyle x^3\equiv(-1)x\not\equiv1\bmod{p}$$
$$\displaystyle x^4\equiv(-1)^2\equiv1\bmod{p}$$

So as you can see, $$\displaystyle 4$$ is the smallest exponent greater than $$\displaystyle 0$$ such that $$\displaystyle x^n\equiv 1\bmod{p}$$. Now by Fermat's little theorem, since $$\displaystyle (x,p)=1\implies x^{p-1}\equiv1\bmod{p}$$. By our above Lemma, this implies $$\displaystyle 4\mid p-1 \implies p\equiv1\bmod{4}$$.

Last edited:

#### 1337h4x

Now for the other direction:

-------

Lemma: Given $$\displaystyle (a,p)=1$$, suppose $$\displaystyle n$$ is the smallest number greater than $$\displaystyle 0$$ such that $$\displaystyle a^n\equiv1\bmod{p}$$ and $$\displaystyle a^m\equiv1\bmod{p}$$ where $$\displaystyle m>n$$, then $$\displaystyle n\mid m$$.

Proof: By the division algorithm, $$\displaystyle m=qn+d$$ where $$\displaystyle 0\leq d <n$$. So we then get $$\displaystyle 1\equiv a^m=a^{qn+d}=\left(a^n\right)^q\cdot a^d \equiv 1\cdot a^d=a^d\bmod{p}$$. Since $$\displaystyle d<n$$ and $$\displaystyle a^d\equiv1\bmod{p}$$, by the minimality of $$\displaystyle n$$ this forces $$\displaystyle d=0$$. So we see that $$\displaystyle m=qn\implies n\mid m$$.

-------

Suppose $$\displaystyle x^2\equiv-a^2\bmod{p}$$ is solvable. This implies $$\displaystyle \left(a^2\right)^{-1}\cdot x^2=\left(xa^{-1}\right)^2\equiv-1\bmod{p}\implies y^2\equiv-1\bmod{p}$$ is solvable. So observe that it's equivalent to show $$\displaystyle x^2\equiv-1\bmod{p}$$ solvable implies $$\displaystyle p\equiv1\bmod{4}$$.

Since $$\displaystyle p$$ is odd, $$\displaystyle x\neq1$$, so we have the following:
$$\displaystyle x^1\not\equiv1\bmod{p}$$
$$\displaystyle x^2\equiv-1\not\equiv1\bmod{p}$$
$$\displaystyle x^3\equiv(-1)x\not\equiv1\bmod{p}$$
$$\displaystyle x^4\equiv(-1)^2\equiv1\bmod{p}$$

So as you can see, $$\displaystyle 4$$ is the smallest exponent greater than $$\displaystyle 0$$ such that $$\displaystyle x^n\equiv 1\bmod{p}$$. Now by Fermat's little theorem, since $$\displaystyle (x,p)=1\implies x^{p-1}\equiv1\bmod{p}$$. By our above Lemma, this implies $$\displaystyle 4\mid p-1 \implies p\equiv1\bmod{4}$$.

So are you saying, this is just another way of skinning the cat? Are your "directions" different "ways" of solving the same problem? Both correspond to my first question right?

#### chiph588@

MHF Hall of Honor
So are you saying, this is just another way of skinning the cat? Are your "directions" different "ways" of solving the same problem? Both correspond to my first question right?
Both are for the first question.

This is what I mean by directions: Your theorem was of the form $$\displaystyle a\iff b$$.

So in my first post I proved $$\displaystyle b\implies a$$ and in my second post I proved $$\displaystyle a\implies b$$.

Putting these two together gives $$\displaystyle a\iff b$$.

#### 1337h4x

Both are for the first question.

This is what I mean by directions: Your theorem was of the form $$\displaystyle a\iff b$$.

So in my first post I proved $$\displaystyle b\implies a$$ and in my second post I proved $$\displaystyle a\implies b$$.

Putting these two together gives $$\displaystyle a\iff b$$.

So does this mean that you have to have both to adequately prove the theorem ?

#### chiph588@

MHF Hall of Honor
So does this mean that you have to have both to adequately prove the theorem ?
yes