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

1. ## 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!

2. Originally Posted by poserp
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.

3. 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?

4. Originally Posted by poserp
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.

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.