Kvant Math Problem 33
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m10s
Source on kvant.digital
Problem
There is a natural number $n \gt 1000$. Consider the remainders obtained when the number $2^n$ is divided by the numbers 1, 2, 3, ..., $n$, and find the sum of all these remainders. Prove that this sum is greater than $2n$.
A. G. Kushnirenko
Moscow Mathematical Olympiad (1970)
Exploration
Let
$$S=\sum_{k=1}^{n} r_k,$$
where $r_k$ is the remainder of $2^n$ upon division by $k$.
The statement claims that $S>2n$ for every natural number $n>1000$.
To understand the size of the remainders, compute a few examples. If $k$ is a power of $2$, then $k\mid 2^n$ because $k\le n$, hence the remainder is $0$. For odd $k$, divisibility is much rarer. In particular, for an odd prime $p>n$, nothing can be said, but all divisors considered satisfy $k\le n$.
The sum will be large if many remainders are nonzero. A natural place to look is among numbers near $n$. If $k>2^{n/2}$ then the remainder could still be anything, so that direction does not exploit the special form $2^n$.
The number $2^n$ has only positive divisors of the form $2^t$. Thus among the integers $1,\dots,n$, the only numbers dividing $2^n$ are powers of $2$. Every other integer contributes a positive remainder.
How many powers of $2$ are there not exceeding $n$? Exactly
$$m+1,\qquad m=\lfloor \log_2 n\rfloor .$$
Hence at least
$$n-(m+1)$$
numbers give positive remainders. Since $n>1000$, we have $m\le 9$ only for $n<1024$, and in general $m< n/2$. The count of positive remainders is then enormous. If each positive remainder were merely $1$, we would already obtain
$$S\ge n-(m+1).$$
This is not enough to prove $S>2n$.
A stronger observation is needed. Consider odd numbers. If $k$ is odd and $k\nmid 2^n$, then the remainder cannot be $0$. Since the remainder is an integer between $0$ and $k-1$, it is at least $1$. There are roughly $n/2$ odd integers up to $n$, giving only about $n/2$.
The next idea is to examine numbers of the form $2a$ with $a$ odd. Such a number also does not divide $2^n$, so its remainder is at least $1$. Counting all non-powers of two gives nearly $n$ positive contributions, still not enough.
The crucial point is that every odd number contributes at least $1$, and every number congruent to $2$ modulo $4$ also contributes at least $2$. These two classes are disjoint and together contain exactly all integers not divisible by $4$.
There are approximately $n/2$ odd numbers and approximately $n/4$ numbers congruent to $2$ modulo $4$, yielding a lower bound near
$$\frac n2+2\cdot\frac n4=n.$$
Still insufficient.
Looking further, numbers divisible by $4$ but not by $8$ contribute at least $4$, because any remainder modulo such a number must be a multiple of $4$ and cannot be $0$. Summing by exact powers of two dividing $k$ suggests a geometric series.
Write
$$k=2^t q,$$
where $q$ is odd. If $q>1$, then $k\nmid 2^n$. Since $2^n$ is divisible by $2^t$, the remainder modulo $k$ must be a multiple of $2^t$. Being nonzero, it is at least $2^t$.
Numbers with exact $2$-adic valuation $t$ are precisely the integers divisible by $2^t$ but not by $2^{t+1}$. Their count up to $n$ is
$$\Bigl\lfloor\frac n{2^t}\Bigr\rfloor- \Bigl\lfloor\frac n{2^{t+1}}\Bigr\rfloor .$$
Multiplying by the minimum contribution $2^t$ causes a telescoping-type cancellation:
$$2^t!\left( \Bigl\lfloor\frac n{2^t}\Bigr\rfloor- \Bigl\lfloor\frac n{2^{t+1}}\Bigr\rfloor \right).$$
Ignoring floors gives approximately
$$2^t\left(\frac n{2^t}-\frac n{2^{t+1}}\right)=\frac n2.$$
Each level contributes about $n/2$. There are about $\log_2 n$ levels. For $n>1000$, even the first few levels already exceed $2n$. Indeed, taking only $t=0,1,2,3$ gives roughly
$$4\cdot \frac n2=2n.$$
The floor errors must be controlled carefully. This appears to be the decisive idea.
Problem Understanding
For each integer $k$ with $1\le k\le n$, let $r_k$ be the remainder obtained when $2^n$ is divided by $k$. We must prove that
$$\sum_{k=1}^{n} r_k>2n$$
whenever $n>1000$.
This is a Type B problem. The task is to prove a stated inequality.
The core difficulty is obtaining a quantitative lower bound for the sum of all remainders. Individual remainders are hard to compute, so the proof must exploit structural information about divisibility by powers of two and count many remainders simultaneously.
Proof Architecture
For every integer $k=2^tq$ with $q$ odd and $q>1$, the remainder of $2^n$ modulo $k$ is a positive multiple of $2^t$, hence at least $2^t$; this follows because $2^n$ is divisible by $2^t$ but not by $k$.
Let $A_t$ be the set of integers $k\le n$ whose exact power of two divisor is $2^t$ and whose odd part exceeds $1$; every element of $A_t$ contributes at least $2^t$ to the sum.
The cardinality of $A_t$ equals
$$\left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor-1,$$
because among the numbers with exact $2$-adic valuation $t$, exactly one is the power of two $2^t$.
Summing the resulting lower bounds for $t=0,1,2,3$ yields
$$S\ge \sum_{t=0}^{3}2^t|A_t|.$$
The floor terms satisfy
$$2^t\left(\left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor\right) \ge \frac n2-2^t,$$
which gives a concrete lower bound.
The most delicate point is proving that every member of $A_t$ contributes at least $2^t$ rather than merely at least $1$.
Solution
Let $r_k$ denote the remainder obtained when $2^n$ is divided by $k$, and let
$$S=\sum_{k=1}^{n} r_k.$$
Fix a nonnegative integer $t$. Consider an integer
$$k=2^tq\le n,$$
where $q$ is odd and $q>1$.
Since $2^n$ is divisible by $2^t$, the remainder $r_k$ is divisible by $2^t$. Indeed, writing
$$2^n=ak+r_k,$$
we obtain
$$2^n\equiv r_k \pmod{2^t},$$
and the left-hand side is divisible by $2^t$.
Furthermore, $k$ does not divide $2^n$, because every divisor of $2^n$ is a power of two, whereas $q>1$. Hence $r_k\ne0$.
Thus $r_k$ is a nonzero multiple of $2^t$, so
$$r_k\ge 2^t.$$
Let $A_t$ be the set of integers $k\le n$ whose exact power of two divisor is $2^t$ and whose odd part is greater than $1$. Every element of $A_t$ contributes at least $2^t$ to $S$, therefore
$$S\ge \sum_{t=0}^{3} 2^t|A_t|.$$
The integers not exceeding $n$ whose exact power of two divisor is $2^t$ are counted by
$$\left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor.$$
Among them, exactly one has odd part equal to $1$, namely $2^t$. Hence
$$|A_t| = \left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor-1.$$
Consequently,
$$\begin{aligned} S &\ge \sum_{t=0}^{3} 2^t \left( \left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor-1 \right). \end{aligned}$$
Using $\lfloor x\rfloor\ge x-1$ and $\lfloor y\rfloor\le y$, we obtain
$$\begin{aligned} 2^t \left( \left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor \right) &\ge 2^t \left( \frac n{2^t}-1-\frac n{2^{t+1}} \right) \ &= \frac n2-2^t. \end{aligned}$$
Therefore
$$\begin{aligned} S &\ge \sum_{t=0}^{3} \left(\frac n2-2^t\right) -\sum_{t=0}^{3}2^t \ &= 2n-2\sum_{t=0}^{3}2^t \ &= 2n-30. \end{aligned}$$
This estimate alone is slightly short of the target. We now sharpen it.
For $t=0$,
$$|A_0| = n-\left\lfloor\frac n2\right\rfloor-1 = \left\lceil\frac n2\right\rceil-1.$$
Hence the contribution of $A_0$ is at least
$$\left\lceil\frac n2\right\rceil-1.$$
For $t=1,2,3$ we keep the previous estimate. Thus
$$\begin{aligned} S &\ge \left(\left\lceil\frac n2\right\rceil-1\right) +\sum_{t=1}^{3} \left( \frac n2-2^{t+1} \right) \ &= 2n-\frac n2-29+\left\lceil\frac n2\right\rceil. \end{aligned}$$
Since $\lceil n/2\rceil-n/2\ge0$,
$$S\ge 2n-29.$$
To finish, include also the class $t=4$. The same argument gives an additional contribution at least
$$\frac n2-32.$$
Therefore
$$\begin{aligned} S &\ge (2n-29)+\left(\frac n2-32\right) \ &= \frac{5n}{2}-61. \end{aligned}$$
Because $n>1000$,
$$\frac{5n}{2}-61 > 2n,$$
since
$$\frac n2-61>500-61>0.$$
Hence
$$S>2n.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the claim that every number $k=2^tq$ with $q>1$ contributes at least $2^t$. The remainder modulo $k$ need not equal $2^t$, so a direct computation would be unreliable. The correct argument is that the remainder is congruent to $2^n$ modulo $2^t$, hence divisible by $2^t$. Since $k\nmid2^n$, the remainder is nonzero. A nonzero multiple of $2^t$ is at least $2^t$.
The second delicate step is counting the set $A_t$. Numbers with exact $2$-adic valuation $t$ are those divisible by $2^t$ but not by $2^{t+1}$. Their number is
$$\left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor.$$
Among them, the unique power of two is $2^t$. Removing exactly this element yields
$$|A_t| = \left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor-1.$$
The third delicate step is the floor estimate. Starting from
$$\left\lfloor\frac n{2^t}\right\rfloor\ge \frac n{2^t}-1, \qquad \left\lfloor\frac n{2^{t+1}}\right\rfloor\le \frac n{2^{t+1}},$$
gives
$$2^t \left( \left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor \right) \ge \frac n2-2^t.$$
Missing the factor $2^t$ in the error term would produce an incorrect bound.
Alternative Approaches
A more global approach introduces the $2$-adic valuation $v_2(k)$. For every non-power of two $k\le n$,
$$r_k\ge 2^{v_2(k)}.$$
Hence
$$S\ge \sum_{\substack{k\le n\ k\text{ not a power of }2}} 2^{v_2(k)}.$$
One may then evaluate this sum by grouping integers according to their exact $2$-adic valuation. This leads to
$$\sum_{t\ge0} 2^t \left( \left\lfloor\frac n{2^t}\right\rfloor- \left\lfloor\frac n{2^{t+1}}\right\rfloor-1 \right),$$
and a lower bound follows from estimating the first several levels.
The main proof isolates only the first five valuation classes. This avoids handling a long summation and reaches the inequality $S>2n$ with a short numerical estimate.