I'm getting familiar with solving equations with modulo. After some trial and error and getting help on this website, I've found this method works.
Given the following equation $$ax \equiv b \pmod{c}$$
- Establish whether it has a solution
- Find the GCD between $a,b$ and simplify the equation if needed
- Rewrite the CGD as $pa + qb$ for some $p,q \in \mathbb{Z}$ as per Bezout's identity
- Multiply all the terms by the number $p$ found. $p$ is going to be the inverse of $a$ modulo $c$, so the equation will now be $x \equiv pb \pmod{c}$
- Substitute $pb$ with its modulo from the division by $c$
- The equation will now be in the form $x\equiv b'\pmod{c}$ and that's the set of the solutions
I am after a formal explanation of why, in step 4, the coefficient of $a$ in Bezout's identity is, in fact, its inverse in set of integers modulo $c$.
Should you find yourself having to write a justification in, say, a test, what would you write?