Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
    • Thread Starter
    Offline

    3
    ReputationRep:
    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!

    Offline

    0
    ReputationRep:
    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...
    • Thread Starter
    Offline

    3
    ReputationRep:
    (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.
    Offline

    0
    ReputationRep:
    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 .
    • Thread Starter
    Offline

    3
    ReputationRep:
    (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?
    Offline

    0
    ReputationRep:
    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
    • Thread Starter
    Offline

    3
    ReputationRep:
    (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?
    Offline

    0
    ReputationRep:
    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.
    Offline

    0
    ReputationRep:
    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.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: April 4, 2013
Poll
Do you like carrot cake?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

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.