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 .