1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ HINT: Write $n=7^k \cdot m$, where $m$ is not divisible by $7$. Then compute $\varphi(n)$, and see what happens. $\endgroup$ – Crostul Apr 1 '17 at 23:22
  • $\begingroup$ I've gotten $ (7^{k} - 7^{k-1})\phi (m) $. I'm not quite sure how that helps me relate to $6n$ $\endgroup$ – M Paul Apr 1 '17 at 23:33
  • $\begingroup$ 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 $\endgroup$ – M Paul Apr 1 '17 at 23:36
  • $\begingroup$ Try writing $7^k-7^{k-1}$ as $6\cdot7^{k-1}$ $\endgroup$ – Lubin Apr 2 '17 at 0:00
  • $\begingroup$ I actually just figured that part out! Silly me! Thanks though! $\endgroup$ – M Paul Apr 2 '17 at 0:02
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'll leave it to you to check when equality holds. $\endgroup$ – Mark Twain Apr 2 '17 at 0:46

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.