# Proof for a Euler Totient Lemma

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$

Therefore:

${\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}$

Thus:

${\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}$

Where:

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

Therefore:

$\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)$

• To disprove $$\phi(a)|\phi(b)\implies a|b$$ a single counterexample is sufficient, for example $a=4$ and $b=6$ – Peter Jun 10 '18 at 6:35
• 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 – Adam Jun 10 '18 at 7:06
• 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. – Peter Jun 10 '18 at 7:09
• 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$ – 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)$$

• 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? – Adam Jun 10 '18 at 7:02
• Maybe, I have written it unlucky, but it only says $\phi(a)|\phi(b)$ , not $\phi(a)=\phi(b)$ – Peter Jun 10 '18 at 7:06
• I'm sorry sir I don't follow, if $A=B=C$ you are saying it to be possible that $A \ne C$? – Adam Jun 10 '18 at 7:09
• Apparently, you missed the "|" sign in the middle. – Peter Jun 10 '18 at 7:10
• 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 – 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.

• 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$ – Adam Jun 10 '18 at 7:54
• The only confusion I have, unless I am missing something, is the admission that $$b \cdot \varphi(rad(b)) = \varphi(b)$$. – Primus8323 Jun 10 '18 at 7:58
• If I am not mistake, I think he meant $$\frac{b \cdot \varphi(rad(b))}{rad(b)} = \varphi(b)$$. – Primus8323 Jun 10 '18 at 8:08