• Author
  • #24794
    Kaveri Kayra

    swastik pramanik

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

    swastik pramanik

    (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! 🙂

    swastik pramanik

    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.