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?

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.