Page 1 of 2 12 LastLast
Results 1 to 15 of 18
Like Tree1Thanks

Math Help - equation soluble

  1. #1
    Junior Member
    Joined
    Oct 2013
    From
    LONDON
    Posts
    29

    equation soluble

    p is an odd prime

    (a) show that x^2+y^2+1=0 (mod p) is soluble

    (b)
    show that x^2+y^2+1=0 (mod p) is soluble for any squarefree odd m

    For (a)
    hint given : count the integers in {0,1,2,...,p-1} of the form x^2 modulo p and
    those of the form -1-y^2 modulo p

    can anyone help me ?? thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,835
    Thanks
    705

    Re: equation soluble

    What do you need help with? Are you having trouble applying the hint? Do you have any work done that we can look at? If you are looking for a place to start, choose a couple values for p and see what is going on. For example, check out the integers in {0,1,2} of the form x^2 modulo 3 and those of the form -1-y^2 modulo 3. Try it for 5 and 7 also. Do you notice any patterns? Try to show that the number of integers of that form is greater than \dfrac{p-1}{2}. Then by the pigeonhole principle, there must be some x^2 and -1-y^2 that are congruent modulo p.

    For (b), what is m?
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2013
    From
    LONDON
    Posts
    29

    Re: equation soluble

    i had proved that that are (p+1)/2 integers u in {0,1,2,...,p-1} s.t. u=x^2(mod p) for some x in the previous part , i am wondering should i use this statement somewhere?? i tried some primes p but i still cannot get the connection, and for m is an odd squarfree integer(the squarfree integer is one divisible by no perfect square)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,835
    Thanks
    705

    Re: equation soluble

    Quote Originally Posted by Sonifa View Post
    i had proved that that are (p+1)/2 integers u in {0,1,2,...,p-1} s.t. u=x^2(mod p) for some x in the previous part , i am wondering should i use this statement somewhere?? i tried some primes p but i still cannot get the connection, and for m is an odd squarfree integer(the squarfree integer is one divisible by no perfect square)
    Let A = \{u \in \{0,1,2,\ldots, p-1\}\mid \exists x \in \mathbb{Z}, u \equiv x^2 \pmod{p}\}, B = \{v \in \{0,1,2,\ldots, p-1\} \mid \exists y \in \mathbb{Z}, v \equiv -1-y^2 \pmod{p}\}. Then, from your previous part, you have |A| = |B| = \dfrac{p+1}{2}. The set \{0,1,2,\ldots,p-1\} has p elements. So, |A|+|B| = \dfrac{p+1}{2} + \dfrac{p+1}{2} = p+1, but |A\cup B| \le p, hence |A\cap B|\ge 1.

    For part (b), I still don't understand what m is. You don't use m in the problem's statement.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2013
    From
    LONDON
    Posts
    29

    Re: equation soluble

    Sorry , i made a mistake for typing. The statment should be :

    show that x^2+y^2+1=0 (mod m) is soluble for any squarefree odd m.

    And why is B has order (p+1)/2 . Thanks for ur part a) , I was looking for the order of B, now it,s OK for me.
    Last edited by Sonifa; October 20th 2013 at 03:34 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,835
    Thanks
    705

    Re: equation soluble

    B has order (p+1)/2 because A does. If there are (p+1)/2 different integers u in {0,1,2,...,p-1} with u = x^2 (mod p), then there are (p+1)/2 different integers v = -u (mod p), and then there are (p+1)/2 different integers v' = -1-u (mod p).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2013
    From
    LONDON
    Posts
    29

    Re: equation soluble

    Yes, for (b) since m is squarefree odd number,then i write m as the prime factorisation m=p1p2p3.... (since no square) then by a) for every prime pi, it has a solution. I stopped here, how to deduce it has solution for their product m???
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,835
    Thanks
    705

    Re: equation soluble

    This is just a guess, but try this: Find solutions for x^2+y^2+1 \equiv 0 \pmod{p_i} for each prime in the prime factorization of m. Then use the Chinese Remainder Theorem to find solutions in m.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2013
    From
    LONDON
    Posts
    29

    Re: equation soluble

    but how to ensure that exist a solution for x and y s.t. x^2+y^2+1=0 (mod pi) for all i ?? if we can prove such x y exist then by chinese remaider theorem we get the resault.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,835
    Thanks
    705

    Re: equation soluble

    You already proved the existence of solutions for x and y (over the integers) s.t. x^2+y^2+1=0 (mod p_i) in part (a). Now, I am suggesting you find elements x_i,y_i of {0,1,2,...,p_i-1} such that x = x_i (mod p_i) and y = y_i (mod p_i) for each i. Then use the Chinese Remainder Theorem to find x (mod m) and y (mod m), and there will hopefully be a way to show that the result you get satisfies x^2+y+2+1 = 0 (mod m).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2013
    From
    LONDON
    Posts
    29

    Re: equation soluble

    I have the idea based on ur suggestion but i dont think it goes right.

    m=p1p2p3..pr

    by part (a) we have xi^2+yi^2+1=0 mod pi , now want x , y s.t. x=xi mod pi and y=yi mod pi for each i. if i take x=x1*x2*...*xr y=y1*y2*...yr then we satify our requirment ,

    is my idea wrong?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,835
    Thanks
    705

    Re: equation soluble

    I don't think that works out. Try m=15. Then for x_1^2+y_1^2 +1 = 0 \pmod{3}, you can choose x_1=y_1=1. For x_2^2+y_2^2+1 = 0 \pmod{5}, you can choose x_2 = 0, y_2 = 2. But, (x_1x_2)^2 + (y_1y_2)^2 + 1 = 0+4+1 = 5 \neq 0 \pmod{15}.

    How about this: Suppose m is odd, squarefree, and the product of r distinct primes. Then there are at least \dfrac{m+1}{2} distinct integers u in \{0,1,\ldots,m-1\} such that u \equiv x^2 \pmod{m} for some integer x. Proof by induction. When r=1, that is the case you just proved for part (a). Suppose the proposition holds for any number of prime factors up to r. Then let m be odd, squarefree, and the product of r+1 distinct primes. Then, given any prime factor p_i of m, you know that \dfrac{m}{p_i} satisfies the induction assumption, so by hypothesis, there must be \dfrac{m + p_i}{2p_i} integers u in \{0,...,\dfrac{m}{p_i}-1\} such that u \equiv x^2 \pmod{\dfrac{m}{p_i}} for some integer x. Can you then use the Chinese Remainder Theorem to prove the hypothesis? I am just guessing. I don't have time at the moment to fully figure this out.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,835
    Thanks
    705

    Re: equation soluble

    Oh, I know. Suppose you have x,y such that x^2+y^2+1 \equiv 0 \pmod{p_i} for all primes p_i such that p_i|m. Then, it must be that p_i | (x^2+y^2+1) for all such prime factors. That implies m divides x^2+y^2+1. So, my initial thought to find solutions x_i,y_i with x_i^2+y_i^2 +1 \equiv 0 \pmod{p_i} and then use the Chinese Remainder Theorem to find x,y should work.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Oct 2013
    From
    LONDON
    Posts
    29

    Re: equation soluble

    I am a bit confused. by (a) we know that for pi we can we can find the solution xi yi s.t. xi^2+yi^2+1=0 mod (pi) . but when we use the chinese remainder theorem, we need to find x and y first s.t. x^2+y^2+1=o (mod pi) for each pi. My point is we should ensure x y satisfy for each congruent equation (pi) then we can use chinese remaider theorem. For me , I failed to find such x y.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,835
    Thanks
    705

    Re: equation soluble

    You already did prove that in part (a). That is exactly what you proved. Given any odd prime p, there exists integers x and y with x^2+y^2+1=0 (mod p). You know m is odd, so its factors will all be odd. Then, if p_i is a factor, you just in part (a) you can find a solution. You have nothing left to prove. I don't understand what issue there is with those solutions you found.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: February 25th 2013, 09:32 PM
  2. Replies: 1
    Last Post: April 11th 2011, 01:17 AM
  3. Replies: 1
    Last Post: November 4th 2009, 09:52 AM
  4. Replies: 2
    Last Post: April 28th 2009, 06:42 AM
  5. Soluble Groups....
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 2nd 2009, 07:43 PM

Search Tags


/mathhelpforum @mathhelpforum