The lemma I have attempted to prove is somewhat well known I think:

$a | b {\rm \: \Rightarrow \:}\phi(a) | \phi(b)$ (1)

$\phi(a) | \phi(b) {\rm \: \not\Rightarrow \:}a | b$ (2)

And in as much as I am sure there are proofs that are much shorter than my attempt, I wanted to try and do this keeping to elementary facts rather than restrict the proof to a particular domain of the naturals.Below is my attempt thus far, and below that is the part I have identified that still requires a vigorous proof in the context of my answer. This missing part applies to only to the proof of (1).

for (1) we have:

$a | b{\rm \: \Rightarrow \:} {rad(a)} |\, {rad(b)}$

${rad(a)} |\, {rad(b)}{\rm \: \Rightarrow \:}\prod_{p|a} p \, | \prod_{p|b} p$

$\prod_{p|a} p \, | \prod_{p|b} p{\rm \: \Rightarrow \:}\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \,b\cdot \prod_{p|b} \Bigl(1-\frac{1}{p}\Bigr)$

$\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \,b\cdot \prod_{p|b} \Bigl(1-\frac{1}{p}\Bigr){\rm \: \Rightarrow \:}{\Biggl\{\frac{b \cdot \prod_{p|b} (1-\frac{1}{p})}{\prod_{p|a} (1-\frac{1}{p})}}\Biggr\}=0$

${\Biggl\{\frac{b \cdot\prod_{p|b} (1-\frac{1}{p})}{\prod_{p|a} (1-\frac{1}{p})}}\Biggr\}=0 \land {\Bigl\{\frac{b}{a}}\Bigr\}=0{\rm \: \Rightarrow \:}{\Biggl\{\frac{b\prod_{p|b} (1-\frac{1}{p})}{a\prod_{p|a} (1-\frac{1}{p})}}\Biggr\}=0$

${\Biggl\{\frac{b\prod_{p|b} (1-\frac{1}{p})}{a\prod_{p|a} (1-\frac{1}{p})}}\Biggr\}=0{\rm \: \Rightarrow \:}{\Bigl\{\frac{\phi(b)}{\phi(a)}}\Bigr\}=0$

${\Bigl\{\frac{\phi(b)}{\phi(a)}}\Bigr\}=0{\rm \: \Rightarrow \:}\phi(a) | \phi(b)$

Thus establishing $a | b {\rm \: \Rightarrow \:}\phi(a) | \phi(b)$ is true.

We now look to establishing that (2) is true:

$\phi(a) | \phi(b) {\rm \: \Rightarrow \:}{\Bigl\{\frac{\phi(b)}{\phi(a)}}\Bigr\}=0$

${\Bigl\{\frac{\phi(b)}{\phi(a)}}\Bigr\}=0{\rm \: \Rightarrow \:}{\Bigl\{\frac{b}{a}}\Bigr\}=0 \lor {\Biggl\{\frac{\prod_{p|b} (1-\frac{1}{p})}{\prod_{p|a} (1-\frac{1}{p})}}\Biggr\}=0 \lor {\Biggl\{\frac{b}{\prod_{p|a} (1-\frac{1}{p})}}\Biggr\}=0$

Consider $z_1=x_1 y_1 \land z_2=x_2 y_2$ and $x_1,x_2,y_1,y_2 \in \mathbb Q$

And suppose we can assert ${\Biggl\{\frac{z_1}{z_2}}\Biggr\}=0$ knowing $z_2$ to divide $z_1$.

We then consider the individual divisibility criteria between the four integer variables in such a ratio with no remainder, as to allow us to see that the reason for the converse of (1) having a false truth value is elementary in nature, by finally substituting these generic variables for the four arithmetic functions appropriate in the division of the totients of $a$ and $b$, allowing us to see that either $a | b$ or it's negation can be true when only knowing $\phi(a) | \phi(b)$.

$\frac{x_2}{x_1} | \frac{ y_2}{ y_1}{\rm \: \Rightarrow \:}{\Biggl\{\frac{x_2}{x_1}}\Biggr\}=0 \land {\Biggl\{\frac{ y_2}{ y_1}}\Biggr\}=0{\rm \: \Rightarrow \:}{\Biggl\{\frac{x_1 y_1}{x_2 y_2}}\Biggr\}=0$

$\frac{x_2}{y_1} | \frac{ y_2}{ x_1}{\rm \: \Rightarrow \:}{\Biggl\{\frac{x_2}{y_1}}\Biggr\}=0 \land {\Biggl\{\frac{ y_2}{ x_1}}\Biggr\}=0{\rm \: \Rightarrow \:}{\Biggl\{\frac{x_1 y_1}{x_2 y_2}}\Biggr\}=0$

$\frac{x_2 y_2}{y_1} | {x_1}{\rm \: \Rightarrow \:}{\Biggl\{\frac{x_2 y_2}{y_1}}\Biggr\}=0 \land {\Biggl\{{ x_1}}\Biggr\}=0{\rm \: \Rightarrow \:}{\Biggl\{\frac{x_1 y_1}{x_2 y_2}}\Biggr\}=0$

$\frac{x_2 y_2}{x_1} | {y_1}{\rm \: \Rightarrow \:}{\Biggl\{\frac{x_2 y_2}{x_1}}\Biggr\}=0 \land {\Biggl\{{ y_1}}\Biggr\}=0 {\rm \: \Rightarrow \:}{\Biggl\{\frac{x_1 y_1}{x_2 y_2}}\Biggr\}=0$


${\Biggl\{\frac{z_1}{z_2}}\Biggr\}=0{\rm \: \Rightarrow \:}\frac{x_2}{x_1} | \frac{ y_2}{ y_1} \lor \frac{x_2}{y_1} | \frac{ y_2}{ x_1} \lor \frac{x_2 y_2}{y_1} | {x_1} \lor \frac{x_2 y_2}{x_1} | {y_1}$


${\Bigl\{\frac{z_1}{z_2}}\Bigr\}=0{\rm \: \Rightarrow \:}S$

$S:({\Bigl\{\frac{ y_2}{ y_1}}\Bigr\}=0 \land {\Bigl\{\frac{x_1}{x_2}}\Bigr\}=0)\lor({\Bigl\{\frac{x_2}{y_1}}\Bigr\}=0 \land {\Bigl\{\frac{ y_2}{ x_1}}\Bigr\}=0)\lor({\Bigl\{\frac{x_2 y_2}{y_1}}\Bigr\}=0)\lor({\Bigl\{\frac{x_2 y_2}{x_1}}\Bigr\}=0)$

Then finally we make the substitutions as follows:

$$x_1=b$$ $$x_2=a$$ $$y_1=\prod_{p|b} (1-\frac{1}{p})$$ $$y_2=\prod_{p|a} (1-\frac{1}{p})$$

$\phi(a) | \phi(b){\rm \: \Rightarrow \:}{\Bigl\{\frac{\phi(b)}{\phi(a)}}\Bigr\}=0{\rm \: \Rightarrow \:}S_{\phi(a),\phi(b)}$

$S_{\phi(a),\phi(b)}:S_{\phi(a),\phi(b),1}\lor S_{\phi(a),\phi(b),2}\lor S_{\phi(a),\phi(b),3} \lor S_{\phi(a),\phi(b),4}$


$S_{\phi(a),\phi(b),1}:{\Bigl\{\frac{ \prod_{p|a} (1-\frac{1}{p})}{\prod_{p|b} (1-\frac{1}{p})}}\Bigr\}=0 \land {\Bigl\{\frac{b}{a}}\Bigr\}=0$

$S_{\phi(a),\phi(b),2}:{\Bigl\{\frac{a}{\prod_{p|b} (1-\frac{1}{p})}}\Bigr\}=0 \land {\Bigl\{\frac{ \prod_{p|a} (1-\frac{1}{p})}{ b}}\Bigr\}=0$

$S_{\phi(a),\phi(b),3}:{\Bigl\{\frac{a \prod_{p|a} (1-\frac{1}{p})}{\prod_{p|b} (1-\frac{1}{p})}}\Bigr\}=0$

$S_{\phi(a),\phi(b),4}:{\Bigl\{\frac{a \prod_{p|a} (1-\frac{1}{p})}{b}}\Bigr\}=0$

And finally it is clear that:

$S_{\phi(a),\phi(b)}{\rm \: \Rightarrow \:} a | b \lor \lnot(a | b)$


$\phi(a) | \phi(b) {\rm \: \not\Rightarrow \:}a | b$

MISSING PART: Show that:

$\Biggl(\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \,b\cdot \prod_{p|b} \Bigl(1-\frac{1}{p}\Bigr) \Biggr)$

is true $\forall a,b \in \mathbb N$ such that $a |b$

Case 1:

$\lnot \Biggl(\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \,b \Biggr)\land \lnot\Biggl(\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \prod_{p|b} \Bigl(1-\frac{1}{p}\Bigr) \Biggr)$

Case 2:

$\Biggl(\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \,b \Biggr)\land \lnot\Biggl(\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \prod_{p|b} \Bigl(1-\frac{1}{p}\Bigr) \Biggr)$

Case 3:

$\lnot \Biggl(\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \,b \Biggr)\land \Biggl(\prod_{p|a} \Bigl(1-\frac{1}{p}\Bigr) | \prod_{p|b} \Bigl(1-\frac{1}{p}\Bigr) \Biggr)$

  • $\begingroup$ To disprove $$\phi(a)|\phi(b)\implies a|b$$ a single counterexample is sufficient, for example $a=4$ and $b=6$ $\endgroup$ – Peter Jun 10 '18 at 6:35
  • $\begingroup$ I had been told my notation for what I was trying to say was not correct, but rather than disprove this alone, I was really trying to demonstrate that any number of $a,b \in \mathbb N$ exist such that $\phi (a) | \phi (b)$ but a doesn't divide b, rather that showing that there exists such a pair as a counter example $\endgroup$ – Adam Jun 10 '18 at 7:06
  • $\begingroup$ It might be interesting to verify the exact conditions that ensure $\phi(a)|\phi(b)\implies a|b$ or vice versa, when it fails , but for the disprove it is not necessary. $\endgroup$ – Peter Jun 10 '18 at 7:09
  • $\begingroup$ ok maybe I should have worked on the way I worded what I was trying to do to show the approach was what I thought would be necessary, but that is correct I wanted to determine the proof specifically for the 3 cases I listed at the end when $a | b$ $\endgroup$ – Adam Jun 10 '18 at 7:17

I would suggest the following proof of $$a|b\implies \phi(a)|\phi(b)$$

First of all, as you did , we notice $$a|b\implies rad(a)|rad(b)$$

So, there exists a positive integer $k$ with $$k\cdot rad(a)=rad(b)$$

$k$ and $rad(a)$ must be coprime, otherwise the left side would not be squarefree, but the rightside is. Hence, we have $$\phi(rad(b))=\phi(k)\cdot \phi(rad(a))$$ Therefore $$\phi(rad(a))|\phi(rad(b))$$

So we get $$\phi(a)=a\cdot \phi(rad(a))|b\cdot \phi(rad(b))=\phi(b)$$

  • $\begingroup$ yep I agree with that for declaration of such a $k$ existing, but doesn't the final line suggest that when a divides b, their totients must be equal? $\endgroup$ – Adam Jun 10 '18 at 7:02
  • $\begingroup$ Maybe, I have written it unlucky, but it only says $\phi(a)|\phi(b)$ , not $\phi(a)=\phi(b)$ $\endgroup$ – Peter Jun 10 '18 at 7:06
  • $\begingroup$ I'm sorry sir I don't follow, if $A=B=C$ you are saying it to be possible that $A \ne C$? $\endgroup$ – Adam Jun 10 '18 at 7:09
  • $\begingroup$ Apparently, you missed the "|" sign in the middle. $\endgroup$ – Peter Jun 10 '18 at 7:10
  • $\begingroup$ I'm sorry if I seem fussy but I completely agree with that the $k$ and $rad(a)$ must be coprime, and so this allows us to use the multiplicative property of the totient $\endgroup$ – Adam Jun 10 '18 at 7:11

Try this: Let $a \, | \, b$. Each number has a unique prime factorization which we represent as: $$a = \prod_{i=1}^{n} p_i^{a_i}$$ $$b = \prod_{i=1}^{m} p_i^{b_i}$$ By hypothesis, $b_i \geq a_i$, for all $ 1 \leq i \leq n$. Now let us split $b$ into two relatively prime pieces, $b = c \cdot d$, where: $$c = \prod_{p_i | a} p_i^{b_i}$$ And $$d = \prod_{p_i \nmid a} p_i^{b_i} $$ Now, since $c$ and $d$ are relatively prime, we have that: $$\varphi(b) = \varphi(c) \cdot \varphi(d)$$ We can now consider that, since $b_i \geq a_i$, we have that we can represent $\varphi(c)$ as: $$\varphi(c) = \varphi \left(\prod_{p_i | a} p_i^{a_i + r_i} \right)$$ Where in all instances, $a_i + r_i = b_i$. Notice: $$\varphi(c) = \prod_{p_i | a} \varphi(p_i^{a_i + r_i}) $$ By properties of the totient function: $$\varphi(c) = \left( \prod_{p_i | a} p_i^{r_i} \right) \cdot \left( \prod_{p_i | a} \varphi(p_i^{a_i}) \right)$$ Subsequently, we have that: $$\varphi(c) = \varphi(a) \cdot \left( \prod_{p_i | a} p_i^{r_i} \right)$$ Since, $$\varphi(b) = \varphi(c) \cdot \varphi(d) = \varphi(d) \cdot \varphi(a) \cdot \left( \prod_{p_i | a} p_i^{r_i} \right)$$ we can clearly see that $\varphi(a) | \varphi(b)$. Hope this helped.

  • $\begingroup$ Yep this is equally valid to Peter's answer, I guess I was just hell bent on keeping my approach the same for the proof of (1) and (2), but it would have been much better to have split b into two unique prime factorizations as you have and exploit the multiplicative property of the totient know one of those factors needs to be square-free and coprime to $a$ $\endgroup$ – Adam Jun 10 '18 at 7:54
  • $\begingroup$ The only confusion I have, unless I am missing something, is the admission that $$b \cdot \varphi(rad(b)) = \varphi(b)$$. $\endgroup$ – Primus8323 Jun 10 '18 at 7:58
  • $\begingroup$ If I am not mistake, I think he meant $$\frac{b \cdot \varphi(rad(b))}{rad(b)} = \varphi(b)$$. $\endgroup$ – Primus8323 Jun 10 '18 at 8:08

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.