Maths Olympiad Prep

Library / /39 of 87

Algebra Difficulty 6.2 National Olympiad Prove it Serbia

Problem:

Let AA be an infinite subset of the set of natural numbers. Determine all natural numbers nn such that for every aAa \in A it holds that
an+an1++a1+1an!+a(n1)!++a1!+1 a^{n}+a^{n-1}+\ldots+a^{1}+1 \mid a^{n!}+a^{(n-1)!}+\ldots+a^{1!}+1

Solutions — 2

Solution 1

Denote P(x)=xn+xn1++1P(x)=x^{n}+x^{n-1}+\cdots+1 and Q(x)=xn!++x1!+1Q(x)=x^{n!}+\cdots+x^{1!}+1; let Q(x)=C(x)P(x)+R(x)Q(x)=C(x) P(x)+R(x), where CC and RR are polynomials with integer coefficients and degR<degP\operatorname{deg} R<\operatorname{deg} P. By the condition of the problem P(a)Q(a)P(a) \mid Q(a), and hence P(a)R(a)P(a) \mid R(a), for infinitely many integers aa. Since for sufficiently large aa we have R(a)<P(a)|R(a)|<|P(a)|, it must be that R(a)=0R(a)=0; therefore, R(x)R(x) has infinitely many zeros, so R(x)0R(x) \equiv 0 and P(x)Q(x)P(x) \mid Q(x).

Lemma. Let k0,k1,,knN0k_{0}, k_{1}, \ldots, k_{n} \in \mathbb{N}_{0}. The polynomial P(x)=xn+xn1++1P(x)=x^{n}+x^{n-1}+\cdots+1 divides Q(x)=xkn++xk1+xk0Q(x)=x^{k_{n}}+\cdots+x^{k_{1}}+x^{k_{0}} if and only if {k0,k1,,kn}\left\{k_{0}, k_{1}, \ldots, k_{n}\right\} is a complete system of residues modulo n+1n+1.

Proof. Let rir_{i} be the remainder when kik_{i} is divided by n+1n+1. Since xn+11x^{n+1}-1 divides xkixrix^{k_{i}}-x^{r_{i}} for all ii, it follows that P(x)=xn+11x1P(x)=\frac{x^{n+1}-1}{x-1} divides Q(x)Q1(x)Q(x)-Q_{1}(x), where Q1(x)=xr0+xr1++xrnQ_{1}(x)=x^{r_{0}}+x^{r_{1}}+\cdots+x^{r_{n}} and moreover degQ1n\operatorname{deg} Q_{1} \leqslant n. If P(x)Q(x)P(x) \mid Q(x), then P(x)Q1(x)P(x) \mid Q_{1}(x), i.e. Q1(x)=cP(x)Q_{1}(x)=c P(x) for some constant cc, and this holds if and only if c=1c=1 and {r0,r1,,rn}={0,1,,n}\left\{r_{0}, r_{1}, \ldots, r_{n}\right\}=\{0,1, \ldots, n\}.

From the lemma it follows that the required numbers nn are those for which {0,1!,,n!}\{0,1!, \ldots, n!\} is a complete system of residues modulo n+1n+1.

If n>3n>3 and n+1n+1 is a composite number, then n!0(modn+1)n!\equiv 0(\bmod n+1), so the condition is not satisfied. If n+1=p>3n+1=p>3 is prime, by Wilson's theorem (p1)!1(modp)(p-1)!\equiv-1(\bmod p), from which (p2)!1=1!(modp)(p-2)!\equiv 1=1!(\bmod p), and again the condition is not satisfied. The remaining cases are n3n \leqslant 3; direct verification shows that n=1n=1 and n=2n=2 satisfy the conditions.

Solution 2

Second solution. We will prove a stronger statement: if A=an++a+1A=a^{n}+\cdots+a+1 divides akn++ak1+ak0a^{k_{n}}+\cdots+a^{k_{1}}+a^{k_{0}} for some aN\{1}a \in \mathbb{N} \backslash\{1\}, then {k0,k1,,kn}\left\{k_{0}, k_{1}, \ldots, k_{n}\right\} is a complete system of residues modulo n+1n+1.

Let AB=akn++ak1+ak0A \mid B=a^{k_{n}}+\cdots+a^{k_{1}}+a^{k_{0}}. Denote by ri,jr_{i, j} the remainder when ki+jk_{i}+j is divided by n+1n+1, and consider the numbers Bj=arn,j++ar1,j+ar0,jB_{j}=a^{r_{n, j}}+\cdots+a^{r_{1, j}}+a^{r_{0, j}}. Then BjajB(modA)B_{j} \equiv a^{j} B(\bmod A), from which it follows that ABjA \mid B_{j} for j=0,1,,nj=0,1, \ldots, n. On the other hand, B0+B1++Bn=jarn,j++jar1,j+jar0,j=(n+1)AB_{0}+B_{1}+\cdots+B_{n}=\sum_{j} a^{r_{n, j}}+\cdots+\sum_{j} a^{r_{1, j}}+\sum_{j} a^{r_{0, j}}=(n+1) A, so since Bj>0B_{j}>0, it must be that Bj=AB_{j}=A for all jj. From the inequality A<2anA<2 a^{n} we conclude that, for every jj, at most one of the remainders ri,jr_{i, j} is equal to nn. But if kikinj(modn+1)k_{i} \equiv k_{i^{\prime}} \equiv n-j(\bmod n+1), then ri,j=ri,j=nr_{i, j}=r_{i^{\prime}, j}=n, which is impossible. Therefore, k0,k1,,knk_{0}, k_{1}, \ldots, k_{n} are pairwise distinct modulo n+1n+1, which was to be proved.

From the lemma it follows that the required numbers nn are those for which {0,1!,,n!}\{0,1!, \ldots, n!\} is a complete system of residues modulo n+1n+1.
If n>3n>3 and n+1n+1 is a composite number, then n!0(modn+1)n!\equiv 0(\bmod n+1), so the condition is not satisfied. If n+1=p>3n+1=p>3 is prime, by Wilson's theorem (p1)!1(modp)(p-1)!\equiv-1(\bmod p), from which (p2)!1=1!(modp)(p-2)!\equiv 1=1!(\bmod p), and again the condition is not satisfied. The remaining cases are n3n \leqslant 3; direct verification shows that n=1n=1 and n=2n=2 satisfy the conditions.

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 translated into English from sr; metadata (topic, difficulty) added by this project.