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 :(