Problem A. 924. (January 2026)

A. 924. For which pairs $\displaystyle (k,l)$ of positive integers is the following statement true: for every positive integer $\displaystyle n$ there exists an integer $\displaystyle i$ with $\displaystyle 0\le i\le l-1$ such that $\displaystyle \binom{n}{i}+{(-1)}^l\binom{n}{i+l}+{(-1)}^{2l}\binom{n}{i+2l}+\dots$ is not divisible by $\displaystyle k$?

(Based on a Kvant problem)

(7 pont)

Deadline expired on February 10, 2026.

Solution 1: During the solution we will use the following notation: for integer-coefficient polynomials $\displaystyle a(x)$, $\displaystyle b(x)$, $\displaystyle m(x)$

$\displaystyle a(x) \equiv b(x) \pmod{m(x)}, $

if there exists an integer-coefficient polynomial $\displaystyle h(x)$ such that $\displaystyle a(x)-b(x)=h(x)m(x)$. Furthermore, if each coefficient of an integer-coefficient polynomial $\displaystyle a(x)$ is divisible by $\displaystyle k$, then we say that the polynomial $\displaystyle a(x)$ is divisible by $\displaystyle k$.

Fix $\displaystyle l$, and let

$\displaystyle A_{n,i}=\binom{n}{i}+ (-1)^l\binom{n}{i+l}+(-1)^{2l}\binom{n}{i+2l}+\ldots$

be the expression in the problem, and consider the

$\displaystyle R_n(x) = \sum_{i=0}^{l-1}(-1)^iA_{n,i}x^i $

polynomial. The question of the problem is for which $\displaystyle n$ it is true that $\displaystyle R_n(x)$ is not divisible by $\displaystyle k$ for any $\displaystyle n$.

Lemma 1.

$\displaystyle R_n(x) \equiv (1-x)^n \pmod{x^l-1}. $

Proof. Notice that

$$\begin{align*} R_n(x)-(1-x)^n &= \sum_{i=0}^{l-1}(-1)^i\bigg( \binom{n}{i}+ (-1)^l\binom{n}{i+l} +\ldots \bigg)x^i - \sum_{i=0}^{n}(-1)^i\binom{n}{i}x^i= \\ &= \sum_{i=0}^{l-1}(-1)^i \bigg((-1)^l\binom{n}{i+l}(1-x^l)+(-1)^{2l}\binom{n}{i+2l}(1-x^{2l})+\ldots\bigg)x^i \end{align*}$$

is divisible by the polynomial $\displaystyle x^l-1$. $\displaystyle \Box$

Lemma 2. If for some $\displaystyle n$ the polynomial $\displaystyle R_n(x)$ is divisible by $\displaystyle k$, then $\displaystyle R_{n+1}(x)$ is also divisible by $\displaystyle k$.

Proof. Let the coefficient of $\displaystyle x^{l-1}$ in $\displaystyle R_n(x)$ be $\displaystyle c$. Then

$\displaystyle R_{n+1}(x) \equiv (1-x)^{n+1} \equiv (1-x)R_n(x) \equiv (1-x)R_n(x)+c(x^l-1) \pmod{x^l-1}, $

$\displaystyle x^l-1 \,\big|\, R_{n+1}(x)-(1-x)R_n(x)-c(x^l-1). $

In the latter polynomial the $\displaystyle x^l$ term cancels, thus its degree is less than $\displaystyle n$; the divisibility can hold only for the constant $\displaystyle 0$ polynomial, hence

$\displaystyle R_{n+1}(x) = (1-x)R_n(x)+c(x^l-1). $

Since the coefficients of $\displaystyle R_n(x)$ and $\displaystyle c$ are divisible by $\displaystyle k$, the same is true for $\displaystyle R_{n+1}(x)$. $\displaystyle \Box$

Now we divide the problem into several cases. Assume that $\displaystyle k,l\ge 2$, since for $\displaystyle k=1$ or $\displaystyle l=1$ the statement of the problem is obviously not true ($\displaystyle l=1$ gives $\displaystyle 0$ for $\displaystyle n=1$).

Case 1: $\displaystyle l$ has a prime divisor that is different from some prime divisor $\displaystyle p$ of $\displaystyle k$.

Take an arbitrary positive integer $\displaystyle n$, and let $\displaystyle t$ be such a large positive integer that $\displaystyle p^t\ge n$.

Consider the polynomial $\displaystyle R_{p^t}(x)$. Since $\displaystyle l$ has a prime divisor different from $\displaystyle p$, $\displaystyle l$ cannot divide $\displaystyle p^t$.

In the sum

$\displaystyle A_{p^t,0} = \binom{p^t}{0}+ (-1)^l\binom{p^t}{l}+(-1)^{2l}\binom{p^t}{2l}+\ldots, $

we have $\displaystyle \binom{p^t}{0}=1$, and $\displaystyle \binom{p^t}{p^t}$ does not appear, because $\displaystyle p^t$ is not a multiple of $\displaystyle l$. All other binomial coefficients appearing in the sum are divisible by $\displaystyle p$. Hence $\displaystyle A_{p^t,0}\equiv1\pmod{p}$, and thus the polynomial $\displaystyle R_{p^t}(x)$ cannot be divisible by $\displaystyle p$.

By Lemma 2, if $\displaystyle R_n(x)$ were divisible by $\displaystyle p$, then $\displaystyle R_{n+1}(x),R_{n+2}(x),\ldots,$ would also be divisible by $\displaystyle p$, but as we have seen, $\displaystyle R_{p^t}(x)$ is not divisible by $\displaystyle p$. Thus we obtain that $\displaystyle R_n(x)$ is not divisible by $\displaystyle p$ for any $\displaystyle n$, and hence not by $\displaystyle k$ either (since $\displaystyle p\mid k$).

Case 2: if the previous statement does not hold for $\displaystyle l$ and $\displaystyle k$, then $\displaystyle l$ can have only one type of prime divisor. If $\displaystyle k$ had a different prime divisor, then the previous statement would also hold for $\displaystyle l$ and $\displaystyle k$. Thus the remaining case is when both $\displaystyle l$ and $\displaystyle k$ are powers of the same prime $\displaystyle p$.

Let $\displaystyle l=p^s$ and $\displaystyle k=p^t$. We claim that $\displaystyle R_{tp^{s}}(x)$ is divisible by $\displaystyle p^t$. If $\displaystyle t=1$, then

$$\begin{align*} R_{p^s}(x) =(1-x)^{p^s}-(-1)^p(x^{p^s}-1) =\sum_{i=1}^{p^s-1}(-1)^s\binom{p^s}{i}x^i+\big(1+(-1)^{p}\big); \end{align*}$$

In the sum each $\displaystyle \binom{p^s}{i}$ is divisible by $\displaystyle p$. If $\displaystyle p$ is odd, then the last two terms cancel, while if $\displaystyle p=2$, then $\displaystyle 1+(-1)^{p}=2$ is divisible by $\displaystyle 2$, thus the polynomial $\displaystyle R_{p^s}(x)$ is indeed divisible by $\displaystyle p$.

If now $\displaystyle t$ is arbitrary, then with the notation $\displaystyle q(x)=\frac1p \left(\sum_{i=1}^{p^s-1}(-1)^s\binom{p^s}{i}x^i+\big(1+(-1)^{p}\big)\right)$

$\displaystyle (1-x)^{tp^{s}}=\left((1-x)^{p^s}\right)^t=\left(p\cdot q(x)+(-1)^p(x^{p^s}-1)\right)^t=p^t\cdot q^t(x)+(x^{p^s}-1)\cdot r(x) $

with a suitable polynomial $\displaystyle r(x)$, that is $\displaystyle (1-x)^{tp^{s}}\equiv p^t\cdot q^t(x) \pmod{x^{p^s}-1}$, and thus we have proved the claim.

Summarizing,

If there exists a prime number of which both $\displaystyle k$ and $\displaystyle l$ are powers or $\displaystyle k=1$ or $\displaystyle l=1$, then the statement of the problem is not true,
Otherwise (that is, we can find primes $\displaystyle p\neq q$ such that $\displaystyle p\mid k$, $\displaystyle q\mid l$), then the statement of the problem is true.

Solution 2: The statement of the problem is obviously not true if $\displaystyle k=1$ or $\displaystyle l=1$, therefore assume that $\displaystyle k,l\ge2$. Reformulate the problem. Fix $\displaystyle l$. Then by varying $\displaystyle n$ and $\displaystyle i$ we can obtain the results in the following way: write $\displaystyle l$ numbers on a circle, initially one $\displaystyle 1$ and otherwise all $\displaystyle 0$ (this is exactly the value of the formula for $\displaystyle n=0$ and $\displaystyle i=0,1,2,\ldots ,l-1$). Then in each step take the numbers written on the circle, $\displaystyle a_0,a_1,\ldots ,a_{l-1}$, and instead of them write the differences of neighboring ones, that is write the numbers $\displaystyle a_1-a_0,a_2-a_1,\ldots ,a_0-a_{l-1}$. By complete induction it can be proved that in the $\displaystyle n$-th step, up to sign, we obtain exactly the values of the formula for the given $\displaystyle l$ and $\displaystyle i=0,1,\ldots ,l-1$. The problem reformulated is therefore for which $\displaystyle l$ it will be true that after every step there will be at least one number on the circle not divisible by $\displaystyle k$.

The key of the solution is the observation that if the statement of the problem is not true, that is sooner or later all $\displaystyle 0$ (mod $\displaystyle k$) appears on the circle, then this is also true if we start from arbitrary $\displaystyle l$ integers on the circle. The reason is that by rotational symmetry the initial $\displaystyle 1$ can be anywhere on the circle, and that as linear combinations of such initial states (one $\displaystyle 1$ somewhere, otherwise all $\displaystyle 0$) any initial $\displaystyle l$-tuple can be obtained, and furthermore the formation rule is linear. It also follows that if in the $\displaystyle N$-th step we obtain all $\displaystyle 0$ from the initial state consisting of one $\displaystyle 1$ and otherwise all $\displaystyle 0$, then for any initial state we will also obtain all $\displaystyle 0$ on the circle after $\displaystyle N$ steps.

First we show that if $\displaystyle k$ has a prime divisor $\displaystyle p$ which does not divide $\displaystyle l$, then this does not hold (that is the original statement of the problem is true). For this it is enough to show that for arbitrarily many steps there exists an initial state which does not become zero modulo $\displaystyle p$ after the given number of steps (here lies the essence: although originally we should have shown this for a concrete $\displaystyle l$-tuple, it turns out that if as a function of the number of steps we show different $\displaystyle l$-tuples which do not become zero, that is equivalent to this). We show this by proving that if there exists an initial state which does not become zero in $\displaystyle \ell$ steps, then there also exists one which does not become zero in $\displaystyle \ell+1$ steps. The idea is that if $\displaystyle a_0,a_1,\ldots, a_{l-1}$ does not become zero in $\displaystyle \ell$ steps, then neither does $\displaystyle a_0+c,a_1+c,\ldots, a_{l-1}+c$, since after the first step we obtain the same $\displaystyle l$-tuple on the circle. If we could find an $\displaystyle l$-tuple $\displaystyle b_0,\ldots ,b_{l-1}$ from which after one step we obtain the $\displaystyle l$-tuple $\displaystyle a_0+c,\ldots ,a_{l-1}+c$ (mod $\displaystyle p$), we would be done. We can obtain an $\displaystyle l$-tuple by performing one step modulo $\displaystyle p$ exactly if the sum of the $\displaystyle l$ numbers to be obtained is $\displaystyle 0$ mod $\displaystyle p$, that is we should choose $\displaystyle c$ such that $\displaystyle a_0+\ldots +a_{l-1}+lc$ is $\displaystyle 0$ mod $\displaystyle p$: this is possible if $\displaystyle p\nmid l$, since then the remainder of $\displaystyle lc$ can be anything mod $\displaystyle p$ with a suitable choice of $\displaystyle c$. One must also pay attention that we need an $\displaystyle l$-tuple with which at least one step can be performed without becoming zero, and this is possible since $\displaystyle l\ge 2$.

It also follows that if $\displaystyle l$ has a divisor greater than $\displaystyle 1$ that is relatively prime to $\displaystyle p$ (let this be $\displaystyle l_0$), then the statement of the problem also holds. Take $\displaystyle b_0,b_1,\ldots ,b_{l_0-1}$ with which the circle does not become zero for $\displaystyle \ell$ steps: by the previous paragraph this is possible. Then let $\displaystyle a_i=b_j$ if $\displaystyle l_0\mid i-j$: it is easy to see that this also does not become zero in $\displaystyle \ell$ steps (since on a segment of length $\displaystyle l_0$ exactly the same happens on the larger circle as when we wrote only $\displaystyle l_0$ numbers on the circle).

Thus finally we obtained that if $\displaystyle k$ has a prime divisor $\displaystyle p$ for which $\displaystyle l$ has a prime divisor different from $\displaystyle p$, then the statement of the problem is true. This holds if $\displaystyle k$ has at least $\displaystyle 2$ prime divisors. If $\displaystyle k$ is a prime power and $\displaystyle l$ is not a power of the same prime, then the statement also holds.

Now we show that if $\displaystyle k=p^t$ and $\displaystyle l=p^s$, then we will obtain all $\displaystyle 0$ residues mod $\displaystyle k=p^t$. This is simple if $\displaystyle t=1$, using the known statement that $\displaystyle p\mid \binom{p^s}{i}$ if $\displaystyle i\neq 0,p^s$, thus $\displaystyle n=p^s$ will work, because $\displaystyle \binom{p^s}{0}$ and $\displaystyle \binom{p^s}{p^s}$ cancel each other in the case $\displaystyle i=0$, while in the other cases one has to sum only binomial coefficients divisible by $\displaystyle p$.

Finally, by complete induction on $\displaystyle t$ we can justify the above statement, again using the circular reformulation: we have seen that in the case $\displaystyle l=p^s$ after some (namely $\displaystyle p^s$) steps every number becomes divisible by $\displaystyle p$; then after the same number of additional steps every number becomes divisible by $\displaystyle p^2$ (since divisibility by $\displaystyle p$ holds starting from any $\displaystyle l$-tuple), and repeating this $\displaystyle t-1$ times (that is after altogether $\displaystyle tp^{s}$ steps) we reach divisibility by $\displaystyle p^t$.

Thus the answer to the problem is: except for the pairs $\displaystyle k=p^t$, $\displaystyle l=p^s$, the statement of the problem will be true for $\displaystyle k,l\ge 2$, and it will not be true if $\displaystyle k=1$ or $\displaystyle l=1$.

Statistics:

13 students sent a solution.

7 points: Bodor Mátyás, Bolla Donát Andor, Gyenes Károly.

6 points: Aravin Peter, Szakács Ábel, Xiaoyi Mo.

4 points: 2 students.

3 points: 1 student.

1 point: 2 students.

0 point: 2 students.

Problems in Mathematics of KöMaL, January 2026

13 students sent a solution.
7 points:	Bodor Mátyás, Bolla Donát Andor, Gyenes Károly.
6 points:	Aravin Peter, Szakács Ábel, Xiaoyi Mo.
4 points:	2 students.
3 points:	1 student.
1 point:	2 students.
0 point:	2 students.

Already signed up?
New to KöMaL?