Gauss's algorithm

Gauss's algorithm is an algorithm used to find modular arithmetic inverses and solutions to modular arithmetic equations. Let us have the equation $ax \equiv b \pmod c$, where a,b, and c are coprime. Dividing each side by $a$, we get $x \equiv \frac{b}{a} \pmod c$. To simplify $\frac{b}{a}$, we multiply it by 1 as a fraction with the same numerator and denominator, and then find that mod 7. To choose what we multiply it by, we find the smallest coprime integer, w, to $c$ such that $aw > c$. We keep doing this until the denominator is 1.


Example: Find $x$ if $3x \equiv 5 \pmod 7$. Solution: Using Gauss's algorithm, we have $\frac{5}{3}$. We find we must multiply it by $\frac{3}{3}$. This gives us $\frac{15}{9}$, which simplifies to $\frac{1}{2}$ when taken mod 7. Our number to multiply by is now 4. We get $\frac{4}{8}$, which is 4. Therefore $x = 4$.

To find inverses, we can use the same process, but with $b=1$.