Home › Forums › Math Olympiad, I.S.I., C.M.I. Entrance › Number Theory

Tagged: #Number theory

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

- AuthorPosts
- December 14, 2018 at 3:50 am #24794December 24, 2018 at 1:59 pm #25059
(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.

December 25, 2018 at 7:54 am #25089(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! ðŸ™‚

December 25, 2018 at 9:21 am #25090In 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}\)…..

- AuthorPosts

You must be logged in to reply to this topic.