a really nice polynomial problem

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

a really nice polynomial problem

G H J

Reveal topic tags

Integer Polynomial

L

G H BBookmark kLocked kLocked NReply

Source: Iranian TST 2018, third exam day 1, problem 3

The post below has been deleted. Click to close.

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

24 posts

#1 h Apr 18, 2018, 1:28 PM • 2 Y

Y by Adventure10, Mango247

$n>1$ and distinct positive integers $a_1,a_2,\ldots,a_{n+1}$ are given. Does there exist a polynomial $p(x)\in\Bbb{Z}[x]$ of degree $\le n$ that satisfies the following conditions?
a. $\forall_{1\le i < j\le n+1}: \gcd(p(a_i),p(a_j))>1$
b. $\forall_{1\le i < j < k\le n+1}: \gcd(p(a_i),p(a_j),p(a_k))=1$

Proposed by Mojtaba Zare

This post has been edited 8 times. Last edited by Etemadi, Apr 21, 2018, 4:35 PM

Z K Y

The post below has been deleted. Click to close.

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

544 posts

lminsl

#2 h May 23, 2018, 12:34 AM • 5 Y

Y by medhasrisairavi, meowchan, hakN, Adventure10, Mango247

Bumping this

Z K Y

The post below has been deleted. Click to close.

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

615 posts

#3 h May 23, 2018, 2:30 PM • 2 Y

Y by Adventure10, Mango247

For $p(x)\in\Bbb{Q}[x]$ it is easy, the main problem is to be more accurate fo get integer coefficients.

Z K Y

The post below has been deleted. Click to close.

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

97 posts

#4 h Jun 16, 2018, 2:57 AM • 4 Y

Y by pavel kozlov, Mathematicsislovely, Adventure10, Mango247

pavel kozlov wrote:

For $p(x)\in\Bbb{Q}[x]$ it is easy, the main problem is to be more accurate fo get integer coefficients.

Let $M=\left|\prod_{i\neq j}(a_i-a_j)\right|$ and $x_1,x_2,\cdots,x_{n+1}\in\mathbb{N}^*$ , the Lagrange interpolation formula tells us that a polynomial $p\in\mathbb{Z}[x]$ with degree $\le n$ exists, such that $p(a_i)=x_i M+1,i=1,2,\cdots,n+1$ .
Then by the CRT it's easy to get proper $x_1,x_2,\cdots,x_{n+1}\in\mathbb{N}^*$ satisfying the condition.

Z K Y

The post below has been deleted. Click to close.

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

343 posts

#5 h Jul 15, 2018, 9:26 AM • 4 Y

Y by pavel kozlov, sholly, Adventure10, Mango247

after arriving at $p(a_i)=x_i M+1,i=1,2,\cdots,n+1$ as above, one can use Dirichlet Theorem to find infinitely many primes $\equiv 1 \pmod M$ , and let $p(a_i)$ be the product of some primes.

This post has been edited 1 time. Last edited by Rickyminer, Jul 15, 2018, 9:27 AM

Z K Y

The post below has been deleted. Click to close.

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

578 posts

#6 h Jun 29, 2019, 7:20 PM • 2 Y

Y by Adventure10, Mango247

Darn this solution has basically already been found above

, but I'll write it up.

The answer is $\boxed{yes}.$

Define $M = \left | \prod_{i \neq j} (a_i - a_j) \right |.$ For each $1 \le i < j \le n+1$ , select a prime $p_{ij}$ which is congruent to $1$ (mod $M$ ). Select these primes in such a way so that all $\binom{n+1}{2}$ of them are distinct, which is doable by Dirichlet's Theorem. By convention, we will let $p_{ji}$ for $j > i$ denote $p_{ij}.$

Now, consider the unique polynomial $P \in \mathbb{R} [x]$ of degree $\le n$ such that:

$P(a_i) = \prod_{j \neq i} p_{ij},$
for each $1 \le i \le n+1.$ It's easily checked that this polynomial satisfies the conditions of the problem, so all that remains is to check that it has integral coefficients. Indeed, observe that $P(a_i)$ is an integer congruent to $1$ (mod $M$ ) for each $1 \le i \le n.$ Therefore, the following claim solves the problem.

Claim. For any polynomial $Q$ of degree $\le n$ so that $Q(a_i)$ is an integer divisible by $M$ for each $1 \le i \le n+1$ , $Q \in \mathbb{Z}[x].$

Proof. By Lagrange's Interpolation Formula, we know that $Q$ is given by:

$\sum_{i = 1}^{n+1} \frac{Q(a_i)}{\prod_{j \neq i} (a_i - a_j)} \cdot \prod_{j \neq i} (x-a_j).$
It suffices only to observe that $\frac{Q(a_i)}{\prod_{j \neq i} (a_i-a_j)} \in \mathbb{Z}$ since $\prod_{j \neq i} (a_i - a_j) | M | Q(a_i).$

$\blacksquare$

Now, applying the claim on $P - 1$ , we've shown that $P -1 \in \mathbb{Z}[x] \Rightarrow P \in \mathbb{Z}[x],$ so we're done.

$\square$

Z K Y

The post below has been deleted. Click to close.

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

558 posts

#9 h Aug 27, 2020, 10:25 AM • 1 Y

Y by AlastorMoody

A bit too straightforward for a TST #3.
Nevertheless , a cool problem

Solution

Z K Y

The post below has been deleted. Click to close.

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

1301 posts

#10 h Mar 8, 2022, 9:03 AM

Y by

Let $N$ be the product of primes up to $\max\{a_1,\cdots, a_m\}$ . We can get $N^k-1$ to be divisible by primes $p_{i,j}$ for $1\le i<j\le n+1$

We construct $P(x)=N^k(x^2+tx)+c$ . We want $P(x)\equiv (x-a_i)(x-a_j)$ in $\mathbb{Z}_{p_{ij}}$ so we need $t\equiv a_j+a_i (\bmod\; p_{i,j})$ since $N^k\equiv 1(\bmod\; p_{i,j})$ . We select $c$ such that $c\equiv 1(\bmod\; N)$ and $c\equiv a_ia_j(\bmod\; p_{i,j})$ . We can construct $t,c$ via the Chinese Remainder Theorem since $\gcd(N, p_{i,j})=1$ .

I claim $P$ works. Note $p_{i,j}|P(a_i)$ and $p_{i,j}|P(a_j)$ . Assume for contradiction $p$ divides $P(a_i), P(a_j)$ and $P(a_k)$ . We know $P(x)\equiv 1(\bmod\; p)$ for all primes less than $\max\{a_1,\cdots,a_{n+1}\}$ so $a_1,\cdots,a_{n+1}$ must be injective mod $p$ . Then in $\mathbb{Z}_p[x]$ , $(x-a_i)(x-a_j)(x-a_k)|P(x)$ . Since $\deg P=2$ it follows that $P$ is the zero polynomial. However, $\gcd(N^k,c)=1$ so p cannot divide both simultaneously, contradiction!

This post has been edited 1 time. Last edited by CANBANKAN, Mar 8, 2022, 6:42 PM

Z K Y

The post below has been deleted. Click to close.

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

18 posts

#11 h Apr 4, 2025, 10:26 AM

Y by

Nice; Let $M = \left | \prod_{i \neq j} (a_i - a_j) \right |.$ . And $b_i = p(a_i)$ . By Lagrange interpolation formula we have there exist a polynomial with rational coefficients that fits on $a_i$ with $b_i$ . We just need to ensure its coefficients are in integers; I'll choose $b_i$ such that $M|b_i-b_j$ for all $1 \leq i, j \leq n+1$ and it's easy to see the coefficients of $p$ will be integers. For this just induct on $n$ . we will prove for all positive integer $M$ ; there exist an arbitrary large sequence(not infinite) like $b_i$ such that that $b_i \equiv 1 (mod M)$ and $\gcd(b_i,b_j)>1$ and $\gcd(b_i,b_j,b_k)=1$ . For adding new element to the sequence like $b_{n+1}$ just choose arbitrary large( larger than any previous elements) distinct primes like $p_1,p_2,...,p_n$ such that $p_i \equiv 1 (mod M)$ . Just set $c_i = b_i \times p_i$ for $1\leq i \leq n$ and $c_{n+1} = p_1...p_n$ . You can see this sequence of $c_i$ satisfies the conditions...

This post has been edited 1 time. Last edited by amirhsz, Apr 4, 2025, 10:28 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a