2

I'm trying to find the multiplicative inverse of $10$ modulo $27$ using the extended euclidean algorithm and Bezout's Identity. Using euclids algorithm I find that gcd$(27,10)=1$, and the extended version gives me $$1=\text{gcd}(27,10)=27\cdot 3+10\cdot(-8)$$ Since the multiplicative inverse has to be positive (in the set $\{0,\ldots ,26\}$), i can't use $-8$. How do I find a positive integer $x$ such that the above equation holds when replacing $-8$ with $x$? I've read a couple of posts here regarding this problem, but they seem a bit confusing.

Answers are greatly appreciated!

Silent Bat
  • 21

1 Answers1

2

$-8$ is congruent to $19$ modulo $27$. So $19$ is the multiplicative inverse of $10$ modulo $27$.

Edit: (Addressing questions in comments).

You used the Euclidean algorithm to show that $$ 1 = 27\times 3 + 10 \times (-8)$$

But then, $$ 1 = 27 \times (3 - 10n) + 10 \times(-8 + 27n)$$ for any $n \in \mathbb N$.

Picking $n = 1$, we have $$ 1 = 27 \times (-7) + 10 \times 19$$

Hence $$ 1 \equiv 10 \times 19 \ {\rm mod } \ 27.$$

Kenny Wong
  • 32,192
  • Well, that is right, but what is the procedure that I can use to get from -8 to 19? There has to be logical steps that lead to the right answer. If you're for example working with large numbers, such a procedure would be really useful. – Silent Bat Jul 20 '20 at 22:37
  • @SilentBat I suppose you can add multiple of $27$ onto $-8$ until you get something that is between $0$ and $26$? – Kenny Wong Jul 20 '20 at 22:41
  • Okay that makes sense. But I'm still trying to understand why this works. Obviously I can verify that 19 indeed satisfies the equality. But is there a general proof or something similar that justifies the fact that adding multiples of the modulus (here 27) gives me the inverse or in general a coefficient that satisfies the equality? – Silent Bat Jul 20 '20 at 22:47
  • @SilentBat See the edits - do they help? – Kenny Wong Jul 20 '20 at 23:08
  • That is really clever, and it makes totally sense! Yes, this is exactly what I was looking for, thank you. – Silent Bat Jul 21 '20 at 09:42