20-CS-472 |
Design and Analysis of Algorithms 2 |
Winter 2011 |
---|---|---|

Inverse Modulo a Number |

**Operation:**
Enter a number `m` and a number `n` in the boxes at the
top left. Click on `Start` to begin the gcd algorithm for
finding the inverse of `m` mod `n`. Repeated clicks on
the `Next` button will update an equation

R = U*m + V*nwhose values are shown on the bottom line of the applet in separate boxes. When an inverse is found, if it exists, it will appear in the box labeled

**Further details:**
Boxes `larger` and `smaller` contain the two numbers
that the algorithm is currently trying to find the greatest common
divisor for. Initially these numbers are `m` and `n`.
The box labeled `divisor` shows the number of times the
`smaller` number divides the `larger` number, and the
box labeled `remainder` shows the remainder of that division.
There are two rows of three columns that record numbers which are
used to compute new factors. Initially these are:

- left column - 1 and -1 times the divisor.
- middle column - 0 and 1
- right column - blank