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


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}$.

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

Looks good to me. Were there any doubts you had that motivated you to ask for verification?

  • $\begingroup$ It's just that the theorems I used to prove it were all from former sections, so I felt like since this question was in a later section, I must have to use one of the new theorems. $\endgroup$ – MathQuestion Nov 2 '15 at 5:58
  • $\begingroup$ Well looking at your proof now are there any of the new theorems which encompass parts of the argument you just made? $\endgroup$ – Brandon Thomas Van Over Nov 2 '15 at 6:00
  • $\begingroup$ It doesn't seem that way. But I'm glad I was able to prove it using simpler theorems anyway. $\endgroup$ – MathQuestion Nov 2 '15 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.