- #1

- 207

- 0

## 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 cant 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.