0
$\begingroup$

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?

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

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<n$ then it just follows from the fact that you can always take $0\leq c<n$ 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\}$.

$\endgroup$
2
  • $\begingroup$ 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).' $\endgroup$
    – hephaes
    Sep 29 '18 at 10:12
  • $\begingroup$ 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$. $\endgroup$
    – Mark
    Sep 29 '18 at 10:14

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.