Let $a$ be a positive real number. Prove that a) There exists $n\in \mathbb{N}$ with $\frac{\sigma(\varphi(n))}{\varphi(\sigma(n))} > a$. b) There exists $n\in \mathbb{N}$ with $\frac{\sigma(\varphi(n))}{\varphi(\sigma(n))} < a$. (As usual, $\sigma(n) = \sum_{d\mid n} d$ and $\varphi(n)$ is the number of integers $1\le m\le n$ which are coprime with $n$.) Proposed by Deniz Can Karaçelebi
Problem
Source: Turkey Olympic Revenge 2024 P5
Tags: number theory, phi function, Sigma function
07.08.2024 00:34
a) Firstly, choose $n=p$. Then we need to show that $\frac{\sigma(p-1)}{\varphi(p+1)}$ can be as large as we want. Claim. $\frac{\sigma(n)}{n}$ is unbounded. Proof. Choose $n$ such that $1,2,3,\cdots,m$ all divide $n$ (example $n=m!$). Then $\frac{\sigma(n)}{n}=\sum_{a\mid n}\frac{1}{a}\geq 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{m}=g(m)$. Since $g(m)$ is unbounded, we are done. Claim. $\frac{n}{\varphi(n)}\geq \frac{\sigma(n)}{n}$ Proof. $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$. Then $$\frac{n^2}{\sigma(n)\varphi(n)}=\sum \frac{p_i^{a_i+1}}{p_i^{a_i+1}-1}\geq 1$$ For any desired $t$, by Chinese Remainder and Dirichlet, we can choose $n=p$ prime such that the $1,2,3,\cdots,t$ all divide $p+1$. $\sigma(p-1)\geq (p-1)+\frac{p-1}{2}+2+1=\frac{3}{2}(p+1)$ so $$\frac{\sigma(p-1)}{\varphi(p+1)}\geq \frac{3}{2}\cdot\frac{p+1}{\varphi(p+1)}$$By the claims, this is unbounded and we can make it as large as we want.
07.08.2024 09:22
Another alternative for (a). We first show $\textstyle \prod_{p\in\mathbb{P},p\ge 2}\left(1-\frac1p\right) = 2/\sum_{n\ge 1}n^{-1}$. (where $\mathbb{P}$ is the set of all primes).
Next, set $n=2^k$, where $k$ will be tuned. Notice that $\sigma(\varphi(n)) = \sigma(2^{k-1})= 2^k-1$. On the other hand, $\varphi(\sigma(n)) = \varphi(2^{k+1}-1)$. Next, let $p_1<p_2<\cdots<p_L$ be the first $L$ odd primes. Choosing $k\equiv -1\pmod{p_i-1},\forall 1\le i\le L$ we obtain by Fermat's theorem that $p_i\mid 2^{k+1}-1,\forall i$. Thus, \[ \varphi(2^{k+1}-1)\le \left(2^{k+1}-1\right)\prod_{1\le i\le L}\left(1-\frac{1}{p_i}\right). \]So, \[ \frac{2^k-1}{\varphi(2^{k+1}-1)} \ge \frac{2^k-1}{2^{k+1}-1} \prod_{i\le L}\left(1-\frac{1}{p_i}\right)^{-1}\ge \frac13 \prod_{i\le L}\left(1-\frac{1}{p_i}\right)^{-1}, \]for all $k$ large. Using now the fact, we see that for $L$ large, the right hand side is arbitrarily large. This concludes part (a).
07.08.2024 12:03
AnSoLiN wrote: By the claims, this is unbounded and we can make it as large as we want. While your idea works, the argument is poorly written: Note that you cannot apply your claim as such, because it only shows that $\frac{\sigma(n)}{n}$ is unbounded, while what you want to apply is the (formally at least) much stronger claim that $\frac{\sigma(p+1)}{p+1}$ is unbounded.
07.08.2024 12:46
Tintarn wrote: AnSoLiN wrote: By the claims, this is unbounded and we can make it as large as we want. While your idea works, the argument is poorly written: Note that you cannot apply your claim as such, because it only shows that $\frac{\sigma(n)}{n}$ is unbounded, while what you want to apply is the (formally at least) much stronger claim that $\frac{\sigma(p+1)}{p+1}$ is unbounded. Dirichlet's theorem
07.08.2024 12:49
internationalnick123456 wrote: Dirichlet's theorem I'm not sure I understand your point. Of course Dirichlet was used in the proof, but it does not address the issue I raised...
20.08.2024 00:35
Here is the official solution for both $a)$ and $b)$.
23.08.2024 01:29
Amazing solution CahitArf