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 , where a,b, and c are coprime. Dividing each side by
, we get
. To simplify
, 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
such that
. We keep doing this until the denominator is 1.
Example: Find if
.
Solution: Using Gauss's algorithm, we have
. We find we must multiply it by
. This gives us
, which simplifies to
when taken mod 7. Our number to multiply by is now 4. We get
, which is 4. Therefore
.
To find inverses, we can use the same process, but with .