0

I want to find the inverse of $7 \bmod 18$. First of all i found that $gcd(7,18)=1$

Then i express the $gcd$ as a linear combination of $7$ and $18$ using Euclidian algorithm

$1=(-5)7+2(18)$

All good until now. However after that the textbook does this:

$1=(13-18)7 + 2(18)$

$1=(13)7+1(18)$

And this supposedly tell us that the inverse of $7 \bmod 18$ is $13$

Can someone explain the logic behind this? Also how come that $(13−18)7+2(18) = (13)7+1(18)$ ??

Than1
  • 331

2 Answers2

1

Modulo $18$, $-5$ and $13$ are equal, so both are the inverse of $7$. The book is just shuffling some multiples of $18$ around to get a positive $13$ as the answer.

There is also a typo. It should read : $$ 1 = (-5)7 +2(18)= (13-18)7 + 2(18)=13\times 7 + (2-7)18= 13\times 7 - 5\times 18$$

SolubleFish
  • 7,908
1

The equation that you found isn't using mod $18$ yet so once you apply it then $18$ becomes $0$ and you get $1 = (-5)7 +2(0) = (-5)7$. This shows that $-5$ multiplied by $7$ becomes $1$, they are inverses! The textbook played around with the numbers to get a positive answer ($-5 + 18 = 13$ so $-5 = 13$ mod $18$) but made a typo it seems.

David
  • 146