Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quadratic congruences with prime modulus

  1. Oct 16, 2006 #1
    The question is:

    Show that if p == 1 mod 4, then (a/p) = (-a/p).
    (Note that == means congruent).

    I know that if X^2==a mod p (p is a prime) is solvable then a is a quadratic residue of p.

    For an example, I let p = 5 since 5==1 mod 4. Then, I let X = 2 and 4 just to check the equation. So:

    2^2==-1 mod 5...........a=-1 is quadratic residue.
    4^2==1 mod 5............a=1 is quadratic residue.

    I know that the legendre symbol (a/p) is 1 if a is a quadratic residue mod p and -1 if a is a quadratic non-residue.

    From my example, (-1/5)=1 and (1/5)=1, so I have found an example that shows (a/p) = (-a/p) but I'm having trouble proving it in general.

    Thanks!
     
  2. jcsd
  3. Oct 16, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Do you know anything about (-1/p)? Have you seen Euler's criteron?
     
  4. Oct 16, 2006 #3

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    p = 1 (mod 4) implies (-1/p) = 1.
     
  5. Oct 16, 2006 #4
    No shmoe, I don't know anything about (-1/p) and I just did some research on Euler's criterion:

    if a is quadratic residue modulo p (i.e. there exists a number k such that k^2 ≡ a (mod p)), then

    a^(p − 1)/2 ≡ 1 (mod p)
    and if a is not a quadratic residue modulo p then

    a^(p − 1)/2 ≡ −1 (mod p).

    I'm not really seeing the connection of why this helps....thanks again
     
  6. Oct 16, 2006 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    If you are happy using Euler's criterion, how do

    a^(p-1)/2 mod p

    and

    (-a)^(p-1)/2 mod p

    compare when p=1 mod 4?

    Also, by looking at (-1)^(p-1)/2 mod p, you can prove what AKG posted with Euler's.

    If this is for a class, you should try to prove it using methods you've covered though. What do you know so far about the legendre symbol?
     
  7. Oct 16, 2006 #6
    This is for a class but he didn't teach us ANYTHING about the legendre symbol. I'm guessing that 1 mod 4 implies (-1/p)=1 is critical but i still don't really understand.

    I took shmoe's advice and found that, when p==1 mod 4
    a^(p-1)/2 mod 5 equals (-a)^(p-1)/2 mod 5
     
  8. Oct 16, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Oi, do you at least have a text you're expected to have access to?

    5 is just one specific example of such a prime, but we can go with this a little bit. More important is what happens in the exponent, when p is 5, (p-1)/2=2. and you have:

    a^(p-1)/2 =a^2 mod 5

    and

    (-a)^(p-1)/2 =(-a)^2=(-1)^2 * a^2 =a^2 mod 5

    So you'd have

    a^(p-1)/2 = (-a)^(p-1)/2 mod 5

    and therefore (a/p)=(-a/p)

    What was important here is the (-1)^(p-1)/2 part. It was 1 when p=5 above. What can you say about (-1)^(p-1)/2 when p=1 mod 4?


    This is really asking about (-1/p). It comes in here because (-a/p)=(-1/p)*(a/p). More generally you'd have (a*b/p)=(a/p)*(b/p).
     
  9. Oct 16, 2006 #8
    Yes shmoe, I do have a textbook...."Elementary Theory of Numbers" by William J. LeVeque. Unlike most mathbooks, this one is about 100 pages and very small....though its size has proven to be misleading...ANYWAYS:

    When p==1 mod 4, (-1)^(p-1)/2 will be an even number because p will be odd (p=4d+1 for some d) and (p-1)/2 will be an even number...(-1)^even number is 1.
     
  10. Oct 16, 2006 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    LeVeque is a nice little book. It works in the ties with abstract algebra well.

    Exactly. If p=3 mod 4, (p-1)/2 would have been odd, so you'd end up with -1, and you hopefully see (-1/p) is completely determined by p mod 4.

    Back to your problem, you should now be able to show

    (-a)^(p-1)/2 = a^(p-1)/2 mod p

    when p=1 mod 4, by just pulling out the -1 from the left hand side like I did above. That's pretty much it.
     
  11. Oct 16, 2006 #10
    Alright I think I get it now. Thanks so much for the help shmoe!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Quadratic congruences with prime modulus
  1. Prime & Congruences (Replies: 7)

  2. Congruences and primes (Replies: 2)

Loading...