[Math] How to identify an inverse of 101 modulo 4620

discrete mathematics

I use Euclidean Algorithm:

4620 = 101 * 45 + 75. long story short. I get 3 = 2 * 1 + 1. After that 2 = 1 * 2 + 0.

gcd(101,4620) = 1.

So I use back substitution.

1 = 3 – 1 * 2. Long story short, I work my way up to express the remainders as the remaining terms of the equation arriving to – 35* 4620 + 1601 * 101. How do I test which one is the inverse based on -35 * 4620 + 1601 * 101?

I tried 1601 but 1601 = 101 (modulo 4620) does not seems right because 4620 does not divide 1601 -101 or 1500.

Best Answer

I think you're confused as to what an inverse is. First, we take your equation

$$-35(4620)+1601(101)=1$$

and now look at this mod $4620$

$$1601(101)\equiv1\pmod{4620}$$

By this equation, $1601$ and $101$ are inverses of one another mod $4620$. When we multiply one by the other, the result is equivalent to $1$.