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

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!

• In my reality, this is the definition of $\phi.$ Do you have a different definition? – B. Goddard May 31 '18 at 22:26
• The definition I have for $\varphi(n)$ is the number of elements in a such that a<n and (a,n)=1. – Kaleb Allinson May 31 '18 at 22:46
• So the problem comes down to showing that the invertible elements are exactly those which are relatively prime. – B. Goddard May 31 '18 at 23:32
• What do you mean by invertible elements? – Kaleb Allinson Jun 1 '18 at 4:02
• The ring $(Z/nZ)^\times$ is the set of invertible elements or "units". – B. Goddard Jun 1 '18 at 11:38

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...$$

• OK, so does this reasoning work? Since $\bar{a}\bar{c}=\bar{1}$ Is the requirement for $(\mathbb{Z}/n\mathbb{Z})^x$... then $\bar{ac}=\bar{1}$ so $ac + kn = ny +1$ ... it follows that $ac + (k-y)n =1$. So we know that a and n are relatively prime and that for every a there is one c with the correct (k-y) chosen to go with the c needed to make $\bar{a} \bar{c}=\bar{1}$. So each a that makes $\bar{a} \bar{c}=\bar{1}$ true matches with one of the a’s from (a,n)=1 – Kaleb Allinson Jun 1 '18 at 3:51
• Yeah. OK so I think we were kind of working on opposite ends of the problem. So one strategy to solve this is to take the two sets A = {invertible elements mod n} and B = {numbers less than n and coprime to n} and show A = B. So to do that we often do two separate aguments: 1. $A \subset B$ and 2. $B \subset A$. So above I outlined the proof of "If m is coprime to n, then m is invertible mod n". You are essentially discussing "If a is invertible mod n, then a and n are relatively coprime". For your step you need slightly more than the literal statement of Bezout I gave above. – T_M Jun 1 '18 at 4:39
• You need to know that the hcf of x and y really is the smallest number you can make via ax + by where a and b are integers – T_M Jun 1 '18 at 4:40

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.

• OK, that makes sense! Thanks! – Kaleb Allinson Jun 1 '18 at 4:17

Hint

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

• that seems basically to be the content of the problem – Andres Mejia May 31 '18 at 22:20
• What do you mean by invertible? – Kaleb Allinson Jun 1 '18 at 3:57