Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have to prove that for $m \in \mathbb{Z_{>1}}, b \in \mathbb{Z}$ it $\exists a \in \mathbb{Z} : ab \equiv 1 (mod\;m) \Rightarrow \exists a'\in \mathbb{N}, a'<m:a'b=1 (mod\;m )$

Since we have to prove existence, we only have to find one example: I started by letting $a' = a\; mod\; m$, which ensures both $a'<m $ and $a' \in \mathbb{N}$ since rest is natural number by default.

Now I have troubles showing that the implication works in the right direction (ie. that we come by substitution from one side to another)

share|cite|improve this question
It is not ecluded that a and a' are both same. – smihael Jan 8 '13 at 20:22
I misread the question, my mistake. – JSchlather Jan 8 '13 at 20:29
up vote 0 down vote accepted

Hint: Suppose that $ab\equiv 1\pmod{m}$. By the result often called the Division Algorithm, there is a $q$ and $r$, with $0\le r\lt m$ such that $a=qm+r$. The "$r$" is the $a'$ you are looking for. It should be easy to show that $a'b\equiv 1\pmod{m}$.

More informally, this just comes down to the fact that if $m\gt 0$, then for any $a$ there is an $a'$ such that $0\le a'\le m-1$ and $a'\equiv a\pmod{m}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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