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.
Best Answer
If $sa+tm=1$, then $sa+tm$ and $1$ are the same number. Thus, they will have the same remainder when divided by $m$, which is precisely what we mean when we say $sa + tm \equiv 1 \pmod{m}$.