# Step in proof Sum of Euler Phi Function of Divisors (part 2)

This is a follow-up question to this post: Step in proof Sum of Euler Phi Function over Divisors,

so we are proving Gauss' formula. Let $d$ be a positive divisor of $n$. We show that the number of elements $\overline a\in\mathbb Z/n\mathbb Z$ with $\operatorname{order}(\overline a)=d$ equals $\phi(d)$ (where $\phi$ is Euler’s function). I’ve already shown that $\operatorname{order}(\overline a)=n/\gcd(a,n)$, which is equivalent to $$a=b\cdot\frac{n}{d}\text{ where }\gcd(b,d)=1\text{ and }1\leq b\leq d.$$ Now my book says that the number of $b$'s for which this holds is $\phi(d)=\#\{\overline b\in\mathbb Z/d\mathbb Z\vert\gcd(b,d)=1\text{ and }1\leq b\leq d\}$. I can see that this number of $b$'s cannot exceed $\phi(d)$, because of the conditions on $b$.

However, assume this number is smaller than $\phi(d)$. That means there would be a $b$ such that $\gcd(b,d)=1$ and $1\leq b\leq d$, yet $a\neq b\cdot\dfrac{n}{d}$. If $b\cdot\dfrac{n}{d}>a$, then $b>d$, which is a contradiction. If $b\cdot\dfrac{n}{d}<a$, I'm guessing we should have a contradiction with the fact that $\gcd(b,d)=1$. Could someone help me out?

• Your last paragraph references some $a$ yet you never define it. – Akater Jul 5 '17 at 17:02

## 1 Answer

Presumably, you define $\phi(d)$ as $\#\left\{b\in\mathbb Z \mid \gcd(b,d) = 1,\, 1\leq b \leq d\right\}$.

The function $$(b\mapsto\bar b)\colon \left\{b\in\mathbb Z \mid \gcd(b,d) = 1,\, 1\leq b \leq d\right\} \to \left\{\bar b\in\mathbb Z/d\mathbb Z \mid \gcd(b,d) = 1,\, 1\leq b \leq d\right\}$$ that is a restriction of the remainder function $\mathbb Z \to \mathbb Z / d \mathbb Z$, is isomorphism of sets, and the fact that it's injective has nothing to do with $\gcd$, contrary to your guess. It is true simply because different integers $b_1, b_2 \in \mathbb Z$ between $1$ and $d$ have different remainders $r_1, r_2 \in \mathbb Z / d \mathbb Z$.