Beautiful polynomial number theory

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Beautiful polynomial number theory

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Baltic Way 2004 Problem 8, "extended" and "generalized"

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#1 h Nov 20, 2004, 1:03 PM • 2 Y

Y by Adventure10, Mango247

Let $f\left(x\right)$ be a non-constant polynomial with integer coefficients, and let $u$ be an arbitrary positive integer. Prove that there is an integer $n$ such that $f\left(n\right)$ has at least $u$ distinct prime factors and $f\left(n\right) \neq 0$ .

This post has been edited 1 time. Last edited by darij grinberg, Apr 3, 2007, 2:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5526 posts

harazi

#2 h Nov 21, 2004, 9:29 AM • 2 Y

Y by Adventure10, Mango247

After seeing the solution you gave, I thought that it is the hardest problem of number theory ever given! In fact, we can give a very short solution, using lemma 1 (Schur theorem, I think in the literature). Indeed, consider $p_1,...,p_k$ different large prime numbers such that there exist $n_1,...,n_k$ for which $p_i| f(n_i)$ and $f(n_i)$ is non-zero (this follows from lemma 1). Choose a number $n$ congruent to $n_i$ mod $p_i$ . There are an infinite number of such numbers and thus in at least one of these numbers the polynomial does not vanish. Even more, the value of the polynomial in each such number is a multiple of $p_1,...p_k$ . Finish!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#3 h Nov 21, 2004, 9:42 AM • 2 Y

Y by Adventure10, Mango247

My solution:

I will reduce the problem to the following lemma:

Lemma 1. The set of all primes p such that there is an integer x satisfying p | f(x) is infinite.

This Lemma will be proved later. Now I will solve the problem with the help of this lemma.

Since the set of all primes p such that there is an integer x satisfying p | f(x) is infinite, we can take u primes $p_1$ , $p_2$ , ..., $p_u$ out of this set, and there are some integers $x_1$ , $x_2$ , ..., $x_u$ such that $p_i \mid f\left(x_i\right)$ for every i with $1\leq i\leq u$ . Now, if $y_i$ is an integer such that $y_i \equiv x_i \; \mathrm{mod} \; p_i$ , then $p_i \mid y_i-x_i$ , while $y_i-x_i \mid f\left(y_i\right)-f\left(x_i\right)$ (this is just because f(x) is a polynomial with integer coefficients), so that $p_i \mid f\left(y_i\right)-f\left(x_i\right)$ , and since $p_i \mid f\left(x_i\right)$ , this yields $p_i \mid f\left(y_i\right)$ . Now, since the numbers $p_1$ , $p_2$ , ..., $p_u$ are prime and thus pairwisely coprime, the Chinese Remainder Theorem shows that there are infinitely many integers Y such that $Y \equiv x_i \; \mathrm{mod} \; p_i$ for every i with $1\leq i\leq u$ . Among these infinitely many integers Y, there is at least one such that $f\left(Y\right) \neq 0$ (else, the polynomial f(x) would have infinitely many zeros, what is not possible for a non-constant polynomial). Denote this number Y satisfying $f\left(Y\right) \neq 0$ by n.

Hence, for these number n, we have $f\left(n\right) \neq 0$ and $n \equiv x_i \; \mathrm{mod} \; p_i$ for every i such that $1\leq i\leq u$ . But the latter congruence yields $p_i \mid f\left(n\right)$ for every i with $1\leq i\leq u$ . In other words, the number f(n) is divisible by all the u primes $p_1$ , $p_2$ , ..., $p_u$ , and hence, this number f(n) has at least u prime factors. This solves the problem.

Now let's prove Lemma 1. Assume the contrary, i. e. assume that the set of all primes p such that there is an integer x satisfying p | f(x) is finite. Let this set be $\left\{p_1;\;p_2;\;...;\;p_s\right\}$ , where s is a positive integer. Then, for every integer x, the value f(x) has the form $f\left(x\right)= \pm p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ , where $e_1$ , $e_2$ , ..., $e_s$ are nonnegative integers. Hence, of course, $\left|f\left(x\right)\right| = p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ .

On the other hand, let our polynomial f(x) be $f\left(x\right) = a_m x^m + a_{m-1} x^{m-1} + ... + a_1 x + a_0$ , with integer coefficients $a_m$ , $a_{m-1}$ , ..., $a_1$ , $a_0$ . Hereby, of course, m is the degree of our polynomial. Since a polynomial of degree m cannot achieve one and the same value more than m times (without being a constant polynomial), our polynomial f(x) achieves every of its values at most m times. Clearly, this yields that the function $\left|f\left(x\right)\right|$ achieves every of its values at most 2m times (in fact, for each value v, we have f(x) = v for at most m different values of x and we have f(x) = -v for at most m different values of x, so that we can have $\left|f\left(x\right)\right| = v$ for at most 2m different values of x).

Let B be an arbitrary positive integer. Then, for every positive integer x with $x\leq 2mB$ , the triangle inequality shows that

$\left|f\left(x\right)\right| = \left|a_m x^m + a_{m-1} x^{m-1} + ... + a_1 x + a_0\right|$
$\leq \left|a_m x^m \right| + \left|a_{m-1} x^{m-1}\right| + ... + \left|a_1 x \right| + \left|a_0\right|$
$= \left|a_m \right| x^m + \left|a_{m-1}\right| x^{m-1} + ... + \left|a_1\right| x + \left|a_0\right|$ (since x is positive)
$\leq \left|a_m \right| \cdot \left(2mB\right)^m + \left|a_{m-1}\right| \cdot \left(2mB\right)^{m-1} + ... + \left|a_1\right| \cdot 2mB + \left|a_0\right|$ (since $x\leq 2mB$ ).

In other words, we have $\left|f\left(x\right)\right| \leq t\left(B\right)$ , where

$t\left(B\right) = \left|a_m \right| \cdot \left(2mB\right)^m + \left|a_{m-1}\right| \cdot \left(2mB\right)^{m-1} + ... + \left|a_1\right| \cdot 2mB + \left|a_0\right|$ .

Of course, t(B) is a polynomial of B, and actually a polynomial which is always nonnegative for B > 0. This will become important later.

Now, consider the interval [1; 2mB]. To each of the 2mB integers in this interval, there corresponds a value of the function $\left|f\left(x\right)\right|$ at this integer. Since the function $\left|f\left(x\right)\right|$ achieves every of its values at most 2m times, at least $\frac{2mB}{2m}=B$ of these values are different. But every such value is $\leq t\left(B\right)$ on the one hand, and on the other hand, every such value can be written in the form $\left|f\left(x\right)\right| = p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ . Hence, there are at least B different numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$ . Let r be such a number $r=p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ , with $r\leq t\left(B\right)$ . Then, if we would have $e_1 > \log_2 t\left(B\right)$ , we would get

$r=p_1^{e_1} p_2^{e_2} ... p_s^{e_s} \geq p_1^{e_1} > p_1^{\log_2 t\left(B\right)}$
$\geq 2^{\log_2 t\left(B\right)}$ (since $p_1\geq 2$ , as any prime is $\geq 2$ )
$=t\left(B\right)$ ,

what contradicts $r\leq t\left(B\right)$ . Thus, $e_1 \leq \log_2 t\left(B\right)$ . Similarly, $e_2 \leq \log_2 t\left(B\right)$ , ..., $e_s \leq \log_2 t\left(B\right)$ . Therefore, all the integers $e_1$ , $e_2$ , ..., $e_s$ lie in the interval $\left[0;\;\log_2 t\left(B\right)\right]$ . Consequently, the number of all possible numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$ doesn't exceed $\left(\log_2 t\left(B\right) +1\right)^s$ .

But remember that we have found at least B different numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$ . Hence, $B \leq \left(\log_2 t\left(B\right) +1\right)^s$ .

And this holds for every positive integer B ! But it is not hard to show that, for every polynomial t(B) and for every integer s, there is a positive integer $B_1$ such that $B_1 > \left(\log_2 t\left(B_1\right) +1\right)^s$ . In fact, this is equivalent to $\sqrt[s]{B_1} > \log_2 t\left(B_1\right) +1$ , what, using the substitution $C_1=\sqrt[s]{B_1}$ , takes the form $C_1 > \log_2 t\left(C_1^s\right) +1$ ; since $\log_2 t\left(C_1^s\right) + 1 = \log_2 \left(2t\left(C_1^s\right)\right)$ , this is equivalent to $C_1 > \log_2 \left(2t\left(C_1^s\right)\right)$ . And this is clear, since $2t\left(C_1^s\right)$ is a polynomial of $C_1$ (since t is a polynomial), and a linear function always overtakes the logarithm of a polynomial. Hence, we have found a positive integer $B_1$ such that $B_1 > \left(\log_2 t\left(B_1\right) +1\right)^s$ , contradicting our previous result $B \leq \left(\log_2 t\left(B\right) +1\right)^s$ for every positive integer B; hence, we have a contradiction, and Lemma 1 is proven.

My apologies for the style. It's just the first time I solve and write down the solution of a slightly nontrivial number theory problem.

This post has been edited 1 time. Last edited by darij grinberg, Nov 4, 2005, 12:16 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5526 posts

harazi

#4 h Nov 21, 2004, 10:06 AM • 2 Y

Y by Adventure10, Mango247

Indeed, I did not realize that the longest proof was for the lemma 1

and this is because this lemma has a super short solution. I will give some hints: assuming that $f(0)$ is non-wero, show that we can reduce to the case $f(1)=1$ and then consider the sequence $f(1+n!)$ . But I particularly like your proof of this lemma. Although long, it has nice ideas.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4464 posts

Myth

#5 h Nov 21, 2004, 10:17 AM • 2 Y

Y by Adventure10, Mango247

Oh yes, Darij's long solution misleads about difficulty of this problem. Well known lemma 1 has short nice proof.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#6 h Nov 21, 2004, 4:13 PM • 2 Y

Y by Adventure10, Mango247

You probably know that well-known and known to me are different things. And I must say I couldn't see anything from Harazi's hint. Anyway, the proposed solutions have a very nice and simple proof, so I guess it should be something of the same kind...

Darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7849 posts

#7 h Nov 21, 2004, 4:21 PM • 3 Y

Y by Takeya.O, Adventure10, Mango247

Here's what Harazi's hint is supposed to mean: if you have $f(1)=1$ , then assume that the elements of the set $\{f(n)|n\in\mathbb Z\}$ have only finitely many prime divisors, $p_1,p_2,\ldots,p_k$ . Now take $n>\max (p_i)$ , and show that $p_i\not |f(1+n!)$ , thus getting a contradiction. It's in fact pretty similar to the idea used to show the infinitude of primes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#8 h Dec 12, 2004, 1:40 PM • 3 Y

Y by Takeya.O, Adventure10, Mango247

Thanks, Grobber, for this. Now it remains only one question (to you, Harazi and everyone): Why can I assume f(1) = 1 ? And, please, give a detailed explanation, not just a hint.

Thanks!

Darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7849 posts

#9 h Dec 12, 2004, 2:32 PM • 3 Y

Y by Takeya.O, Adventure10, Mango247

I remember Harazi's other hint was to use a polynomial transformation. I don't really know what he was talking about, so we'll just have to wait and see.

Meanwhile..

Here's how I see this thing: take a number $t$ for which $f(t)\ne 0$ . Let $p_1,p_2,\ldots,p_k$ be the primes dividing the elements of $f(\mathbb Z)$ (just as before). Now take $n$ so large that the exponent of $p_i$ in $n!$ is larger than the exponent of $p_i$ in $f(t)$ . Now the exponent of $p_i$ in $f(n!+t)=n!\cdot N+f(t)$ is bounded by the exponent of $p_i$ in $t$ , and since we can take arbitrarily large such $n$ 's, we get a contradiction (the polynomial can only take a finite number of values in infinitely many points of the form $n!+t$ , where $t$ is the $t$ fixed above and $n$ increases indefinitely).

This is somewhat of a change of plan, but I think it gives a better idea of what's going on: even if $f(1)\ne 1$ , it can't be that important (as long as $f(1)\ne 0$ ).

I expect Harazi to have a different answer, since he didn't mention $f(1)\ne 0$ , so maybe he has a nice way around that.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#10 h Dec 12, 2004, 4:55 PM • 3 Y

Y by Takeya.O, Adventure10, Mango247

Grobber, thanks for the explanation!

grobber wrote:

This is somewhat of a change of plan, but I think it gives a better idea of what's going on: even if $f(1)\ne 1$ , it can't be that important (as long as $f(1)\ne 0$ ).

Well, guarranteeing $f\left(1\right)\neq 0$ is not hard: The polynomial f can have only finitely many roots, hence it can have only finitely many integer roots, and consequently, there is a greatest integer root v of this polynomial; now, after replacing f(x) by f(x + v), it is clear that f(0) = 0 and $f\left(1\right) \neq 0$ .

Darij

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

92 posts

Zorro

#11 h Dec 12, 2004, 9:49 PM • 2 Y

Y by Adventure10, Mango247

I've posted a solution of this problem some time ago, why it isn't here??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1198 posts

Megus

#12 h Dec 12, 2004, 9:54 PM • 2 Y

Y by Adventure10, Mango247

Zorro wrote:

I've posted a solution of this problem some time ago, why it isn't here??

Probably due to the problems with database which occured last week

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a