7
$\begingroup$

Here I am trying to find the multiplicative inverse of 19 respect to 29.

$$19x \equiv 1 \pmod{29} $$

What I tried

\begin{align*} 29 &= 1(19) + 10\\\ 19 &= 1(10) + 9\\\ 10 &= 1(9) + 1. \end{align*}

From backtracking, I came up with the

\begin{align*} 1 &= 2(29) - 3(19)\\\ \end{align*}

However, 3 is not a multiplicative inverse of the 29. Where am I making a mistake?

I looked many answers including this answer; however, couldn't figure out my mistake.

$\endgroup$
  • 3
    $\begingroup$ The inerse is $-3$ here, which is congruent to $26$ $\endgroup$ – Peter Oct 12 at 14:02
  • $\begingroup$ Instead of rote rule application to the Bezout identity you should remember its genesis, viz. reducing $\, a n + b m = 1\,$ modulo $n$ yields $\,bm\equiv 1\,$ so $\, m\equiv b^{-1}\pmod{\!n}.\,$ In your case $\, b = -3\,$ (you forgot to include the sign). Generally one should always strive to remember the conceptual heart of the matter vs. rote rules. $\endgroup$ – Bill Dubuque Oct 12 at 14:17
  • 1
    $\begingroup$ Btw, it is easier and far less error-prone to forward propagate the equations, e.g. see here and here. $\endgroup$ – Bill Dubuque Oct 12 at 15:26
  • $\begingroup$ @BillDubuque Do you agree with my suggested choice of duplicate? $\endgroup$ – Jyrki Lahtonen Oct 13 at 9:23
  • $\begingroup$ FWIW I haven't downvoted on the answers here even though I am tempted, and encourage the practice. A site this age has certainly covered all the nooks and corners of Euclid, so it behooves 20k+ users to search first. When they obviously don't, a downvote is A) a reminder, B) a gesture of strong disproval. $\endgroup$ – Jyrki Lahtonen Oct 13 at 9:25
3
$\begingroup$

What you have found indeed is that $-3\equiv 26$ is the multiplicative inverse of $19$ $\mod 29$.

$\endgroup$
  • $\begingroup$ Since this is the first answer, I want to give a credit to this one. I have only one question. Why $-3\equiv 26$ $\endgroup$ – Emrah Sariboz Oct 12 at 14:17
  • 1
    $\begingroup$ @user109067 Because $\,29\,$ divides $\,-3-26\ \ $ $\endgroup$ – Bill Dubuque Oct 12 at 14:21
  • 2
    $\begingroup$ @user109067 Because $-3+29=26$ $\endgroup$ – user Oct 12 at 14:22
  • $\begingroup$ sorry still not clear. What you mean 29 divides -3? $\endgroup$ – Emrah Sariboz Oct 12 at 14:23
  • $\begingroup$ @user109067 $\ -3-26 = -29\ $ is divisible by $29.\ $ Recall $\ a\equiv b\pmod n\ $ means $a-b$ is divisible by $n\ \ $ $\endgroup$ – Bill Dubuque Oct 12 at 14:24
3
$\begingroup$

You're almost there! Multiply both sides by $-3$ and you have $$-57x\equiv -3\pmod {29}\\x\equiv-3\equiv26\pmod{29}$$

$\endgroup$
3
$\begingroup$

Reducing your backtracking result modulo $29$, it becomes $$ 1\equiv -3\cdot 19\pmod{29} $$ Which is to say, the multiplicative inverse of $19$ is $-3$.

$\endgroup$
  • 1
    $\begingroup$ This is a correct explanation, so why was it downvoted? $\endgroup$ – Bill Dubuque Oct 12 at 14:07
  • $\begingroup$ @BillDubuque The ways of the downvote fairies are ineffable. But yeah, I'm wondering that too. I mean, there are other correct answers here, but I feel my approach is at least a tiny bit distinct. $\endgroup$ – Arthur Oct 12 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.