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$ .

Page

Toolbox

Search

Gauss's algorithm