Finding the Inverse of a Number in a Finite Field

[moo5003]

Homework Statement

Suppose that m = 1 mod b. What integer between 1 and m-1 is equal to b^(-1) mod m?

The Attempt at a Solution

m = 1 mod b means that:

m = kb + 1 for some integer k

Let x be the inverse of b mod m, note: x exists since b and m must be coprime due to the previous statement.

xb = 1 mod m

thus: xb = gm + 1 for some integer g.

Now this is were I have little success. I can't seem to manipulate anything to my advantage and I'm unsure how to proceed.

I did find x = (m+1)/b but that is not always an integer. Thanks for any help you can provide.

 

[Hurkyl]

Well, you don't seem to have made use of the fact that m = 1 mod b...

 

[moo5003]

I thought I used that fact when using the statement

m = kb + 1 for some integer k, unless I'm missing something else. Little tired, but I will come back to it tomorrow.