# Proof that the inverse exists in the group of units of the additive group of modulo n

Here is a statement I am trying to prove, that will allow me to prove the inverse exists in the group of units of the additive group of modulo n.

Let $$n\in \mathbb{N}$$ and $$a\in\mathbb{Z}$$. If gcd$$(a,n) = 1$$, there exists $$0\leq b < n$$ such that $$ab \equiv 1$$ (mod $$n$$), and gcd$$(b,n) = 1$$.

The proof I can think of is this:

Since $$(a,n) = 1$$, there exists some $$c_1$$ and $$c_2 \in \mathbb{Z}$$ such that $$c_1a+c_2n = 1$$. Then $$c_1a = -c_2n + 1$$, and this means $$c_1a \equiv 1$$ (mod $$n$$). Consider the ideal $$J$$ generated by $$c_1$$ and $$n$$, which is J := $$\{x_1c_1 + x_2n : x_1, x_2 \in \mathbb{Z} \}$$, then $$1 \in J$$, and since $$1$$ is the smallest positive integer, it must be the generator for $$J$$ and hence it is the greatest common divisor for $$c_1$$ and $$n$$.

But this proof does not consider the inequality. So my question is: from where does the inequality arise?

• Which inequality are you talking about? Sep 29 '18 at 10:07
• $0≤b<n$ that appears in the statement. Sep 29 '18 at 10:07

I don't understand the problem. You already proved that there exists $$b\in\mathbb{Z}$$ such that
$$ab\equiv 1$$(mod $$n$$) and $$gcd(b,n)=1$$. If your question is why $$0\leq b then it just follows from the fact that you can always take $$0\leq c such that $$c\equiv b$$(mod $$n$$) and then $$ac\equiv ab$$(mod $$n$$). So without loss of generality you can say $$b$$ itself is in $$\{0,1,...,n-1\}$$.
• Thank you very much. My question is about why should $b$ obeys $0≤b<n$, but I think your answer has completely solved the problem. It seems I just overlook the fact that 'you can always take 0≤c<n such that c≡b(mod n) and then ac≡ab(mod n).' Sep 29 '18 at 10:12
• Yes. The specific $b$ you found might not satisfy $0\leq b<n$, but multiplication mod $n$ doesn't depend on which number you choose to represent the equivalence class, so you can always take one from $\{0,1,...,n-1\}$ which is congruent to $b$.