Originally Posted by
maria_stoeva Hi all,
I can't solve this.
x = 18^-1 mod 31
I know that I have to use thew reverse euclidean algorithm but I don't see how since 1/18 is not a integer
Thanks
ThePerfectHacker has a very neat solution.
But in case you ever need to know how to do the inverse GCD,
you still need to do the forward GCD.
So
Code:
31 = 18 + 13
18 = 13 + 5
13 = 2*5 + 3
5 = 1*3 + 2
3 = 1*2 + 1
2 = 2*1 + 0
As you can can see the gcd(18,31) = 1
And by the theorem of the gcd, you can find integers u,v such that
1 = u*31 + v*18
So, the algorithm now in reverse:
Code:
3 = 1 * (2) + 1
rearranging
1 = (3) - 1(2) and from the line before that 2 = 5 - 3
1 = (3) - 1(5 -3)
1 = 2*(3) - 1*(5) and from the line before that 3 = 13 - 2*5
1 = 2*(13 - 2*5) - 1*5
1 = 2*13 -5*5 and from the line before that 5 = 18 - 13
1 = 2 * 13 - 5*(18 -13)
1 = 7*13 - 5 * 18 and from the line before that 13 = 31 - 18
1 = 7*31 - 12 * 18
1 = 7*31 + ( -12)*(18)
Now in modulo 31,
1= (-12) * 18
1 = 19 * 18
which is the same answer as before.
The hardest part of modulo arithmetic is realizing that there is no such thing as division, but only multiplicative inverse.
and that 18^-1 is not 0.05555555.
It is true if you consider the real numbers, but not in this case.