Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
 You are Here: Home >< Maths

# Hopefully Simple Modular Arithmetic watch

1. 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!

2. Some hints that might help: first observe that if both x and y are coprime to p then (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 mod .

Finally, using the fact that , 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...
3. (Original post by jb444)
Some hints that might help: first observe that if both x and y are coprime to p then (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 mod .

Finally, using the fact that , 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.
4. In fact this is the same proof: using Euler's criterion to show that

when p = 3 mod 4 is one way of showing that is not a square mod .
5. (Original post by jb444)
In fact this is the same proof: using Euler's criterion to show that

when p = 3 mod 4 is one way of showing that is not a square mod .
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?
6. Supposing that are coprime to , they have inverses modulo , and therefore:

can be written

a contradiction, since this shows that

7. (Original post by jb444)
Supposing that are coprime to , they have inverses modulo , and therefore:

can be written

a contradiction, since this shows that

What is it that makes x/y an integer?
8. Here is an inverse modulo p, i.e. an integer modulo p such that . So e.g. since

Such a number exists only when y and p are coprime.
9. ok...some proper details.

Suppose x,y are coprime to .

By Bezout's identity, there exist such that .

That is, .

We have .

Therefore .

Thus -1 is a square mod p.

Write . If , then , which is impossible.

Thus by fermat's little theorem .

Since , , so is odd.

Finally,

This is a contradiction of the above, since it shows that (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.

Reply
Submit reply
Turn on thread page Beta
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: April 4, 2013
Today on TSR

### Ask the House of Commons anything

The digital outreach team is online until 4pm!

Poll
Useful resources

## Make your revision easier

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

Can you help? Study help unanswered threads

## Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.