For linear congruences of the form
Let gcd(a, c) = d. I know that if d = 1, then there is one unique class of solutions.
If , there there is no solutions.
However, I did a problem in the book and the answer said that there are three classes of solutions:
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 we get , where and
So, then , ,
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.