Maths Olympiad Prep

Library / /221 of 299

Number theory Difficulty 7.0 National Olympiad Prove it Iran

We call a natural number mm "interesting", if for all natural numbers 1nm1 \le n \le m, we can write nn as the sum of distinct divisors of mm. Prove that there are infinitely many interesting numbers of the form k2+k+2022k^2 + k + 2022.

Solution

First solution
We shall firstly prove the following lemmas,

Lemma 1. If xx is interesting and y<xy < x then xyxy is also interesting.
Proof. If n<xyn < xy, by division algorithm we have n=yq+rn = yq + r where q<xq < x, r<yr < y. Now, we can write q=diq = \sum d_i and r=dir = \sum d'_i where {di}\{d_i\} and {di}\{d'_i\} are distinct divisors of xx. Now diyd_i y, did'_i are distinct divisors of xyxy and n=diy+din = \sum d_i y + \sum d'_i.

Lemma 2. For iNi \in \mathbb{N}, 2i2^i is an interesting number.
Proof. It is clear by writing n<2in < 2^i in the basis 2.

Let P(x)=x2+x+2022P(x) = x^2 + x + 2022. If nn is an interesting number and nP(x0)n | P(x_0), then nP(r)n | P(r) where rr is the remainder of x0x_0 modulo nn. If n>2022n > 2022,
P(r)(x1)2+x1+2022<x2, P(r) \le (x-1)^2 + x - 1 + 2022 < x^2,
which implies that P(r)P(r) is an interesting number. So, it is enough to find a sequence nin_i so that 2iP(ni)2^i | P(n_i). To do this we use induction, assume that 2iP(ni)2^i | P(n_i) then
P(ni+k2i)=(n+k2i)2+ni+ki+2022P(ni)+k2i(mod2i+1) P(n_i + k 2^i) = (n + k 2^i)^2 + n_i + k_i + 2022 \equiv P(n_i) + k 2^i \pmod{2^{i+1}}
So it is enough to set k=P(ni)2ik = -\frac{P(n_i)}{2^i}.

Second solution
Here we provide a slightly different solution. Let p1<p2<<pkp_1 < p_2 < \dots < p_k be distinct prime numbers and let α1,,αk\alpha_1, \dots, \alpha_k be non-negative integers. If m=p1α1ptαtm = p_1^{\alpha_1} \dots p_t^{\alpha_t}, mm is an interesting number if and only if p1=2p_1 = 2 and pj1σ(p1α1pj1αj1)p_j - 1 \le \sigma(p_1^{\alpha_1} \dots p_{j-1}^{\alpha_{j-1}}) for 1<jk1 < j \le k. Let NMN_M be the total number of integers nn such that can be written in the form d\sum d where dd are distinct divisors of MM. It is clear that NMσ(M)N_M \le \sigma(M). For a given set SS of integers MM define SS^* to be the subset of SS containing integers such that σ(M)NM\sigma(M) - N_M is minimal.

Let MM be an interesting number and pp be a prime number such that gcd(p,M)=1\gcd(p, M) = 1 then M1=pkMM_1 = p^k M is interesting if and only if pσ(M)+1p \le \sigma(M) + 1.

The smallest divisor of M1M_1 not a divisor of MM is pp. If p>σ(M)+1p > \sigma(M) + 1 then n=1+σ(M)n = 1 + \sigma(M) defies the representation with respect to M1M_1. If pσ(M)+1p \le \sigma(M) + 1, we show by induction that pkσ(pk1M)+1p^k \le \sigma(p^{k-1} M) + 1. The base, i.e., k=1k=1 is true. Using the induction hypothesis on kk, we have
pk+1pσ(pk1M)+ppσ(pk1M)+σ(M)+1=σ(pkM)+1. p^{k+1} \le p \sigma(p^{k-1} M) + p \le p \sigma(p^{k-1} M) + \sigma(M) + 1 = \sigma(p^k M) + 1.
This shows that M1=pkMM_1 = p^k M is interesting. Considering the intervals from rpkr p^k to rpk+σ(pk1M)r p^k + \sigma(p^{k-1} M), r=0,1,,σ(M)r = 0, 1, \dots, \sigma(M). It follows that no integer in the range 1nσ(M1)1 \le n \le \sigma(M_1) is omitted from all these intervals. For the one hand, because pkσ(pk1M)+1p^k \le \sigma(p^{k-1} M) + 1 we have (r+1)pkrpk+σ(pk1M)+1(r+1) p^k \le r p^k + \sigma(p^{k-1} M) + 1. Hence, intervals are overlapping or contiguous. On the other hand the intervals include 11 and pkσ(M)+σ(pk1M)=σ(M1)p^k \sigma(M) + \sigma(p^{k-1} M) = \sigma(M_1). Thus, such nn can be written as
n=rpk+s,0rσ(M),0sσ(pk1M). n = r p^k + s, \quad 0 \le r \le \sigma(M), \quad 0 \le s \le \sigma(p^{k-1} M).
Since MM, pk1Mp^{k-1} M are interesting we can write r=Σdr = \Sigma d where dd are distinct divisors of MM and we can write s=ΣDs = \Sigma D where DD are distinct divisors of pk1Mp^{k-1} M. That is, n=Σd+ΣDn = \Sigma d' + \Sigma D. Where d=pkdd' = p^k d are distinct from DD because of involving pkp^k. While both dd', DD dividing M1M_1.

If mm is interesting and 1n1+σ(m)1 \le n \le 1 + \sigma(m) then mnmn is interesting. In part, mnmn is interesting for all 1n2m1 \le n \le 2m. Since m1m-1 is sum of divisors of mm, we have m+(m1)σ(m)m + (m-1) \le \sigma(m).

Let f(n)=n2+bn+cf(n) = n^2 + b n + c then f(n+f(n))=f(n)f(n+1)f(n + f(n)) = f(n) f(n + 1). Notice that f(n+1)=f(n)+2n+b+1f(n+1) = f(n) + 2n + b + 1 and f(n)2nb1=n(n2)+b(n1)+c10f(n) - 2n - b - 1 = n(n-2) + b(n-1) + c - 1 \ge 0. If n2n \ge 2 is an integer with f(n)f(n) an interesting number then f(n+f(n))f(n + f(n)) would also be interesting. Because, f(n+1)2f(n)f(n+1) \le 2 f(n).

Finally, we need to find at least one interesting number. Indeed, since 2024=8×11×232024 = 8 \times 11 \times 23, we find that 88 and 8×118 \times 11 are both interesting. Further, since 2×8×11232 \times 8 \times 11 \ge 23 it follows that 2024=811232024 = 8 \cdot 11 \cdot 23 is also interesting. Now, letting f(n)=n2+n+2023f(n) = n^2 + n + 2023 take a1=1a_1 = 1 and ai+1=ai+f(ai)a_{i+1} = a_i + f(a_i), i=1,2,i = 1, 2, \dots and according to the above facts, we are done. ■

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.