[SOLVED] Linear Congruences - Classes of Solutions

For linear congruences of the form

$\displaystyle ax \equiv b (\bmod c) $

Let gcd(a, c) = d. I know that if d = 1, then there is one unique class of solutions.

If $\displaystyle d \nmid b $, there there is no solutions.

However, I did a problem in the book and the answer said that there are three classes of solutions:

$\displaystyle 3x \equiv 6 (\bmod 9) $

By the Euclidean Algorithm

9 = 3*3 + 0

Thus, (3, 9) = 3 | 6, *then there are three solutions*. This part I do not understand.

It follows by solving the Diophantine equation $\displaystyle 3x + 9 y = 6 $ we get $\displaystyle x = 2 + 3t $, where $\displaystyle t \in \mathbb{Z} $ and $\displaystyle 0 \leq t \leq 2 $

So, then $\displaystyle x \equiv 2 (\bmod 9) $, $\displaystyle x \equiv 5 (\bmod 9) $, $\displaystyle x \equiv 8 (\bmod 9) $

Is there a theorem that states how many solutions there are? From the problem, I believe that the number of solutions is equal to the gcd.