Proof for a Euler Totient Lemma

Question

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

Answer 1

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

Answer 2

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.