Olympiad Maths Prep

Library / /3 of 3

Number theory Difficulty 7.8 National olympiad, round 2 Prove it Balkan Mathematical Olympiad

Let k>2k > 2 be a given positive integer. Find all positive integers dd, for which there exists a polynomial P(x)P(x) with integer coefficients such that degP(x)=d\deg P(x) = d and 11k2025n+P(n)11^k \mid 2025^n + P(n) for all positive integers n>kn > k.

Solution

First, we will prove the following lemma:
*Lemma.* Let ff be a polynomial with rational coefficients such that f(n)f(n) is an integer for any integer nn. Then there exist integers a0,a1,,apa_0, a_1, \dots, a_p such that f(x)=i=0pai(xi)f(x) = \sum_{i=0}^{p} a_i \binom{x}{i}.
*Proof.* Let us first prove that for any polynomial with rational coefficients ff there are rational numbers a0,a1,,apa_0, a_1, \dots, a_p (where p=degf(x)p = \deg f(x)) such that f(x)=i=0pai(xi)f(x) = \sum_{i=0}^{p} a_i \binom{x}{i}.
We will prove this by induction on p=degf(x)p = \deg f(x), with the base case p=0p = 0 being clear. Assuming that p1p \ge 1 and that the result holds for polynomials of degree not exceeding p1p-1, consider a polynomial f(x)f(x) of degree pp. Then choose apa_p such that f(x)ap(xp)f(x) - a_p \binom{x}{p} has degree not exceeding p1p-1 (namely, if aa is the leading coefficient of ff, choose ap=ap!a_p = a \cdot p!). By the inductive hypothesis we can write
f(x)ap(xp)=i=0p1ai(xi) f(x) - a_p \binom{x}{p} = \sum_{i=0}^{p-1} a_i \binom{x}{i}
for some rational numbers a0,,apa_0, \dots, a_p, and thus ff has the required form. Assuming that f(n)f(n) is an integer for all integers nn, then
a1=(a0+a1)a0=f(1)f(0) a_1 = (a_0 + a_1) - a_0 = f(1) - f(0)
is an integer, as a difference of two integers. Clearly, a0=f(0)a_0 = f(0) is also an integer. Assuming that a0,,ak1a_0, \dots, a_{k-1} are integers for some k2k \ge 2, the relation
f(k)=a0(k0)+a1(k1)++ak1(kk1)+ak f(k) = a_0 \binom{k}{0} + a_1 \binom{k}{1} + \dots + a_{k-1} \binom{k}{k-1} + a_k
shows that aka_k is an integer, as well. Therefore a0,a1,,apa_0, a_1, \dots, a_p are all integers and the proof of the lemma is complete.

Now let's return to the original problem. For all n>kn > k, we have that
2025n=(2024+1)n=i=0n(ni)2024ii=0k1(ni)2024i(mod11k). 2025^n = (2024 + 1)^n = \sum_{i=0}^{n} \binom{n}{i} 2024^i \equiv \sum_{i=0}^{k-1} \binom{n}{i} 2024^i \pmod{11^k}.
Let Q(n)=i=0k1(ni)2024iQ(n) = \sum_{i=0}^{k-1} \binom{n}{i} 2024^i, which is a polynomial with rational coefficients of degree k1k-1 in nn. Then the condition is equivalent to
P(n)+Q(n)0(mod11k) P(n) + Q(n) \equiv 0 \pmod{11^k}
for all positive integers n>kn > k.
Let Q(x)=i=0k1qixiQ(x) = \sum_{i=0}^{k-1} q_i x^i and P(x)=i=0dpixiP(x) = \sum_{i=0}^{d} p_i x^i. If dk1d \ge k-1, we can select pi=qip_i = -q_i for all 0dk10 \le d \le k-1 and pi=11kp_i = 11^k for i>k1i > k-1 and the condition is satisfied. Obviously all qiq_i are rational numbers, and hence PP is a polynomial with rational coefficients.
Let pi=aibip_i = \frac{a_i}{b_i} where ai,bia_i, b_i are integers such that GCD(ai,bi)=1\text{GCD}(a_i, b_i) = 1, for all i{0,1,,k1}i \in \{0, 1, \dots, k-1\} (or if pi=0p_i = 0 we set ai=0,bi=1a_i = 0, b_i = 1). Notice that (xi)2024i=x(x1)(xi+1)12i2024i\binom{x}{i} \cdot 2024^i = \frac{x(x-1)\dots(x-i+1)}{1 \cdot 2 \dots i} \cdot 2024^i, and since

v11(i!)=i11+i112+<i=v11(2024i)v_{11}(i!) = \lfloor \frac{i}{11} \rfloor + \lfloor \frac{i}{11^2} \rfloor + \dots < i = v_{11}(2024^i), the denominator of this fraction (after reduction) is not divisible by 1111, for all i{0,1,,k1}i \in \{0, 1, \dots, k-1\}. Hence, none of the bib_i's is divisible by 1111.
Let S=LCM(b0,b1,b2,,bk1)S = \text{LCM}(b_0, b_1, b_2, \dots, b_{k-1}) and let SinvS_{inv} be an integer such that SSinv1(mod11k)S \cdot S_{inv} \equiv 1 \pmod{11^k} (SinvS_{inv} exists because SS is not divisible by 1111). Define P(x)=P(x)SSinvP'(x) = P(x) \cdot S \cdot S_{inv}. Now, first notice that P(x)P'(x) has integer coefficients (P(x)SP(x) \cdot S has integer coefficients, and multiplying it by SinvS_{inv} doesn't change that fact) and due to the construction of SinvS_{inv}, for each positive integer n>kn > k we have that P(n)P(n)(mod11k)P'(n) \equiv P(n) \pmod{11^k}.
Thus, PP' also satisfies the condition and has integer coefficients. In conclusion, all dk1d \ge k-1 satisfy the problem condition.

Now, suppose that d<k1d < k-1 and let
R(x)=P(x)+Q(x). R(x) = P(x) + Q(x).
Then degR(x)=k1\text{deg} R(x) = k-1 and R(n)11k\frac{R(n)}{11^k} is an integer for all positive integers n>kn > k (hence, in fact, for all positive integers due to the periodicity of RR modulo 11k11^k). Let
T(x)=R(x)11k=i=0k1ri11kxi. T(x) = \frac{R(x)}{11^k} = \sum_{i=0}^{k-1} \frac{r_i}{11^k} x^i.
Then the leading coefficient of T(x)T(x) is equal to
rk111k=qk111k=2024k1(k1)!11k. \frac{r_{k-1}}{11^k} = \frac{q_{k-1}}{11^k} = \frac{2024^{k-1}}{(k-1)!11^k}.
Also, using the lemma we can write
T(x)=i=0k1ai(xi) T(x) = \sum_{i=0}^{k-1} a_i \binom{x}{i}
with aiZa_i \in \mathbb{Z} for all 0ik10 \le i \le k-1. Comparing the leading coefficients we get that
2024k1(k1)!11k=ak1(k1)! \frac{2024^{k-1}}{(k-1)!11^k} = \frac{a_{k-1}}{(k-1)!}
which implies that
2024k111k=ak1Z, \frac{2024^{k-1}}{11^k} = a_{k-1} \in \mathbb{Z},
a contradiction. In conclusion, the desired positive integers dd are all such that dk1d \ge k-1.

Looking for a route rather than 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.