finding inverse of $x\bmod y$

I am working through a review problem asking to find the inverse of
$4\bmod 9 $.
Through examples I know that I first need to verify that the gcd is equal to 1 and write it as a linear combination of 4 and 9 to find the inverse. I can do this in just one step:

gcd(4,9)
9 = 2 * 4 + 1
1 = 9 - 2 * 4

This would suggest that the inverse is 1 if I am understanding this correctly. However, the solution manual doesn’t show the work but says the LC should actually be

1 = 7 * 4 - 3 * 9

making the answer to the question 7.

Can anyone explain to me what is going on here and how to properly find the inverse?
Thanks!

P.S. wish I could add tags for congruency, gcd, and inverse. I can’t believe their isn’t an inverse tag already 🙁

Solutions Collecting From Web of "finding inverse of $x\bmod y$"

I know you’ve already gotten lots of responses, but instead of trying to fit responses into the comments under an answer I thought I’d just reiterate exactly why you need to do what you’re doing.

An inverse to $4 \mod 9$ is an integer $a$ such that $4a \equiv 1 \mod 9$. If we rewrite this, it means precisely that $9| (4a-1)$, or that there is another integer $b$ so that $9b = 4a-1$. What this says is that you need to find integer solutions to $4x-9y=1$. If you find that $x=a$ and $y=b$ works then $a$ is an inverse.

So what you do to solve something like this is run the Euclidean algorithm for $9$ and $4$, and then “reverse” the steps.

$9=4\cdot 2 + 1$, so it is actually over in 1 step in this case. Just subtract over to get $9-4\cdot 2 = 1$, or in the form we wrote it above $4\cdot (-2)-9\cdot (-1)=1$. So a solution is $x=-2$ and $y=-1$ and we said the $x$-value was the inverse, so the inverse is $-2\mod 9$.

Hopefully if you understand the process of why you’re doing these things, then if you get confused about which one is which on the final you can always just rederive it from these steps.

$-2$ is congruent to $7$ mod $9$. Your arithmetic steps are correct, but the conclusion should be that the congruence class of $-2$ is the inverse of $4$ mod $9$, and you probably want to use representatives in $\{1,2,3,4,5,6,7,8\}$ for your inverses, for simplicity, by adding appropriate multiples of $9$.

HINT $\ $ Congruences preserve inverses, i.e. $\rm\ A\equiv a\ \Rightarrow\ A^{-1}\equiv a^{-1}\:.\ $ This follows from the fact that congruences preserve products, i.e. it’s the special case $\rm\: AB \equiv 1\: $ in this congruence product rule

LEMMA $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A-a,\:\:\ B-b\ \Rightarrow\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB – ab $

This congruence product rule is at the heart of many other similar product rules, for example Leibniz’s product rule for derivatives in calculus, e.g. see my post here.

1/4 = 4/16 = 4/7 = 8/14 = 8/5 = 16/10 = 16/1 = 16 = 7.

Note that in the first step I multiplied the numerator and denominator by 4 instead of 3. That is because 3 is not co-prime with 9.

Using Gauss Fraction Method: 1/4 = 2/8 = 2/(-1) = -2 = 7

It is true that x = -2, but if you want to make that -2 a positive number you should do this:

  • x = -2
  • -2 ≡ 7 (mod 9)

so 7 is the inverse.