Results 1 to 11 of 11

Math Help - Another congruence problem

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    27

    Another congruence problem

    I missed a lecture where they discussed finding solutions to x^2 \equiv -1 mod 13 , and was given this problem to try out. Problem is, I don't even know how to start off since I don't even know how to do the above one.

    If p > 2 is prime and a member of Z, show that X^2 \equiv a mod p has either no solutions or exactly 2 solutions mod p.

    If it has 2 solutions, show that only one solution, x , satisfies 0 <= x <= (p-1)/2.
    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 Th3sandm4n View Post
    I missed a lecture where they discussed finding solutions to x^2 \equiv -1 mod 13 , and was given this problem to try out. Problem is, I don't even know how to start off since I don't even know how to do the above one.
    There is nothing brilliant here, just good through the numbers x=1,2,...,12 and see which ones work.

    Now for the second part if x^2 \equiv a(\bmod p) where (a,p)=1 has a solution x_0 then a\equiv x_0^2(\bmod p) and so (x-x_0)(x+x_0) = x^2 - x_0^2\equiv 0 (\bmod p) \implies x\equiv \pm x_0(\bmod p).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Quote Originally Posted by ThePerfectHacker View Post
    There is nothing brilliant here, just good through the numbers x=1,2,...,12 and see which ones work.

    Now for the second part if x^2 \equiv a(\bmod p) where (a,p)=1 has a solution x_0 then a\equiv x_0^2(\bmod p) and so (x-x_0)(x+x_0) = x^2 - x_0^2\equiv 0 (\bmod p) \implies x\equiv \pm x_0(\bmod p).
    Okay let me just make sure I'm getting this correctly
    we KNOW it has a solution (but we show that if it has a solution, it must has two?) x_0^2.
    so then x_0^2 \equiv a mod p

    So then,
    x^2 \equiv amodp
    x^2 \equiv x_0^2 mod p (substituting)
    x^2 - x_0^2 \equiv 0 mod p (subtracting x_0^2 from both sides)
    (x-x_0)(x+x_0) \equiv 0 modp (factoring)

    So then,
    x = x_0 or x = -x_0 \equiv 0modp
    which leads to:
    x \equiv x_0 modp
    x \equiv -x_0 modp?

    And then im guessing that 0 <= x_0 <= (p-1)/2 holds because if it was greater than half of p, squaring it would mess it up?
    And also 0>= -x_0 >=-(p-1)/2.
    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 Th3sandm4n View Post
    Okay let me just make sure I'm getting this correctly
    we KNOW it has a solution (but we show that if it has a solution, it must has two?) x_0^2.
    so then x_0^2 \equiv a mod p
    I said if it has a solution then it has two. Thus, it either has no solutions or two.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Ah, yes. I forget how important wording is in proofs sometimes.

    EDIT:
    Just a follow up for anyone else looking for something similar

    One of the solutions is between 0<= x <= (p-1)/2 because the field of p = {0,...,p-1} and since there are exactly 2 solutions or no solutions, then one solutions must cover half the field, and the other cover the other half.

    If I am correct in my thinking, barely covered fields on Friday.
    Last edited by Th3sandm4n; March 29th 2009 at 09:46 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2008
    Posts
    11
    Quote Originally Posted by ThePerfectHacker View Post
    There is nothing brilliant here, just good through the numbers x=1,2,...,12 and see which ones work.
    here is a quicker way

    x^2\equiv-1\pmod{13}\ \iff\ x^2\equiv25\pmod{13}\ \iff\ 13\mid x^2-25=(x-5)(x+5)

    hence the two solutions are 5 and 8 (mod 13)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Quote Originally Posted by Th3sandm4n View Post
    If p > 2 is prime and a member of Z, show that X^2 \equiv a mod p has either no solutions or exactly 2 solutions mod p.
    That is actually false, as it stands. If p\mid a, then x^2\equiv a\pmod p has infinitely many solutions.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by JaneBennet View Post
    That is actually false, as it stands. If p\mid a, then x^2\equiv a\pmod p has infinitely many solutions.
    Any congruence with a solution has infinitely many solutions in \mathbb{Z}. When a congruence problem says "has two solutions" they mean two solutions that are distinct modulo the number you are working. If you want to be a little more formal then you can say x^2 = a has zero,one, or two solutions in \mathbb{F}_p.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Quote Originally Posted by ThePerfectHacker View Post
    Any congruence with a solution has infinitely many solutions in \mathbb{Z}. When a congruence problem says "has two solutions" they mean two solutions that are distinct modulo the number you are working. If you want to be a little more formal then you can say x^2 = a has zero,one, or two solutions in \mathbb{F}_p.
    yeah sorry, it's worded real weird.

    "solutions mod p" is grouped together, not just solutions. It took me a while to understand it (if I even do fully, time will tell.) But like PerfectHacker points out it's not asking for over \mathbb{Z}
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Okay, so you want solutions in \{1,\ldots,p-1\}\pmod p. Now I know.

    Let’s analyse the problem this way. Either x^2\equiv a\pmod p has no solutions or there is at least one solution in \{1,\ldots,p-1\}. In the first case, we are done; there is nothing to prove. So we’ll suppose there is at least one solution.

    Note that if x_0\in\{1,\ldots,p-1\} is one solution, then p-x_0\in\{1,\ldots,p-1\} is another solution. Moreover, as p>2, x_0\ne p-x_0, otherwise we would have p=2x_0, which is impossible as p is odd. Hence there are at least two solutions in \{1,\ldots,p-1\}. if any solutions exist at all. This would also answer your last query, namely one of them has to be less than or equal to \frac{p-1}2, as it is not possible for both x_0 and p-x_0 to be greater than \frac{p-1}2.

    We still need to show that there are no more than 2 solutions. For this, we use a bit of field theory. Consider the polynomial x^2-a in \mathbb Z/p\mathbb Z[x]. As \mathbb Z/p\mathbb Z is a field, \mathbb Z/p\mathbb Z[x]. is a unique-factorization domain. In a UFD, any polynomial of degree n cannot have more than n roots. Hence the quadratic polynomial x^2-a can have at most 2 roots modulo p. Hence there are at most 2 solutions to the equation x^2\equiv a\pmod p.

    Combining the results, we see that x^2\equiv a\pmod p has exactly 2 solutions whenever it is solvable.
    Last edited by JaneBennet; April 3rd 2009 at 03:16 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Quote Originally Posted by JaneBennet View Post
    We still need to show that there are no more than 2 solutions. For this, we use a bit of field theory. Consider the polynomial x^2-a in \mathbb Z/p\mathbb Z[x]. As \mathbb Z/p\mathbb Z is a field, \mathbb Z/p\mathbb Z[x]. is a unique-factorization domain. In a UFD, any polynomial of degree n cannot have more than n roots. Hence the quadratic polynomial x^2-a can have at most 2 roots modulo p. Hence there are at most 2 solutions to the equation x^2\equiv a\pmod p.

    Combining the results, we see that x^2\equiv a\pmod p has exactly 2 solutions whenever it is solvable.
    Not too informed in field theory, as it was only touched on one day of class. We never proved the fact of the polynomial n having at most n roots modulo p, YET
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 29th 2011, 07:41 AM
  2. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 18th 2011, 09:23 PM
  3. Congruence problem with gcd
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 9th 2009, 12:18 AM
  4. Congruence problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 24th 2008, 10:54 AM
  5. Congruence problem with LCM
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 19th 2007, 12:55 PM

Search Tags


/mathhelpforum @mathhelpforum