Maths Olympiad Prep

Library / /4 of 6

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)=2n1\sigma(n) = 2n - 1 (for instance, 4 is almost perfect since σ(4)=7\sigma(4) = 7). Let nmodkn \mod k be the remainder of the division of nn by kk and s(n)=1knnmodks(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(n1)s(n) = s(n-1).

Solution

s(n)=s(n1)    1knnmodk=1kn1(n1)modk    1knnmodk=1kn1((nmodk)1)+1kn1knk    1kn11=σ(n)n    2n1=σ(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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.