# Number Theory: Prove that for any $n\exists k$ such that $n\mid\phi(k)$.

I think I've proven this homework problem, but I'm not sure if my proof is correct:

Given an integer $n$, prove that there exists at least one $k$ for which $n\mid \phi(k)$. (Where $\phi$ is the Euler-phi function).

Proof

Let $n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$.

Note that $\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_r})$.

Now, let $k=n^t$, some $2\leq t\in\mathbb{N}$. Then, $k=p_1^{ta_1}p_2^{ta_2}\cdots p_r^{ta_r}$. So,

$\phi(k)=n^t(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_r})=n^{t-1}\phi(n)=n^{t-1}m$, since $\phi(n)=m\in\mathbb{Z}$.

Clearly, $n\mid n^{t-1}$, so we have $n\mid\phi(k)$ if $k=n^t$ for any $2\leq t\in\mathbb{N}$.

• looks good - just one little adjustment - the condition required is $t \gt 1$ rather than $t \in \mathbb{N}$ – David Holden Nov 2 '15 at 5:59
• Thank you very much, just made the adjustment. – MathQuestion Nov 2 '15 at 6:06