# Thread: [SOLVED] Linear Congruences - Classes of Solutions

1. ## [SOLVED] Linear Congruences - Classes of Solutions

For linear congruences of the form

$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 $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:

$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 $3x + 9 y = 6$ we get $x = 2 + 3t$, where $t \in \mathbb{Z}$ and $0 \leq t \leq 2$

So, then $x \equiv 2 (\bmod 9)$, $x \equiv 5 (\bmod 9)$, $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.

2. Originally Posted by Paperwings
However, I did a problem in the book and the answer said that there are three classes of solutions:

$3x \equiv 6 (\bmod 9)$
Note that $2$ is a solution and $3=\gcd(3,9)$ therefore, $2, 2+\tfrac{9}{3}, 2 + 2\cdot \tfrac{9}{3}$ are solutions.

Yes, the number of solutions, up to congruences, is equal to the the gcd.

3. Ah, I see. Thank you ThePerfectHacker