Show that number of elements in $(\mathbb{Z}/n\mathbb{Z})^\times$ is $\varphi(n)$

Question

Question at the end: Prove that the number of elements of $(\mathbb Z / n\mathbb Z)^\times$ is $\varphi(n)$ where $\varphi$ denotes the Euler function. I’ve demonstrated that it works for all n up to 12... Work showing n=1-12

It seems kinda obvious that not only does $\varphi(n)$ give the number of elements of $(\mathbb Z / n\mathbb Z)^\times$, but also the list of numbers are the same.

Question: I need a nudge in the right direction here. I can see that it works but I’m not sure how the remainders being equal to the relatively prime factors connects in a proof.

Thanks!

Answer 1

Hint

An element $\bar{a}$ (where $a=0, \dotsc, n-1$) is invertible in $\mathbb{Z/n}$ iff $a$ is relatively prime to $n$.

Answer 2

The key to these kinds of things is a clever observation called Bezout's Lemma. It says that if $x$ and $y$ are natural numbers with highest common factor equal to $d$, then you can find integers $a$ and $b$ such that $$ ax + by = d. $$ It is proved by applying Euclid's algorithm repeatedly and keeping track of what is happening. The relevance here is that if $m$ is relatively prime to $n$, then you have $$ am + bn = 1 $$ for some numbers $a$ and $b$. i.e. given such $m$, you can find $a$ with $$ am = (\text{multiple of}\ n) + 1... $$

Answer 3

The criterion for $ax \equiv b \pmod{n}$ is that $(a,n) \mid b$.

If $a$ is invertible then $ax \equiv 1 \pmod{n}$ has a solution. So $(a,n) \mid 1$. So $(a,n) =1$. And vice versa.