Given a natural number $n$. Prove that you can choose $ \phi (n)+1 $ (not necessarily different) divisors $n$ with the sum $n$. Here $ \phi (n)$ denotes the number of natural numbers less than $n$ that are coprime with $n$. (Fedir Yudin)
Problem
Source: 2021 Ukraine NMO 10.8 11.7
Tags: number theory, Divisors
08.05.2021 09:18
parmenides51 : Ukraine MO 2021/10.8/11.7 wrote: Given a natural number $n$. Prove that you can choose $ \phi (n)+1 $ (not necessarily different) divisors $n$ with the sum $n$. (Fedir Yudin) Absolutely beautiful! though it took me more time to finish than I expected. Some definition. Firstly, as a sidenote, let me explain the reason behind defining the following, that's because of the second claim I guess (you may hate me for this). Call a positive integer $n$ lucky if it can be written as the sum of $\phi(n)+1$ (not necessarily distinct) divisors of it , at least three of which are ones. Note that being lucky is a sufficient but not a necessary condition, so if the number can be written in desired form with less than $3$ ones involved (or at least if we can't guarantee that) we let it be pseudo-lucky. Claim. All prime powers are lucky except for $2$ and $4$. Proof. Note that $$p^t=\underbrace{1+\cdots+1}_{\phi(p^t)}+p^{t-1}$$$\square.$ Claim. If $q, r$ with $(q, r)=1$ are lucky, then so is $qr$. Proof. By definition $$q=a_{1}+\cdots+a_{\phi(q)-2}+1+1+1$$$$r=b_{1}+\cdots+b_{\phi(r)-2}+1+1+1$$Thus by direct expansion (with some manipulation) $$(a_{1}+\cdots+a_{\phi(q)-2})(b_{1}+\cdots+b_{\phi(r)-2})+(1+1)(a_{1}+\cdots+a_{\phi(q)-2})+(1+1)(b_{1}+\cdots+b_{\phi(r)-2})+q+r+1+1+1$$is the lucky representation of $qr$ $\square.$ Claim. For odd $n\in \mathbb{N}$, $2n$ and $4n$ are pseudo-lucky. Proof. It's obvious for $2n$ , so let $2n=b_{1}+\cdots+b_{\phi(n)+1}$ then $$4n=2(b_1+\cdots+b_{\phi(n)})+2b_{\phi(n)+1}$$. $\square$ From the results proven above it follows that any $n\in \mathbb{N}$ has the desired property. $\mathbb{Q.E.D.}$