Year 12s: what will be the first way you research your future options? >>

Hopefully Simple Modular Arithmetic

Hey,

I do apologise if this turns out to be ridiculously easy, but I do not understand the logic behind a step in a proof I am reading and I cannot work it out myself.

The scene:

p is a prime such that p is congruent to 3 modulo 4.
x and y are integers such that (x^2)+(y^2) is congruent to 0 modulo p.

The conclusion:

x and y are both congruent to 0 modulo p.

The question:

Why?

I attempted a case-by-case analysis and quickly discovered that either gcd(x,p)=gcd(y,p)=1 or gcd(x,p)=gcd(y,p)=p. However, I could not discount the 1st case.

Please help me!

:smile:

Reply 1

jb444

Some hints that might help: first observe that if both x and y are coprime to p then

x^2 = (p-1)y^2 \mod p

(also true when x,y are divisible by p, but in this case a correct argument won't work).

Conclude that if such a solution exists, then there must be a number mod p that squares to give

p-1

mod

p

.

Finally, using the fact that

p = 3 \mod 4

, show that no such number exists.

Therefore you are left with the second case you obtained.

Edit: argh, there've been various edits that should be noted, it's late...

(edited 11 years ago)

Reply 2

Magu1re

Original post by jb444

Some hints that might help: first observe that if both x and y are coprime to p then

x^2 = (p-1)y^2 \mod p

(also true when x,y are divisible by p, but in this case a correct argument won't work).

Conclude that if such a solution exists, then there must be a number mod p that squares to give

p-1

mod

p

.

Finally, using the fact that

p = 3 \mod 4

, show that no such number exists.

Therefore you are left with the second case you obtained.

Edit: argh, there've been various edits that should be noted, it's late...

Thanks for the response.

I tried your method but could not make much progress. Instead I found a very easy method which involves the use of Legendre symbols and requires knowledge of quadratic residues.

x^2 + y^2 congruent to 0 modulo p -> x^2 congruent to -(y ^ 2) modulo p
-> -(y^2) is a quadratic residue modulo p (if y is coprime to p)
-> ( -(y^2) / p ) = 1

But ( -(y^2) / p ) = (-1/p) (y^2 / p ) = (using Euler's criterion) -1 x 1 (if y is coprime to p) = -1

So we have our contradiction and conclude x and y are both congruent to 0 modulo p.

Reply 3

jb444

In fact this is the same proof: using Euler's criterion to show that

\left(\frac{-1}p\right) = \left(\frac{p-1}p\right) = -1

when p = 3 mod 4 is one way of showing that

p-1

is not a square mod

p

Reply 4

Magu1re

Original post by jb444

In fact this is the same proof: using Euler's criterion to show that

\left(\frac{-1}p\right) = \left(\frac{p-1}p\right) = -1

when p = 3 mod 4 is one way of showing that

p-1

is not a square mod

p

Nice. You previously wrote that we could conclude p-1 is a quadratic residue mod p, or at least you wrote it was congruent to a square as a result of the equation written above it. What was your line of reasoning for this? :smile:

Reply 5

jb444

Supposing that

x,y

are coprime to

p

, they have inverses modulo

p

, and therefore:

x^2 = (p-1)y^2 \mod p

can be written

(xy^{-1})^2 = (p-1) \mod p

a contradiction, since this shows that

\left(\frac{p-1}{p}\right) = 1

Reply 6

Magu1re

Original post by jb444

Supposing that

x,y

are coprime to

p

, they have inverses modulo

p

, and therefore:

x^2 = (p-1)y^2 \mod p

can be written

(xy^{-1})^2 = (p-1) \mod p

a contradiction, since this shows that

\left(\frac{p-1}{p}\right) = 1

What is it that makes x/y an integer?

Reply 7

jb444

Here

y^{-1}

is an inverse modulo p, i.e. an integer modulo p such that

y \cdot y^{-1} = 1 \mod p

. So e.g.

3^{-1} = 2 \mod 5

since

3\cdot 2 = 1 \mod 5

Such a number exists only when y and p are coprime.

Reply 8

jb444

ok...some proper details.

Suppose x,y are coprime to

p

.

By Bezout's identity, there exist

a,b \in \mathbb Z

such that

ay + bp = 1

.

That is,

ay = 1 \mod p

.

We have

x^2 = -y^2 \mod p

.

Therefore

(ax)^2 = a^2x^2 = - (ay)^2 = -1 \mod p

.

Thus -1 is a square mod p.

Write

z = ax

. If

\gcd(z,p) > 1

, then

\gcd(-1,p) = \gcd(z^2,p) > 1

, which is impossible.

Thus by fermat's little theorem

z^{p-1} = 1 \mod p

.

Since

p = 3 \mod 4

p = 3 + 4k

, so

(p-1)/2

is odd.

Finally,

z^{(p-1)} = (z^2)^{(p-1)/2} = (-1)^{(p-1)/2} = -1

This is a contradiction of the above, since it shows that

z

(as well as any other number) does not square to give -1 mod p.

An elementary proof of something like this is a little nicer, since the idea remains hidden inside Euler's identity for the legendre symbol; the ideas are the same.