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.
No comments:
Post a Comment