How can I prove that for modular multiplicative inverses that if $∃ $[$b$]$ ∈ℤ_n$ such that [$a$] * [$b$] = [$1$], then gcd($a,n$) =$1$?

Question

How can I prove that for modular multiplicative inverses that if $∃ $[$b$]$ ∈ℤ_n$ such that [$a$] * [$b$] = [$1$], then gcd($a,n$) =$1$?

I understand the relationship between primes and multiplicative inverses, but I am not sure how to prove that

if $∃ $[$b$]$ ∈ℤ_n$ such that [$a$] * [$b$] = [$1$], $⇒ $ gcd($a,n$) =$1$

I have some definitions to work with, but I am not sure how to fully write out the proof.

gcd($m,n$) is defined as the smallest element of the set $S$ = {$K∈N$ : $k=mx+ny$ for some $x,y∈ℤ$}.

I know that gcd($m,n$) = $1$ when they are primes.

Multiplicative Inverse for modulo is defined as [$b$]$∈ℤ_n$ if [$a$] * [$b$] = [$1$].

I can prove the converse better, but I am not quite sure how to start with $∃ $[$b$]$ ∈ℤ_n$ such that [$a$] * [$b$] = [$1$] to derive gcd($a,n$) = $1$.

I have looked at other posts, but they haven't really shown me what I am looking for. Any help and proofs would be greatly appreciated. Thanks!

Answer 1

If $a\cdot b\equiv 1\mod n$, you have for some $k$ $$ab=1+kn\iff ab-kn=1,$$ which is a Bézout's relation between $a$ (or $b$) and $n$.