Number Theory

[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}\).....

[Author]

Posts