Showing Element is Not part of Multiplicative group of Integers mod $n$

Question

How do you show that $a$ is not an element of the multiplicative group of integers mod $n$ if and only if $gcd(a,n)\neq 1$?

Doesn’t this follow trivially from the definition of the multiplicative group of integers mod $n$? Am I misreading the question?

Answer 1

It is not quite clear what you mean by "trivially follow from the definition" as it depends on what definition you are starting with. Usually the elements of the multiplicative groups of integers mod $n$ are by definition the group of invertible elements $a$ for the multiplication in the additive group of integers mod $n$. This means $a$ is in the multiplicative group iff there exists an integer $b$ such that $ab=1$ mod $n$.

Starting with this definition, it is in a sense non trivial as the proof requires an important theorem (Bézout).

$a$ has a multiplicative inverse iff there exist two integers $b,k$ such that $ab=1+kn$ which is equivalent by Bézout theorem to $gcd(n,a)=1$. So $a$ is not in the multiplicative group iff $gcd(a,n)\neq 1$.

Answer 2

The relationship $a\cong b \pmod n$ defines an equivalence relation on the set of all integers...

Thus every integer falls into some residue class mod $n$...