Maths Olympiad Prep

Library / /88 of 104

Algebra Difficulty 6.7 National Olympiad Prove it Bulgaria

Problem:
Let nn be a positive integer. Find all positive integers mm, for which there exists a polynomial f(x)=a0+a1x++anxnZ[x], an0f(x) = a_{0} + a_{1} x + \cdots + a_{n} x^{n} \in \mathbb{Z}[x],\ a_{n} \neq 0, such that gcd(a0,a1,,an,m)=1\gcd(a_{0}, a_{1}, \ldots, a_{n}, m) = 1 and f(k)f(k) divides mm for any integer kk.

Solution

Solution:
1. We shall use the following well-known facts.

LEMMA 1. For any integer xx and any positive integer tt the number t!t! divides (x+1)(x+2)(x+t)(x+1)(x+2) \ldots (x+t).

Proof. The statement is obvious for x{0,1,2,,t}x \in \{0, -1, -2, \ldots, -t\}. We have to prove it for x>0x > 0. Let pp be a prime divisor of tt. Then the power of pp in the prime factorization of t!t! is [tp]+[tp2]+\left[\frac{t}{p}\right] + \left[\frac{t}{p^{2}}\right] + \cdots. This power does not exceed the power of pp in the prime factorization of (x+1)(x+2)(x+t)=(x+t)!x!(x+1)(x+2) \ldots (x+t) = \frac{(x+t)!}{x!} since the last power equals [x+tp]+[x+tp2]+[xp][xp2]=[x+tp][xp]+[x+tp2][xp2]\left[\frac{x+t}{p}\right] + \left[\frac{x+t}{p^{2}}\right] + \cdots - \left[\frac{x}{p}\right] - \left[\frac{x}{p^{2}}\right] - \cdots = \left[\frac{x+t}{p}\right] - \left[\frac{x}{p}\right] + \left[\frac{x+t}{p^{2}}\right] - \left[\frac{x}{p^{2}}\right] - \cdots and [a+b][a]+[a+b] \geq [a] + **.

LEMMA 2. For g(x)R[x]g(x) \in \mathbb{R}[x] with degg=n\deg g = n one has that g(Z)Zg(\mathbb{Z}) \subset \mathbb{Z} if and only if g(x)=i=0nbi(xi)g(x) = \sum_{i=0}^{n} b_{i} \binom{x}{i}, where b0,b1,,bnZb_{0}, b_{1}, \ldots, b_{n} \in \mathbb{Z}.

Proof. Obviously, if gg has the above form, then g(Z)Zg(\mathbb{Z}) \subset \mathbb{Z}.
Conversely, let g(Z)Zg(\mathbb{Z}) \subset \mathbb{Z}. Set g(i)=αiZ, i=0,1,,ng(i) = \alpha_{i} \in \mathbb{Z},\ i = 0, 1, \ldots, n and apply the Lagrange interpolation formula with knots 0,1,,n0, 1, \ldots, n. Then
g(x)=i=1nx(x1)(xi+1)(xi1)(xn)αii(i1)(i(i1))(i(i+1))(in)=i=1n(1)n+iαi(n+1)(xn+1)xi \begin{aligned} g(x) & = \sum_{i=1}^{n} \frac{x(x-1) \ldots (x-i+1)(x-i-1) \ldots (x-n) \alpha_{i}}{i(i-1) \ldots (i-(i-1))(i-(i+1)) \ldots (i-n)} \\ & = \sum_{i=1}^{n} (-1)^{n+i} \frac{\alpha_{i} (n+1) \binom{x}{n+1}}{x-i} \end{aligned}
It remains to use that any polynomial
(n+1)(xn+1)xi=x(x1)(xi+1)(xi+1)(xn)n! \frac{(n+1) \binom{x}{n+1}}{x-i} = \frac{x(x-1) \ldots (x-i+1)(x-i+1) \ldots (x-n)}{n!}
can be written in the given form (compare the respective coefficients). The lemma is proved.

Let now mm be a divisor of n!n! and consider the polynomial f(x)=(x+1)(x+2)(x+n)f(x) = (x+1)(x+2) \ldots (x+n). It follows by Lemma 1 that mm divides f(k)f(k) for any kZk \in \mathbb{Z}. Moreover, ff is a monic polynomial (i.e., the leading coefficient of ff equals 11) and hence gcd(a0,a1,,an,m)=1\gcd(a_{0}, a_{1}, \ldots, a_{n}, m) = 1. So all divisors of n!n! are solutions of the problem.

Assume that mm does not divide n!n! and mm is a solution of the problem. Set r=m(m,n!)r = \frac{m}{(m, n!)}. It is clear that r>1r > 1 is an integer and (r,n!)=1(r, n!) = 1. Let f(x)=a0+a1x++anxn, an0f(x) = a_{0} + a_{1} x + \cdots + a_{n} x^{n},\ a_{n} \neq 0, be a polynomial with the desired properties. Then for g(x)=f(x)rg(x) = \frac{f(x)}{r} one has that g(Z)Zg(\mathbb{Z}) \subset \mathbb{Z} and, by Lemma 2, g(x)=i=0nbi(xi)g(x) = \sum_{i=0}^{n} b_{i} \binom{x}{i}, where b0,b1,,bnZb_{0}, b_{1}, \ldots, b_{n} \in \mathbb{Z}.

Hence f(x)=i=0nmbi(xi)f(x) = \sum_{i=0}^{n} m b_{i} \binom{x}{i} and using that (r,i!)=1(r, i!) = 1 for i=0,1,,ni = 0, 1, \ldots, n, we get that rr divides all the coefficients of ff, a contradiction.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.