Maths Olympiad Prep

Library / Brazilian Mathematical Olympiad /68 of 120

Brazilian Mathematical Olympiad

Number theory Difficulty 5.5 AIME, harder Prove it Brazil

Let σ(n)\sigma(n) be the sum of all positive divisors of nn, where nn is a positive integer (for instance, σ(6)=12\sigma(6) = 12 and σ(11)=12\sigma(11) = 12). We say that nn is almost perfect if σ(n)=2n−1\sigma(n) = 2n - 1 (for instance, 4 is almost perfect since σ(4)=7\sigma(4) = 7). Let nmod  kn \mod k be the remainder of the division of nn by kk and s(n)=∑1≤k≤nnmod  ks(n) = \sum_{1 \le k \le n} n \mod k (for instance, s(6)=0+0+0+2+1+0=3s(6) = 0 + 0 + 0 + 2 + 1 + 0 = 3 and s(11)=0+1+2+3+1+5+4+3+2+1+0=22s(11) = 0 + 1 + 2 + 3 + 1 + 5 + 4 + 3 + 2 + 1 + 0 = 22). Prove that nn is almost perfect if and only if s(n)=s(n−1)s(n) = s(n-1).

Solution

s(n)=s(n−1)  ⟺  ∑1≤k≤nn mod k=∑1≤k≤n−1(n−1) mod k  ⟺  ∑1≤k≤nn mod k=∑1≤k≤n−1((n mod k)−1)+∑1≤k≤n−1k∤nk  ⟺  ∑1≤k≤n−11=σ(n)−n  ⟺  2n−1=σ(n) \begin{align*} s(n) = s(n-1) &\iff \sum_{1 \le k \le n} n \bmod k = \sum_{1 \le k \le n-1} (n-1) \bmod k \\ &\iff \sum_{1 \le k \le n} n \bmod k = \sum_{1 \le k \le n-1} ((n \bmod k) - 1) + \sum_{\substack{1 \le k \le n-1 \\ k \nmid n}} k \\ &\iff \sum_{1 \le k \le n-1} 1 = \sigma(n) - n \\ &\iff 2n - 1 = \sigma(n) \end{align*}

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

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