Square Roots and Su mof Two Squares (involves modulos)

**1337h4x** · May 28th 2010, 10:45 AM

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@** · May 28th 2010, 11:00 AM

Originally Posted by 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!

2.) This follows directly from 1.):

$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** · May 28th 2010, 11:07 AM

Originally Posted by chiph588@

2.) This follows directly from 1.):

$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@** · May 28th 2010, 02:07 PM

Originally Posted by 1337h4x

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@** · May 28th 2010, 03:55 PM

Originally Posted by 1337h4x

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 $p\equiv 1\bmod{4}$ .

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

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

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

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

-------

I'll post the other direction later.

**chiph588@** · May 28th 2010, 07:13 PM

Originally Posted by 1337h4x

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 $(a,p)=1$ , suppose $n$ is the smallest number greater than $0$ such that $a^n\equiv1\bmod{p}$ and $a^m\equiv1\bmod{p}$ where $m>n$ , then $n\mid m$ .

Proof: By the division algorithm, $m=qn+d$ where $0\leq d <n$ . So we then get $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 $d<n$ and $a^d\equiv1\bmod{p}$ , by the minimality of $n$ this forces $d=0$ . So we see that $m=qn\implies n\mid m$ .

-------

Suppose $x^2\equiv-a^2\bmod{p}$ is solvable. This implies $\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 $x^2\equiv-1\bmod{p}$ solvable implies $p\equiv1\bmod{4}$ .

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

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

**1337h4x** · May 29th 2010, 07:26 AM

Originally Posted by chiph588@

Now for the other direction:

-------

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

Proof: By the division algorithm, $m=qn+d$ where $0\leq d <n$ . So we then get $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 $d<n$ and $a^d\equiv1\bmod{p}$ , by the minimality of $n$ this forces $d=0$ . So we see that $m=qn\implies n\mid m$ .

-------

Suppose $x^2\equiv-a^2\bmod{p}$ is solvable. This implies $\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 $x^2\equiv-1\bmod{p}$ solvable implies $p\equiv1\bmod{4}$ .

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

So as you can see, $4$ is the smallest exponent greater than $0$ such that $x^n\equiv 1\bmod{p}$ . Now by Fermat's little theorem, since $(x,p)=1\implies x^{p-1}\equiv1\bmod{p}$ . By our above Lemma, this implies $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@** · May 29th 2010, 07:37 AM

Originally Posted by 1337h4x

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 $a\iff b$ .

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

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

**1337h4x** · May 29th 2010, 07:42 AM

Originally Posted by chiph588@

Both are for the first question.

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

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

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

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

**chiph588@** · May 29th 2010, 09:44 AM

Originally Posted by 1337h4x

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

yes

Thread: Square Roots and Su mof Two Squares (involves modulos)

LinkBack

Thread Tools

Display

Square Roots and Su mof Two Squares (involves modulos)

Similar Math Help Forum Discussions

square root and squares

Fractional Square Roots w/ unperfect squares...

Solve the problem (involves roots and letters)

Math problem (involves square roots)

Rules for squares and square roots

Search Tags