Maths Olympiad Prep

Library / /2 of 11

Number theory Difficulty 7.9 National Olympiad, round 2 Prove it Switzerland

Problem:

We call a positive integer silly if the sum of its positive divisors is a square. Prove that there are infinitely many silly numbers.

Solution

Solution:

Let σ(n)\sigma(n) denote the sum of all positive divisors of the integer nn, and we will order the prime numbers 2=p1<p2<p3<2=p_{1}<p_{2}<p_{3}<\ldots An important observation is that σ(n)\sigma(n) is multiplicative, in the sense that if n1,n2n_{1}, n_{2} are coprime, then σ(n1n2)=σ(n1)σ(n2)\sigma\left(n_{1} n_{2}\right)=\sigma\left(n_{1}\right) \sigma\left(n_{2}\right). More generally, we have the identity
σ(p1α1pkαk)=i=1k(1+pi++piαi) \sigma\left(p_{1}^{\alpha_{1}} \cdot \ldots \cdot p_{k}^{\alpha_{k}}\right)=\prod_{i=1}^{k}\left(1+p_{i}+\ldots+p_{i}^{\alpha_{i}}\right)
We could first try to solve the exercise in the following way: For any integer k>2k>2, consider S={p1,,pk}S=\left\{p_{1}, \ldots, p_{k}\right\} the set of the kk smallest prime numbers. We notice that all prime factors of the numbers σ(pi)\sigma\left(p_{i}\right) are smaller that pkp_{k} (since either σ(pi)<pk\sigma\left(p_{i}\right)<p_{k} or σ(pk)=pk+1\sigma\left(p_{k}\right)=p_{k}+1 is not prime). Therefore there are 2k2^{k} subsets AA of SS, but if we consider the product of all elements in AA, the sum of its divisors will only be divisible by primes among p1,,pk1p_{1}, \ldots, p_{k-1} so if we consider the parity of the exponent of each of these primes there are only 2k12^{k-1} results possible, so by the pigeonhole principle there must exist two distinct subsets AA and AA^{\prime} such that all the exponents have the same parity. Therefore the product of all the elements in the symmetric difference AΔAA \Delta A^{\prime} will be a silly number (the symmetric difference of two sets is defined as the set of all elements that belong to exactly one of the sets).
This contains most of the ideas for the solution, but the problem is that if we found sets A,AA, A^{\prime} for kk, we will also find these same sets for k+1k+1 so this argument is not enough to guarantee the existence of infinitely many silly numbers and we need a more subtle argument.
Assume that we already have ll silly numbers n1,,nln_{1}, \ldots, n_{l}. We will prove that there exist a silly number distinct of all these numbers. Let pαp_{\alpha} be the largest prime factor of one of these ll silly numbers and let γ\gamma be the largest exponent in the prime factor decompositions of these numbers. Finally let pβp_{\beta} be a prime number larger than σ(pαγ+1)\sigma\left(p_{\alpha}^{\gamma+1}\right) and consider the set
S={p1γ+1,,pαγ+1,pα+1,,pβ} S=\left\{p_{1}^{\gamma+1}, \ldots, p_{\alpha}^{\gamma+1}, p_{\alpha+1}, \ldots, p_{\beta}\right\}
Now by construction we can prove again that for each aSa \in S the prime factors of σ(a)\sigma(a) are smaller that pβp_{\beta} so we can make the same argument as before, but now the element we will construct will be distinct from all the n1,,nln_{1}, \ldots, n_{l}, since either it will be divisible by a prime number which does not divide any of these numbers, or one of the prime numbers will appear with a higher multiplicity than in any of the ll silly numbers.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.