I'm working in the following Euler's theorem exercise:
if $d|n$ then $\phi(dn)=d\phi(n)$
Hints for a shorter and simpler, imo, approach:
I'm based on:
$$n=\prod_{i=1}^k p_i^{a_i}\;,\;\;p_i\;\;\text{primes}\;\;,\;\;a_i\in\Bbb N\implies \phi(n)=n\prod_{i=1}^k\left(1-\frac1{p_i}\right)$$
So now:
$$d\mid n\implies n= xd\;,\;\;x\in\Bbb N\implies\; \phi(x)=x\prod_{i=1}^k\left(1-\frac1{p_i}\right)$$
I'm not sure this is the right way, how should I involve that $d$ so I would be able to show the requested property? Any help will be really appreciated.
Best Answer
Here is a proof that I'm copypasting from my old homework. It proves a bit more (see Theorem 3) and does not use the explicit formula for $\phi$ through the prime factorization.
Let $\phi$ denote Euler's totient function.
Proof of Lemma 1. (b) If $d$ is a common divisor of $ms+x$ and $m$, then $d$ must also divide $x$ (since $d\mid ms+x$ and $d\mid m$, so that \begin{equation} x=\underbrace{\left( ms+x\right) }_{\substack{\equiv0\mod d\\\text{(since }d\mid ms+x\text{)}}}-\underbrace{m}_{\substack{\equiv 0\mod d\\\text{(since }d\mid m\text{)}}}s\equiv 0-0s=0\mod d, \end{equation} so that $d\mid x$), and thus $d$ must be a common divisor of $x$ and $m$. In other words, each common divisor of $ms+x$ and $m$ must be a common divisor of $x$ and $m$.
If $d$ is a common divisor of $x$ and $m$, then $d$ must also divide $ms+x$ (since $d\mid x$ and $d\mid m$, so that \begin{equation} \underbrace{m}_{\substack{\equiv0\mod d\\\text{(since }d\mid m\text{)}}}s+\underbrace{x}_{\substack{\equiv0\mod d\\\text{(since }d\mid x\text{)}}}\equiv0s+0=0\mod d, \end{equation} so that $d\mid ms+x$), and thus $d$ must be a common divisor of $ms+x$ and $m$. In other words, each common divisor of $x$ and $m$ must be a common divisor of $ms+x$ and $m$.
We have thus shown that:
Each common divisor of $ms+x$ and $m$ must be a common divisor of $x$ and $m$.
Each common divisor of $x$ and $m$ must be a common divisor of $ms+x$ and $m$.
Combining these two statements, we conclude that the common divisors of $ms+x$ and $m$ are exactly the common divisors of $x$ and $m$. Thus, the greatest common divisor of $ms+x$ and $m$ is the greatest common divisor of $x$ and $m$. In other words, $\gcd\left( ms+x,m\right) =\gcd\left( x,m\right) $. Now, we have the following equivalence of statements: \begin{align*} \left( ms+x\text{ is coprime to }m\right) \ & \Longleftrightarrow\ \left( \underbrace{\gcd\left( ms+x,m\right) }_{=\gcd\left( x,m\right) }=1\right) \\ & \Longleftrightarrow\ \left( \gcd\left( x,m\right) =1\right) \ \Longleftrightarrow\ \left( x\text{ is coprime to }m\right) . \end{align*} This proves Lemma 1 (b).
(a) We have \begin{align*} & \left( \text{the number of integers among }ms+1,\ ms+2,\ \ldots ,\ ms+m\text{ that are coprime to }m\right) \\ & =\left\vert \left\{ x\in\left\{ 1,2,\ldots,m\right\} \ \mid \ \underbrace{ms+x\text{ is coprime to }m}_{\substack{\text{this is equivalent to}\\x\text{ being coprime to }m\\\text{(by Lemma 1 (b))}}}\right\} \right\vert \\ & =\left\vert \left\{ x\in\left\{ 1,2,\ldots,m\right\} \ \mid\ x\text{ is coprime to }m\right\} \right\vert \\ & =\left( \text{the number of integers among }1,\ 2,\ \ldots,\ m\text{ that are coprime to }m\right) \\ & =\left( \text{the number of }x\in\left\{ 1,2,\ldots,m\right\} \text{ that are coprime to }m\right) \\ & =\phi\left( m\right) \end{align*} (since $\phi\left( m\right) $ is defined as the number of $x\in\left\{ 1,2,\ldots,m\right\} $ that are coprime to $m$). This proves Lemma 1 (a). $\blacksquare$
Proof of Lemma 2. We have \begin{align*} & \left( \text{the number of positive integers }\leq mk\text{ that are coprime to }m\right) \\ & =\left( \text{the number of integers among }1,\ 2,\ \ldots,\ mk\text{ that are coprime to }m\right) \\ & =\sum_{s=0}^{k-1}\underbrace{\left( \text{the number of integers among }ms+1,\ ms+2,\ \ldots,\ ms+m\text{ that are coprime to }m\right) }_{\substack{=\phi\left( m\right) \\\text{(by \eqref{darij1.p11.claim1})}}}\\ & \qquad\qquad\left( \begin{array} [c]{c} \text{since each of the integers }1,\ 2,\ \ldots,\ mk\text{ belongs to exactly one}\\ \text{of the }k\text{ lists }\left( 1,\ 2,\ \ldots,\ m\right) ,\ \left( m+1,\ m+2,\ \ldots,\ 2m\right) ,\ \ldots,\\ \left( m\left( k-1\right) +1,\ m\left( k-1\right) +2,\ \ldots ,\ mk\right) \text{; in other words, each}\\ \text{of the integers }1,\ 2,\ \ldots,\ mk\text{ belongs to exactly one of the }k\\ \text{lists }\left( ms+1,\ ms+2,\ \ldots,\ ms+m\right) \text{ with } s\in\left\{ 0,1,\ldots,k-1\right\} \end{array} \right) \\ & =\sum_{s=0}^{k-1}\phi\left( m\right) =k\phi\left( m\right) . \end{align*} This proves Lemma 2. $\blacksquare$
Proof of Theorem 3. (a) Let $x$ be an integer.
Proof of the $\Longrightarrow$ direction of \eqref{darij1.p12.c1}: Assume that $x$ is coprime to $m$. Thus, $\gcd\left( x,m\right) =1$. Hence, no prime can divide both $m$ and $x$. Now, we shall prove that $x$ is coprime to $mn$. Indeed, assume the contrary. That is, $x$ is not coprime to $mn$; thus, $\gcd\left( x,mn\right) >1$. Hence, there exists a prime $p$ which divides $\gcd\left( x,mn\right) $. Consider this $p$. Then, $p\mid\gcd\left( x,mn\right) \mid mn$. Since $p$ is a prime, this yields that we have $p\mid m$ or $p\mid n$. If we had $p\mid m$, then the prime $p$ would divide both $m$ and $x$ (because $p\mid m$ and $p\mid\gcd\left( x,mn\right) \mid x$); this would contradict the fact that no prime can divide both $m$ and $x$. Hence, we cannot have $p\mid m$. Thus, we must have $p\mid n$ (since we have $p\mid m$ or $p\mid n$). Since $p$ is a prime, we thus conclude that $p\mid m$ (due to our assumption that every prime that divides $n$ also divides $m$). This contradicts the fact that we cannot have $p\mid m$. This contradiction shows that our assumption was false. Hence, we have shown that $x$ is coprime to $mn$. The $\Longrightarrow$ direction of \eqref{darij1.p12.c1} is thus proven.
Proof of the $\Longleftarrow$ direction of \eqref{darij1.p12.c1}: Assume that $x$ is coprime to $mn$. Thus, $\gcd\left( x,mn\right) =1$. Now, we shall prove that $x$ is coprime to $m$. Indeed, assume the contrary. That is, $x$ is not coprime to $m$; thus, $\gcd\left( x,m\right) >1$. Hence, there exists a prime $p$ which divides $\gcd\left( x,m\right) $. Consider this $p$. Then, $p\mid\gcd\left( x,m\right) \mid x$ and $p\mid\gcd\left( x,m\right) \mid m\mid mn$. Hence, $p$ is a common divisor of the numbers $x$ and $mn$, and therefore divides their greatest common divisor. In other words, $p\mid\gcd\left( x,mn\right) =1$. So we have $p\mid1$. This is absurd, since $p$ is a prime. This contradiction shows that our assumption was false. Hence, we have shown that $x$ is coprime to $m$. The $\Longleftarrow$ direction of \eqref{darij1.p12.c1} is thus proven.
Now, with both directions of \eqref{darij1.p12.c1} being proven, the proof of \eqref{darij1.p12.c1} is complete. In other words, Theorem 3 (a) is proven.
(b) Lemma 2 (applied to $k=n$) yields that the number of positive integers $\leq mn$ that are coprime to $m$ is $n\phi\left( m\right) $. Thus, \begin{align*} n\phi\left( m\right) & =\left( \text{the number of positive integers }\leq mn\text{ that are coprime to }m\right) \\ & =\left( \text{the number of }x\in\left\{ 1,2,\ldots,mn\right\} \text{ such that }\underbrace{x\text{ is coprime to }m} _{\substack{\Longleftrightarrow\left( x\text{ is coprime to }mn\right) \\\text{(due to \eqref{darij1.p12.c1})}}}\right) \\ & =\left( \text{the number of }x\in\left\{ 1,2,\ldots,mn\right\} \text{ such that }x\text{ is coprime to }mn\right) \\ & =\phi\left( mn\right) \end{align*} (since $\phi\left( mn\right) $ is defined as the number of $x\in\left\{ 1,2,\ldots,mn\right\} $ such that $x$ is coprime to $mn$). This proves Theorem 3 (b). $\blacksquare$
Proof of Corollary 4. Every prime that divides $n$ also divides $m$ (since $n\mid m$). Hence, Theorem 3 (b) yields $\phi\left( nm\right) =n\phi\left( m\right) $. This proves Corollary 4. $\blacksquare$
Corollary 4 is your question (with $d$ and $n$ renamed as $n$ and $m$).