Select Page
2 voices
3 replies
• Author
Posts
• #24794
Kaveri Kayra
Participant

#25059
swastik pramanik
Participant

(b) Let $$n=\prod_{k=1}^r p_k^{a_k}=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_r^{a_r}$$ . So, $$\phi(n) =n\left(1-\frac{1}{p_1}\right) \left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_r}\right)$$ .

For any prime $$p$$ the inequality $$2p-2\geq p$$ or, $$\frac{p-1}{p}\geq \frac{1}{2}$$ So, we have $$r$$ prime number for which the inequality is true. Multiplying them gives $$\left(1-\frac{1}{p_1}\right) \left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_r}\right)\geq \frac{1}{2^r}$$ multiplying both sides with $$n$$ gives So, we want to show that $$n\left(1-\frac{1}{p_1}\right) \left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_r}\right)\geq \frac{n}{2^r}$$ or concisely $$\phi(n)\geq \frac{n}{2^r}$$ as required.

#25089
swastik pramanik
Participant

(a) Let $$n=2^{k_0}p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$$ . So, $$\phi(n)=2^{k_0-1}p_1^{k_1-1}p_2^{k_2-1}\cdots p_r^{k_r-1}(2-1)(p_1-1)(p_2-1)\cdots (p_r-1)$$ . Now, we use the inequalities $$k-\frac{1}{2}\ge \frac{k}{2}$$ and $$p-1>\sqrt{p}$$ for $$p>2$$. So, we have $$\phi(n)\le 2^{k_0-1}p_1^{k_1/2}p_2^{k_2/2}\cdots p_r^{k_r/2}\ge \frac{1}{2}\sqrt{n}$$ .

Now, also $$p-1<p$$ . So, $$\phi(n)\le 2^{k_0}p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}=n$$ .

Combining them up we get $$\frac{1}{2}\sqrt{n}\le \phi(n)\le n$$ as required.

(c) Let $$p$$ be the smallest prime divisor of $$n$$ so that, $$p\le \sqrt{n}$$. Then $$\phi(n) \le n\left(1-\frac{1}{p}\right)$$ . We know that, $$p\le \sqrt{n}$$ which implies $$1-\frac{1}{p}\le 1-\sqrt{n}$$. So, $$\phi(n) \le n\left(1-\frac{1}{p}\right)\le n\left(1-\frac{1}{\sqrt{n}}\right)=n-\sqrt{n}$$.

Hence, we are done! 🙂

#25090
swastik pramanik
Participant

In part (c) in line 3 the inequality should be $$1-\frac{1}{p}\le 1-\frac{1}{\sqrt{n}}$$ not $$1-\frac{1}{p}\le 1-\sqrt{n}$$…..

topic tags

You must be logged in to reply to this topic.