# How does author reach step of $sa + tm \equiv 1 \pmod m$?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications

Theorem 1

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 $\overline a$ less than m that is an inverse of $a$ modulo $m$ and every other inverse of $a$ modulo $m$ is congruent to $\overline a$ modulo $m$.

Proof: By Theorem 6 of Section 4.3, because $\text{gcd}(a,m)=1$, there are integers $s$ and $t$ such that $$sa+tm=1$$

This implies that $$sa+tm\equiv1 \pmod m$$

Here is theorem 6 of Section 4.3:

Theorem 6

Beloit's Theorem: If $a$ and $b$ are positive integers, then there exist integers $s$ and $t$ such that $\text{gcd}(a,b)\equiv sa+tb$.

The first part of the proof, "because $\text{gcd}(a,m)=1$" makes sense because the conditional statement includes the statement that "$a$ and $m$ are relatively prime integers", meaning that their gcd is $1$. I don't get the step that the author uses to get from

$$sa + tm = 1$$

to

$$sa+tm\equiv1 \pmod m$$

Can someone explain how the author got to that step? Can someone give a general overview of inverse of modulo as well? I don't really understand it from my book. I understand modulus: $7 \bmod 3$ is $1$ but what would inverse of $7 \bmod 3$ get you?

• I would prefer to say and therefore $sa\equiv 1\pmod{m}$. This follows from $sa+tm=1$, since that says that $sa-1$ is a multiple of $m$. – André Nicolas Feb 11 '15 at 5:57
• Where did tm go? – committedandroider Feb 11 '15 at 6:01
• It was explained above. We have $sa+tm=1$ and therefore $sa-1=-tm$, so $sa-1$ is a multiple of $m$, so $sa-1\equiv 0\pmod{m}$, so $sa\equiv 1\pmod{m}$. – André Nicolas Feb 11 '15 at 6:07
• @AndréNicolas That comment should be the answer :) Thanks for making it clear – committedandroider Feb 12 '15 at 0:37
• As long as comments and answer together make everything clear, task accomplished. – André Nicolas Feb 12 '15 at 1:14

Hint: $1 = 1 \pmod m$ for any $m \in \mathbb{N}$.