Results 1 to 4 of 4

Math Help - quadratic congruences

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    2

    quadratic congruences

    x^2=14(mod p) where p is prime.
    Given: solution exists or basically, a^((p-1)/2)=1 (mod p).

    Find values of p.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by florest View Post
    x^2=14(mod p) where p is prime.
    Given: solution exists or basically, a^((p-1)/2)=1 (mod p).

    Find values of p.
    First it is trivial for p=2.

    You need to find all values for odd primes p such that, the Legendre symbol, (14/p)=1.
    That is,
    (2/p)*(7/p)=1
    Thus,
    (2/p)=(7/p)=1
    or
    (2/p)=(7/p)=-1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2007
    Posts
    2
    (2/p)=(7/p)=1
    or
    (2/p)=(7/p)=-1
    Hmm.
    would that mean
    1=2^((p-1)/2) mod p
    1=7^((p-1)/2) mod p

    or
    -1=2^((p-1)/2) mod p
    -1=7^((p-1)/2) mod p
    ?

    Wouldn't that exist for all odd prime values of p excluding 7??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by florest View Post
    (2/p)=(7/p)=1
    or
    (2/p)=(7/p)=-1
    Here is my professor's approach to this problem. But based on my commentaries.

    The way this problem is actually solved is through a most beautiful result, Quadradic Reciprocity.

    I will use the following theorem.

    Theorem: Let p be an odd prime then (2/p)=1 if p=1,7(mod 8) otherwise (2/p)=-1.

    Proof: This is a well-known fact, that can be easily be proven with Gauss' Lemma.

    Now, I said there are two cases to consider.
    1) Both Legendre symbols are 1.
    2) Both Legendre symbols are -1.

    I shall do case #1 and leave case #2 for you to do.

    Throughout this derivation you are expected to know the basic properties of the Legendre symbol.

    ----
    So in case #1 we require that (2/p)=1 and (7/p)=1.

    Note, by theorem, (2/p)=1 for p=1,7(mod 8).

    Now, to do (7/p) we will rely on Quadradic Reciprocity.

    Thus,
    (7/p) = (p/7) if p=1(mod 4).
    (7/p) = -(p/7) if p=3(mod 4).

    Now let us do the first case first with p=1(mod 4).
    Under modulo 7, p=1,2,3,4,5,6(mod 7)
    Check each one:
    (1/7)=1, (2/7)=1 , (3/7)=-1, (4/7)=1, (5/7)=-1, (6/7)=-1

    This tells us that if p=1(mod 4).
    Then p=1,2,4(mod 7).
    And if p=3(mod 4).
    Then p=3,5,6(mod 7).

    Combining these under the same modulos since gcd(4,7)=1. With Chinese Remainder Theorem.

    Thus, p= 1,3,9,19,25,27 (mod 28)

    So if you multiply 8k+1,8k+7 with this out you get,

    p=1,3,7,9,19,21,25,27,63,133,175,189(mod 224)

    And this is only the first case.
    The second case will produce more prime forms.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic Congruences...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 19th 2010, 03:32 PM
  2. Quadratic Congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 13th 2009, 10:36 PM
  3. solve quadratic congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 12th 2008, 04:12 PM
  4. [SOLVED] Quadratic Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 14th 2008, 09:43 PM
  5. Congruences classes, Quadratic Field
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 4th 2008, 07:40 PM

Search Tags


/mathhelpforum @mathhelpforum