Find the largest integer $N \in \{1, 2, \ldots , 2019 \}$ such that there exists a polynomial $P(x)$ with integer coefficients satisfying the following property: for each positive integer $k$, $P^k(0)$ is divisible by $2020$ if and only if $k$ is divisible by $N$. Here $P^k$ means $P$ applied $k$ times, so $P^1(0)=P(0), P^2(0)=P(P(0)),$ etc.
Problem
Source: USA TST for EGMO 2020, Problem 6
Tags: algebra, polynomial, Integer Polynomial, Periodic sequence, modular arithmetic, TST
28.01.2020 02:47
Since no one's posted a solution yet (I guess all the attention is on the nearly-identical IMO TST p5), I will post one here for aesthetic purposes.
28.01.2020 15:23
Personally, I think EGMO TST #03 is much harder than this. The answer is $N = \boxed{1980}$. Define a period modulo $n$ as $p$ if $p$ is the smallest positive integer such that $P^p(0) \equiv 0 \ (\text{mod} \ n)$. Call the set of possible periods modulo $n$ as $P_n$. We wanted to determine the largest element of $P_{2020}$. Let it be $k$. Notice that if $P^k(0) \equiv 0 \ (\text{mod} \ 2020)$, then $P^k(0) \equiv 0 \ (\text{mod} \ 4)$, $P^k (0) \equiv 0 \ (\text{mod} \ 5)$, and $P^k(0) \equiv 0 \ (\text{mod} \ 101)$. Therefore, \[ k = \text{LCM}_{x_i \in P_4, x_j \in P_5, x_k \in P_{101} }( x_i, x_j, x_k)\] Claim 01. The set of residues $\{ 0, P(0), \dots, P^{p - 1}(0) \}$ must all be distinct. Proof. Suppose otherwise, there exists a cycle. Obviously this cycle doesn't pass through $0$ or otherwise this contradicts the minimality of $p$, and therefore the cycle will never pass $0$, eventually, and hence $P^k (0) \equiv 0 \ (\text{mod} \ 2020)$ has no solution in $k$. Claim 02. $P_4 = \{ 1, 2, 4 \}$. Proof. Consider the polynomial $P(x) = x, P(x) = x + 2, P(x) = x + 1$ for each cases. Now, we'll prove that $3 \notin P_4$. Let the polynomial be $P(x) = xQ(x) + c$. If $c$ is even, then $P(x)$ will always be even and can only cover at most $2$ residues modulo $4$. Therefore, $c$ has to be odd. Suppose $3 \in P_4$, then $P^k(0)$ cover all residues except for one, and by the previous reasoning, it must be an even integer. (This is because all even integers are mapped to odd, and therefore the number of odd integers must be $\ge$ than the number of even integers.) Therefore, $P(0), P^2 (0), P^3 (0)$ must all be odd. But this creates a cycle and contradicts Claim 01. Claim 03. $p - 2, p - 1, p \in P_p$ for every odd prime $p$. Proof. The construction for prime $p$: Consider the polynomial $P(x) = x + 1$. Otherwise, consider \[ P(x) = x + 4 - 2(x + 4)^{p - 1} \]We claim that this polynomial has period $p - 1$. Notice that $P(x)$ has the value of $P(x) = x + 2$ when $x \not= -4$ by Fermat Little Theorem. Moreover, it attains the value of $P(x) = x + 4$ when $x = -4$. Therefore, it won't achieve the point of $x = -2$. Easy check gives us it passes through all other points. Construction for $p - 2$ is similar to the ones to $p - 1$. Consider \[ P(x) = x + 6 - 4(x + 6)^{p - 1} \] Since $k < 2020$, we have $k = 4 \times 5 \times 99 = \boxed{1980}$. Since $\gcd(4,5,99) = 1$, we can construct such polynomial by Chinese Remainder Theorem.
12.03.2020 19:58
How both of you are constructing such polynomials in case of prime from nowhere? IndoMathXdZ wrote: Personally, I think EGMO TST #03 is much harder than this. The answer is $N = \boxed{1980}$. Define a period modulo $n$ as $p$ if $p$ is the smallest positive integer such that $P^p(0) \equiv 0 \ (\text{mod} \ n)$. Call the set of possible periods modulo $n$ as $P_n$. We wanted to determine the largest element of $P_{2020}$. Let it be $k$. Notice that if $P^k(0) \equiv 0 \ (\text{mod} \ 2020)$, then $P^k(0) \equiv 0 \ (\text{mod} \ 4)$, $P^k (0) \equiv 0 \ (\text{mod} \ 5)$, and $P^k(0) \equiv 0 \ (\text{mod} \ 101)$. Therefore, \[ k = \text{LCM}_{x_i \in P_4, x_j \in P_5, x_k \in P_{101} }( x_i, x_j, x_k)\] Claim 01. The set of residues $\{ 0, P(0), \dots, P^{p - 1}(0) \}$ must all be distinct. Proof. Suppose otherwise, there exists a cycle. Obviously this cycle doesn't pass through $0$ or otherwise this contradicts the minimality of $p$, and therefore the cycle will never pass $0$, eventually, and hence $P^k (0) \equiv 0 \ (\text{mod} \ 2020)$ has no solution in $k$. Claim 02. $P_4 = \{ 1, 2, 4 \}$. Proof. Consider the polynomial $P(x) = x, P(x) = x + 2, P(x) = x + 1$ for each cases. Now, we'll prove that $3 \notin P_4$. Let the polynomial be $P(x) = xQ(x) + c$. If $c$ is even, then $P(x)$ will always be even and can only cover at most $2$ residues modulo $4$. Therefore, $c$ has to be odd. Suppose $3 \in P_4$, then $P^k(0)$ cover all residues except for one, and by the previous reasoning, it must be an even integer. (This is because all even integers are mapped to odd, and therefore the number of odd integers must be $\ge$ than the number of even integers.) Therefore, $P(0), P^2 (0), P^3 (0)$ must all be odd. But this creates a cycle and contradicts Claim 01. Claim 03. $p - 2, p - 1, p \in P_p$ for every odd prime $p$. Proof. The construction for prime $p$: Consider the polynomial $P(x) = x + 1$. Otherwise, consider \[ P(x) = x + 4 - 2(x + 4)^{p - 1} \]We claim that this polynomial has period $p - 1$. Notice that $P(x)$ has the value of $P(x) = x + 2$ when $x \not= -4$ by Fermat Little Theorem. Moreover, it attains the value of $P(x) = x + 4$ when $x = -4$. Therefore, it won't achieve the point of $x = -2$. Easy check gives us it passes through all other points. Construction for $p - 2$ is similar to the ones to $p - 1$. Consider \[ P(x) = x + 6 - 4(x + 6)^{p - 1} \] Since $k < 2020$, we have $k = 4 \times 5 \times 99 = \boxed{1980}$. Since $\gcd(4,5,99) = 1$, we can construct such polynomial by Chinese Remainder Theorem. alifenix- wrote: Since no one's posted a solution yet (I guess all the attention is on the nearly-identical IMO TST p5), I will post one here for aesthetic purposes.
13.03.2020 01:16
I can try to answer this: I didn't actually come up with $P(x)$ myself (indeed, it was the crucial missing point in my own solution in-test), but basically you want a function that looks like $N(x) = x + 1$ on $0, 1, 2, \cdots, i - 2$ but then it suddenly becomes $0$ at $i - 1$ (this just seems like a nice way to have the period of $i$, right?), or $$P(x) = \begin{cases} x + 1 & \text{ if } x \in \{0, 1, 2, \cdots, i -2 \} \\ 0 & \text{ if } x = i - 1. \end{cases}$$Now it can be simplified if $P(x) = (x + 1) \cdot Q(x)$ where $Q(x) = 1$ for $0 \le x \le i - 2$ but $0$ when $x = i - 1$. Then $1 - Q(x)$ has roots at $0, 1, 2, \cdots, i - 2$ (it has the value of $0$ over and over again), so $1 - Q(x) = \alpha \cdot x(x - 1) \cdots (x - (i - 2))$ and then you can just find the correct value of $\alpha$.
13.03.2020 01:22
It may be helpful to keep in mind that every function from $\mathbb{F}_p$ to itself can be written as a polynomial.
08.02.2021 06:03
This is a very neat problem and I'll post a solution for storage. First let's consider period of $0\pmod{4}$ as $P_4$, period of $0\pmod{5}$ as $P_5$ and $0\pmod{101}$ as $P_{101}$. Here, period $\pmod{n}$ refers to smallest $k$ such that $n|P^k(0)$ and similar notation will be used throughout. So, we have $P_4\le 4, P_5\le 5, P_{101}\le 101$ and the desired $P_{2020}=lcm(P_4,P_5,P_{101})$. This is clearly maximized at $(4,5,99)$ so the desired maxima is $1980$. Now, we need to show that we can infact set up a polynomial with the claimed periods. First, we set up a rational polynomial $Q_1$ which satisfies: $Q_1(0)=1,Q_1(1)=2,\cdots Q_1(97)=98, Q_1(98)=0$. This, can be done by Lagrange interpolation. Now, in case any coefficient is of the form $\frac{p}{q}$, we replace $\frac{1}{q}$ with the inverse mod $101$ of $q$ and get an integer polynomial, now multiply this polynomial with $20^{100}$. Call this new polynomial $R_1$. $R_1$ has cycle length $99$ mod $101$ as our changes to it did not change anything mod $101$ as $20^{100}\equiv 1\pmod{101}$ and $R_1$ is always $0\pmod{20}$. Similarly, we set up $R_2(x)=404^4(x+1)$ and $R_3(x)=505^2(x+1)$. Now, observe that $R_1+R_2+R_3$ satisfies the conditions we wanted. Thus, we are done as $\boxed{N=1980}$.
07.06.2024 03:27
Love this problem sm <3 I claim that the answer is $N=1980$. Notice first that the value of $P^k(0)$ mod $2020$ must go in a cycle that has exactly length $N$ so that $2020\mid P^k(0)$ if and only if $N\mid k$. For the length of the cycle, we can consider the cycles of $P^k(0)$ mod $4$, $5$, and $101$ separately, since by Chinese Remainder Theorem, if there exists a polynomial for each of them to have certain mods when certain mods are plugged in, there must exist a polynomial that satisfies the modulo relations for all of them. We can take the "remainders" by looking at each coefficient separately and taking mods as needed. Now, note that the length of the cycle $N$ is the LCM of the lengths of the three separate cycles, where the $4$-cycle has length at most $4$, the $5$-cycle has length at most $5$, and the $101$-cycle has length at most $101$. Taking cases separately, we can find that the maximum possible LCM of three separate numbers satisfying these conditions is $1980$, which is achieved when the $4$-cycle has length $4$, the $5$-cycle has length $5$, and the $101$-cycle has length $99$. We now need to show that $1980$ is achievable. We can do this by showing that there are separate polynomials for each of the three mods such that the cycles have the desired lengths, and then CRT (Chinese Remainder Theorem) completes the rest and ensures that there exists a polynomial that satisfies the cycle lengths for all three mods. For the mod $4$ and mod $5$ cycles, note that \[x+1 \mod 4,\]and \[x+1 \mod 5,\]have the desired cycle lengths for mod $4$ and mod $5$, respectively. We now need to show that there exists a polynomial $P(x)$ such that $P^k(0)$ has a cycle of length $99$ when taken mod $101$. This can be done with Lagrange's Interpolation Formula. Note that with Lagrange's formula, it is irrelevant if the coefficients are integers when we first plug into the formula, as long as no denominators are $0$ mod $101$. This is because $101$ is prime, meaning that every number that is not a multiple of $101$ has an inverse mod $101$. By taking the fractional coefficients and turning them into integers mod $101$ using modular inverses, we maintain the modulo cycle length while making the coefficients integers. Therefore we only need to prove that there exists a polynomial $P(x)$ with rational coefficients such that $P^k(0)$ makes a cycle of length $99$ when taken mod $101$. Since we know that \[P(x)\equiv P(x+101)\mod 101,\]we can ensure a cycle of length $99$ when taken mod $101$ by simply setting $99$ cycling numbers that are all different numbers (worry about the fractional coefficients that are obtained through Lagrange later by doing what's explained above). We do this as follows \[P(0)=1,\]\[P(1)=2,\]\[P(2)=3,\]\[\dots,\]\[P(97)=98,\]\[P(98)=0,\]and use Lagrange Interpolation Formula to come up with a polynomial. As explained above, this polynomial with rational coefficients (they must be rational because we are using integers, and the way the Lagrange formula is structured will then give us rational coefficients) can be turned into one with integer coefficients with the same modulos mod $101$ as long as no denominator is a multiple of $101$. This means that we just need to prove that the Lagrange interpolated polynomial given by the formula doesn't have any term with a denominator of multiple $101$. However, note that the denominators all consist of terms in the form of multiplied terms $(x_i-x_j)$, with $i\neq j$, which means that as long as there do not exist $i$, $j$ such that $i\neq j$ and $x_i\equiv x_j\mod 101$, no denominator term will be divisible by $101$. However, note that no two of our $x_i$ terms are the same mod $101$, meaning that none of the denominators of our coefficients will be divisible by $101$, as desired. Therefore there exists a polynomial $P(x)$ such that $P^k(0)$ takes a cycle of length $1980$ when taken mod $101$. This means that our answer is indeed $N=1980$, finishing the problem.