# Proving modular implicaton

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)

-
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

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}$.