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