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
    9
    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
    9
    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
    9
    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