# Euler Phi Function and Divisibility

Question: Suppose that the positive integer n is divisible by 7. Prove that $7φ(n) ≤ 6n$ When exactly does equality hold and why?

I have concluded that if n is divisible by 7, it obviously cannot be prime. This eliminates the use of the equation $φ(p^k) = p^k − p^{k−1}$.

I have had a lot of practice with $n$ being prime, but have not learned a whole lot when $n$ is not prime.

• HINT: Write $n=7^k \cdot m$, where $m$ is not divisible by $7$. Then compute $\varphi(n)$, and see what happens. – Crostul Apr 1 '17 at 23:22
• I've gotten $(7^{k} - 7^{k-1})\phi (m)$. I'm not quite sure how that helps me relate to $6n$ – M Paul Apr 1 '17 at 23:33
• I have further simplified to get $$(7^{k}-7^{k-1}) \phi (m) \le 6*7^{k-1}m$$ which seems obvious to me as to why the RHS would be greater than the LHS, but I need to explain it better than that – M Paul Apr 1 '17 at 23:36
• Try writing $7^k-7^{k-1}$ as $6\cdot7^{k-1}$ – Lubin Apr 2 '17 at 0:00
• I actually just figured that part out! Silly me! Thanks though! – M Paul Apr 2 '17 at 0:02

Because $7$ divides $n$, $$\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)\le n\left(1-\frac{1}{7}\right)$$ and$$7\varphi(n)\le7n\left(1-\frac{1}{7}\right)=6n$$
By hypothesis, $n = 7^k m$ for some $k$, $m \in \mathbb{N}$, where $7 \nmid m$. Then $\gcd(7^k,m) = 1$, so $\varphi(7^k m) = \varphi(7^k) \varphi(m)$, so \begin{aligned}[t] 7 \varphi(n) = 7 \varphi(7^k m) = 7 \varphi(7^k) \varphi(m) &= 7 (7^k-7^{k-1}) \varphi(m) \\ &= 7\cdot 7^{k-1}(7-1) \varphi(m) = (7-1) 7^k \varphi(m) \leq 6 \cdot 7^k m = 6n.\end{aligned}