Number Theory

This topic contains 3 replies, has 2 voices, and was last updated by  swastik pramanik 2 months, 3 weeks ago.

Viewing 4 posts - 1 through 4 (of 4 total)
  • 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}\)…..

Viewing 4 posts - 1 through 4 (of 4 total)

You must be logged in to reply to this topic.