Linear congruence equations - how to determine the solutions

Question

How can I determine the solutions of linear congruence equation solved using extended euclidean algorithm?

For example:

$$13x \equiv 12 \pmod{15}$$

$$\text{GCD}(13,15)=1=7(13)-6(15)$$

What's next?

Answer 1

HINT:

We need $13x=12+15y$ for some integer $y$

$\implies 13x-15y=12=12\{7\cdot13-6\cdot15\}$

$\implies 13(x-84)=15(y-72)\implies \frac{13(x-84)}{15}=y-72$ which is an integer

$\implies 15$ divides $13(x-84)$

$\implies 15$ divides $(x-84)$ as $(13,15)=1$

$\implies x\equiv84\pmod{15}\equiv9$

Answer 2

Using the Euclidean algorithm, you found that $7(13)-6(15)=1$. That is, $$ (7)(13) \equiv 1 \pmod{15} $$ It follows that $$ (12\times7)(13) \equiv 12 \pmod{15} $$ Or in terms of the original question: the equation $13x \equiv 12 \pmod{15}$ is solved by $x = 12\times7=84\equiv9 \pmod{15}$. That this is in fact a unique solution mod $15$ follows from the fact that $13$ and $15$ are relatively prime.