Results 1 to 5 of 5

Math Help - Are there an infinite number of solutions to y^2 = x^2 mod n for all composite n?

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    5

    Are there an infinite number of solutions to y^2 = x^2 mod n for all composite n?

    Just curious if there is a proof of whether or not this is true. It seems to be assumed that solutions exist, and I presume people also understand that there are more than a few solutions for all composite n, hence the quadratic sieve and other methods of factorization which essentially solve this congruence. However, I haven't run across any proofs about the existence of solutions or how many solutions potentially exist. Thanks!
    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 poserp View Post
    Just curious if there is a proof of whether or not this is true. It seems to be assumed that solutions exist, and I presume people also understand that there are more than a few solutions for all composite n, hence the quadratic sieve and other methods of factorization which essentially solve this congruence. However, I haven't run across any proofs about the existence of solutions or how many solutions potentially exist. Thanks!
    It depends how you define solution. You can just choose x=y=1,2,3,... and that would work. But you probably want solutions up to congruence mod n. In that case there are finitely many solutions.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    5
    Good point -- in this case x is not equal to y and n is a composite not of the form 2*p, where p is prime. So there are only a finite number of solutions?
    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 poserp View Post
    Good point -- in this case x is not equal to y and n is a composite not of the form 2*p, where p is prime. So there are only a finite number of solutions?
    Again if you want solutions up to congruence then yes, it must be finite.
    But if (x,y) is a solution then (x,y+n) is a solution, and (x,y+2n), (x,y+3n) are solutions. And so on. You can generate more and more. They are just all the same up to congruence.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    Posts
    5
    Oh yea, duh... You can have an infinite number of solutions to x^2 = y^2 + n, but computed modulo n each of those solutions will be less than n.

    edit: I mean, there are an infinite number of solutions to x^2 = y^2 + c*n.
    Last edited by poserp; October 23rd 2008 at 11:32 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 11th 2011, 05:22 PM
  2. infinite solutions
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 14th 2011, 05:57 AM
  3. Infinite Solutions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 11th 2009, 05:30 PM
  4. Infinite Number of Solutions
    Posted in the Algebra Forum
    Replies: 2
    Last Post: July 9th 2009, 12:09 AM
  5. Infinite Solutions
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 4th 2008, 06:49 AM

Search Tags


/mathhelpforum @mathhelpforum