# Infinitely many pairwise congruent solutions modulo $c$?

The following is from my number theory textbook..

In particular, there exists an integer $c$ such that there are infinitely many solutions to the equation $x^2 - dy^2 = c$. Since there are only a finite number of classes modulo $c$, there even exist infinitely many pairwise congruent solutions modulo $c$.

Why is the second sentence true? It's not very clear to me...

• Maybe an example will be illuminating. Take $c=10$, so that being congruent modulo $10$ just means having the same last digit (for positive integers). If you have an infinite set of positive integers, do you agree that there must be some last digit that infinitely many of them have? – Greg Martin Oct 19 '15 at 3:51

I assume here you want $d>0$, otherwise this is clearly false as a diophantine problem. Consider breaking all solutions into sets of distinct solutions,
$$S_{a,b}\{(x_{i},y_{i})\in\Bbb Z^2 : x_i\equiv a\mod c, y_i\equiv b\mod c\}\qquad 1\le a,b\le c.$$
Clearly all solutions $(x,y)$ fall into some $S_{a,b}$, and since
$$\bigsqcup_{a,b} S_{a,b}=S$$
is a finite union, one of the $S_{a,b}$ must be infinite, hence the result in the problem.