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 :(
\mod
is an operator used in CS;x mod y
means the (nonnegative) remainder when dividing $x$ by $y$; by contrast,\pmod
is the name of an equivalence relation, which consists of the symbol $\equiv$ and the(mod y)
. Second: the names of operators and functions in mathematics follows the following convention: if they are one or two symbols long, then italics are prefered; if they are three or more symbols long, then roman typeface should be used. So $x\ mod\ y$ does not follow that convention; although it is probably better to use\mathrm{mod}
than\mod
; I did now $\endgroup$\mod
is one of my peeves that I raise whenever I proofread/review/referee papers. $\endgroup$