reverse euclidean algorithm

maria_stoeva · #1 $Old$ 11-18-2008, 02:21 PM

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

JaneBennet · #2 $Old$ 11-19-2008, 12:28 PM

It could be a badly written way of saying $18x\equiv1\!\!\!\pmod{31}.$

ThePerfectHacker · #3 $Old$ 11-19-2008, 07:51 PM

$18x\equiv 1 (\bmod 31)$
$18x \equiv -30(\bmod 31)$
$3x\equiv -5(\bmod 31)$
$3x\equiv -36(\bmod 31)$
$x\equiv -12(\bmod 31)$
$x\equiv 19(\bmod 31)$

Soroban · #4 $Old$ 11-20-2008, 10:08 AM

Hello, maria_stoeva!

Here's a very primitive solution . . .

Quote:

Solve: . $x \:\equiv \:18^{-1}\pmod{31}$

We have: . $18x \:\equiv \:1 \pmod{31}$

That is: . $18x - 1 \:=\:31a\:\text{ for some integer }a$

Solve for $x\!:\;\;x \:=\:\frac{31a+1}{18} \:=\:a + \frac{13a+1}{18}\;\;{\color{blue}[1]}$

Since $x$ is an integer, $13a + 1$ must be a multiple of 18.
. . That is: . $13a + 1 \:=\:18b\:\text{ for some integer} b$

Solve for $a\!:\;\;a \:=\:\frac{18b-1}{13} \:=\:b + \frac{5b-1}{13}\;\;{\color{blue}[2]}$

Since $a$ is an integer, $5b-1$ must be a multiple of 13.
. . That is: . $5b-1 \:=\:13c\:\text{ for some integer } c$

Solve for $b\!:\;\;b \:=\:\frac{13c+1}{5} \:=\:2c + \frac{3c+1}{5} \;\;{\color{blue}[3]}$

Since $b$ is an integer, $3c+1$ must be a multiple of 5.
. . This first happens when: $c = 3$

Substitute into [3]: . $b \:=\:2(3) + \frac{3(3)+1}{5} \quad\Rightarrow\quad b\:=\:8$

Substitute into [2]: . $a \:=\:8 + \frac{5(8)-1}{13} \quad\Rightarrow\quad a \:=\:11$

Substitute into [1]: . $x \:=\:11 + \frac{13(11)+1}{18} \quad\Rightarrow\quad\boxed{ x \:=\:19}$

Therefore: . $19 \:\equiv\:18^{-1} \pmod{31}$

thejinx0r · #5 $Old$ 11-30-2008, 04:27 PM

Quote:

Originally Posted by maria_stoeva $View Post$

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.