Show that $\varphi(2n)\mid n!$ for all positive integer $n$.
Problem
Source: 2020 Thailand Mathematical Olympiad P1
Tags: number theory
28.12.2020 10:32
(1) For $n=1$ with $\varphi(2n)=1$, the claimed statement holds true. (2) If $n\ge3$ is odd, then $\varphi(2n)=\varphi(n)\le n-1$ and hence divides $n!$. (3) If $n\ge2$ is even, then $\varphi(2n)=2\varphi(n)$. As $2$ divides $n$ and $\varphi(n)\le n-1$ divides $(n-1)!$, the claimed statement holds true.
01.02.2022 07:08
Since $\gcd(2k,2n)\geq 2>1$ for $1\leq k\leq n$, $$\varphi(2n)\leq 2n-n=n.$$Thus, $\varphi(2n)|n!.$
31.03.2022 07:07
Let $n=2^km$ where $k\ge 0$ and $m$ is odd; also, let $p_1^{\ell_1}\cdots p_j^{\ell_j}$ be the prime factorization of $m.$ Then, \begin{align*}\varphi(2n)&=\varphi(2^{k+1}m)=\varphi(2^{k+1})\cdot\varphi(m)=2^k\cdot\prod_{i=1}^{j}{p^{\ell_i-1}(p_i-1)}\\&=2^k\cdot\prod_{i=1}^{j}p^{\ell_i-1}\cdot\prod_{i=1}^{j}(p_i-1)=2^k\cdot\frac{m}{\prod_{i=1}^{j}p_i}\cdot\prod_{i=1}^{j}(p_i-1).\end{align*}Hence, if $n!=A\cdot\varphi(2n),$ $$A=\frac{n!\cdot\prod_{i=1}^{j}p_i}{2^km\prod_{i=1}^{j}(p_i-1)}=\prod_{i=1}^{j}p_i\frac{(n-1)!}{\prod_{i=1}^{j}(p_i-1)}.$$But $\prod_{i=1}^{j}(p_i-1)\mid (n-1)!$ as each $p_i\le n$ are distinct. Thus, $A$ is an integer. $\square$