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
Hello, maria_stoeva!
Here's a very primitive solution . . .
Solve: .$\displaystyle x \:\equiv \:18^{-1}\pmod{31}$
We have: .$\displaystyle 18x \:\equiv \:1 \pmod{31}$
That is: .$\displaystyle 18x - 1 \:=\:31a\:\text{ for some integer }a$
Solve for $\displaystyle x\!:\;\;x \:=\:\frac{31a+1}{18} \:=\:a + \frac{13a+1}{18}\;\;{\color{blue}[1]}$
Since $\displaystyle x$ is an integer, $\displaystyle 13a + 1$ must be a multiple of 18.
. . That is: .$\displaystyle 13a + 1 \:=\:18b\:\text{ for some integer} b$
Solve for $\displaystyle a\!:\;\;a \:=\:\frac{18b-1}{13} \:=\:b + \frac{5b-1}{13}\;\;{\color{blue}[2]}$
Since $\displaystyle a$ is an integer, $\displaystyle 5b-1$ must be a multiple of 13.
. . That is: .$\displaystyle 5b-1 \:=\:13c\:\text{ for some integer } c$
Solve for $\displaystyle b\!:\;\;b \:=\:\frac{13c+1}{5} \:=\:2c + \frac{3c+1}{5} \;\;{\color{blue}[3]}$
Since $\displaystyle b$ is an integer, $\displaystyle 3c+1$ must be a multiple of 5.
. . This first happens when: $\displaystyle c = 3$
Substitute into [3]: .$\displaystyle b \:=\:2(3) + \frac{3(3)+1}{5} \quad\Rightarrow\quad b\:=\:8$
Substitute into [2]: .$\displaystyle a \:=\:8 + \frac{5(8)-1}{13} \quad\Rightarrow\quad a \:=\:11$
Substitute into [1]: .$\displaystyle x \:=\:11 + \frac{13(11)+1}{18} \quad\Rightarrow\quad\boxed{ x \:=\:19}$
Therefore: .$\displaystyle 19 \:\equiv\:18^{-1} \pmod{31}$
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
As you can can see the gcd(18,31) = 1Code:31 = 18 + 13 18 = 13 + 5 13 = 2*5 + 3 5 = 1*3 + 2 3 = 1*2 + 1 2 = 2*1 + 0
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:
Now in modulo 31,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)
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.