Difference between revisions of "Gauss's algorithm"
Idk12345678 (talk | contribs) (Created page with "Gauss's algorithm is an algorithm used to find modular arithmetic inverses and solutions to modular arithmetic equations. Let us have the equation <math>ax \equiv b \pmod c</m...") |
(No difference)
|
Latest revision as of 16:30, 27 June 2024
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 
.
