Thread: [SOLVED] Linear Congruences - Classes of Solutions

1. [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.

2. Originally Posted by Paperwings
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)$
Note that $\displaystyle 2$ is a solution and $\displaystyle 3=\gcd(3,9)$ therefore, $\displaystyle 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