0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Feb 11 '15 at 5:57
  • $\begingroup$ Where did tm go? $\endgroup$ – committedandroider Feb 11 '15 at 6:01
  • 1
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Feb 11 '15 at 6:07
  • $\begingroup$ @AndréNicolas That comment should be the answer :) Thanks for making it clear $\endgroup$ – committedandroider Feb 12 '15 at 0:37
  • $\begingroup$ As long as comments and answer together make everything clear, task accomplished. $\endgroup$ – André Nicolas Feb 12 '15 at 1:14
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Oh because 1 - 1 is 0, which can be equal to any k * m $\endgroup$ – committedandroider Feb 11 '15 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.