From K Rosen's Discrete Maths,
Theorem: If a and m are relatively prime integers and m > 1, then an inverse of a modulo m exists. Furthermore, this inverse is unique modulo m. (That is, there is a unique positive integer a less than m that is an inverse of a modulo m and every other inverse of a modulo m is congruent to a modulo m.)
Proof:
By Theorem 6 of Section 4.3,
because gcd(a, m) = 1, there are integers s and t such that
sa + tm = 1.
This implies that, sa + tm ≡ 1 (mod m).
Because t m ≡ 0 (mod m), it follows that sa ≡ 1 (mod m).
Consequently, s is an inverse of a modulo m.
I am struggling a lot and have gone through theorems given in the chapter multiple times, I'm unable to figure out how we can say,
sa + tm = 1.
This implies that, sa + tm ≡ 1 (mod m).
I realise that this a rookie question but if you can give me some link or even a theorem no. that would be of great help.
