Co-prime polynomials

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

Co-prime polynomials

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Indian TST Day 1 Problem 1

The post below has been deleted. Click to close.

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

209 posts

#1 h Jul 11, 2014, 8:28 AM • 8 Y

Y by anantmudgal09, TheOneYouWant, doxuanlong15052000, megarnie, Master_of_Aops, Adventure10, CRT_07, and 1 other user

Find all polynomials $f(x)$ with integer coefficients such that $f(n)$ and $f(2^{n})$ are co-prime for all natural numbers $n$ .

Z K Y

The post below has been deleted. Click to close.

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

836 posts

#2 h Jul 13, 2014, 7:42 AM • 13 Y

Y by debjit1999, mbrc, quangminhltv99, biomathematics, doxuanlong15052000, Math-Ninja, Adventure10, Mango247, thepassionatepotato, CRT_07, and 3 other users

We will show $f\equiv 1$ and $f\equiv -1$ work.
Lemma :
$f(2^k)=1$ or $-1$ each $k$ .
Proof :
Suppose not. Then take a prime $p$ dividing $f(2^k)$ for some $k$ . Now see that $p\mid f(s_r)$ where $s_r=2^k+rp$ for any integer $r$ . Now, consider $f(2^{s_r})$ . We try to find an $r$ such that $p\mid 2^{s_r}-2^k$ . Then we would have $p\mid 2^{s_r}-2^k\mid f(2^{s_r})-f(2^k)\implies p\mid f(2^{s_r})$ hence $\gcd(f(s_r),f(2^{s_r}))>1$ which serves our contradiction. It remains to find such an $r$ . If $p=2$ then it is trivial. Suppose $p>2$ . We need to find $r$ such that
$2^{s_r}\equiv 2^k\pmod p\implies 2^{2^k-k+rp}\equiv 1\pmod p$ but since $p$ is odd hence $\{2^n\mod p\}$ is periodic. Hence such an $r$ exists. Hence we are done.
Now we have that for each $n,\; f(2^n)$ is $1$ or $-1$ . Suppose there exist $k,\ell$ with $f(2^k)=1,f(2^\ell)=-1$ . But then
$2^k-2^\ell \mid 2$ which is a contradiction for sufficiently large $k,\ell$ . Then for big $k$ we have $f(2^k)=1$ or $-1$ throughout. Then $f(x)=1$ has infinitely many solutions, and similarly for $f(x)=-1$ and hence $f$ is identically equal to $1$ or $-1$ . Hence our claim follows.
In the end, our solutions are :
$\boxed{f\equiv 1,f\equiv -1}$

Z K Y

The post below has been deleted. Click to close.

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

339 posts

#3 h Oct 7, 2014, 1:25 PM • 3 Y

Y by Adventure10, Mango247, CRT_07

Alternative finish (I believe this is how XmL did it too): The lemma in the post above shows that at least one of the polynomials $f(x)-1$ and $f(x)+1$ has infinitely many roots, so one of them must be identically equal to zero, so $f(x)$ is either always 1 or always -1.

Z K Y

The post below has been deleted. Click to close.

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

1979 posts

#4 h Oct 16, 2015, 9:45 AM • 2 Y

Y by Adventure10, CRT_07

I am posting in a hurry so if there is anything wrong please inform me. Thank you.

Here:
Let us observe that $f \equiv 1$ and $f\equiv -1$ are solutions and no other constant polynomial works.
Now assume that
$degP \ge 1$ .
Now let $k_0$ be a natural number such that $\forall k \ge k_0$ , $f(k)$ has absolute value greater than $1$ .

Let $p$ be a prime such that $p \mid f(2^k)$ and let $p>2$ (Such a prime $p$ exists by taking $k$ to be larger than $v_2(f(0))$ or in other words $k$ to be sufficiently large.)
.
Then set $n= 2^k +p(l(p-1)+k-2^k)$ for sufficiently large $l,k \in \mathbb{N}$ .
Now, $f(n) \equiv f(2^k) \equiv 0 \bmod p$
and $f(2^n) \equiv f(2^k) \equiv 0 \bmod p$ because of our choice of $n$ .
This clearly leads to a contradiction to our hypothesis.

Z K Y

The post below has been deleted. Click to close.

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

239 posts

#6 h Mar 6, 2016, 1:34 AM • 3 Y

Y by Adventure10, Mango247, CRT_07

Assume that $f$ is nonconstant . Consider $(f(2^i))_{i \geq 1}$ . For sufficiently large $k$ , by our assumption that $f$ is nonconstant , we may choose a prime divisor $p$ so that $p|f(2^k)$ and $p \geq 2$ . Choose $n \equiv 2^k \text{( mod p )}$ and $n \equiv k \text{( mod (p-1) )}$ .

Then , $f(2^n) \equiv f(n) \equiv 0 \text{( mod p )}$ . This is a contradiction , so $f$ is constant and it is easy to conclude that $f \equiv +1$ or $f \equiv -1$ .

Z K Y

The post below has been deleted. Click to close.

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

643 posts

#7 h Apr 12, 2018, 1:42 PM • 4 Y

Y by paragdey01, Adventure10, Mango247, CRT_07

Indian TST Day 1 Problem 1 wrote:

Find all polynomials $f(x)$ with integer coefficients such that $f(n)$ and $f(2^{n})$ are co-prime for all natural numbers $n$ .

Solution

This post has been edited 2 times. Last edited by ayan.nmath, Apr 12, 2018, 2:24 PM

Z K Y

The post below has been deleted. Click to close.

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

452 posts

aops29

#8 h Jan 9, 2020, 7:41 PM • 4 Y

Y by Alireza_Amiri, Adventure10, Mango247, CRT_07

Solution

Z K Y

The post below has been deleted. Click to close.

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

82 posts

#9 h May 14, 2020, 10:47 AM • 4 Y

Y by Mango247, Mango247, Mango247, CRT_07

Very nice solution @aops29 but in this part:

aops29 wrote:

Take $l$ to be an integer such that $l\equiv m - 2^m \pmod{p}$ .

I think it should be $\pmod{p-1}$

Z K Y

The post below has been deleted. Click to close.

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

TFIRSTMGMEDALIST

162 posts

TFIRSTMGMEDALIST

#10 h Mar 24, 2022, 11:46 PM • 1 Y

Y by CRT_07

how did he prove it

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

87 posts

#11 h Mar 25, 2022, 12:44 AM • 1 Y

Y by CRT_07

Suppose there exists $p$ odd prime with $p\mid f(2^{n_0})$ . Then, using the chinese remainder theorem, take
$n \equiv n_0 \pmod{p-1}$ $n\equiv 2^{n_0} \pmod p.$ Since if $a\equiv b \pmod n$ , $f(a)\equiv f(b) \pmod n$ ,
$f(n) \equiv f(2^{n_0}) \equiv f(2^n) \pmod p,$ a contradiction.
Hence, for each $n,$ $\pm f(2^n)$ is a power of two. Then, if it is even for some $n, \ f(0)$ is even, so $2\mid \gcd (f(2),f(4))$ .
Therefore, $f(2^n) = \pm 1$ for all $n$ , so either $f+1$ or $f-1$ has infinitely many zeros. This implies that $f\equiv 1$ or $f\equiv -1$ , which both work.

Z K Y

The post below has been deleted. Click to close.

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

TFIRSTMGMEDALIST

162 posts

TFIRSTMGMEDALIST

#12 h Mar 25, 2022, 7:21 AM • 1 Y

Y by CRT_07

Olympikus wrote:

Suppose there exists $p$ odd prime with $p\mid f(2^{n_0})$ . Then, using the chinese remainder theorem, take
$n \equiv n_0 \pmod{p-1}$ $n\equiv 2^{n_0} \pmod p.$ Since if $a\equiv b \pmod n$ , $f(a)\equiv f(b) \pmod n$ ,
$f(n) \equiv f(2^{n_0}) \equiv f(2^n) \pmod p,$ a contradiction.
Hence, for each $n,$ $\pm f(2^n)$ is a power of two. Then, if it is even for some $n, \ f(0)$ is even, so $2\mid \gcd (f(2),f(4))$ .
Therefore, $f(2^n) = \pm 1$ for all $n$ , so either $f+1$ or $f-1$ has infinitely many zeros. This implies that $f\equiv 1$ or $f\equiv -1$ , which both work.

In chinese remainder u can choose whatever you want ? Ur choice for $n_0$ and $2^n_0$

Z K Y

The post below has been deleted. Click to close.

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

TFIRSTMGMEDALIST

162 posts

TFIRSTMGMEDALIST

#13 h Mar 26, 2022, 4:23 PM • 1 Y

Y by CRT_07

TFIRSTMGMEDALIST wrote:

how did he prove it

Help please

Z K Y

The post below has been deleted. Click to close.

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

1481 posts

CT17

#14 h Mar 26, 2022, 5:01 PM • 1 Y

Y by CRT_07

If $f$ is constant, then the only solutions are clearly $f\equiv -1$ and $f\equiv 1$ .

Assume $f$ is nonconstant. Let $p$ be a prime dividing $f(2^k)$ for some positive integer $k$ . Then $f(n)$ and $f(2^n)$ are both divisible by $p$ for any $n\equiv kp - 2^k(p-1)\pmod{p^2 - p}$ so we have a contradiction, as desired.

Z K Y

The post below has been deleted. Click to close.

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

250 posts

L13832

#15 h Jan 9, 2025, 6:55 PM • 1 Y

Y by CRT_07

Standard
solution

This post has been edited 1 time. Last edited by L13832, Jan 10, 2025, 3:28 AM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

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

195 posts

onyqz

#16 h Jan 12, 2025, 2:30 PM • 1 Y

Y by CRT_07

solution
motivation

Z K Y

The post below has been deleted. Click to close.

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

172 posts

#17 h Jan 18, 2025, 9:39 AM • 1 Y

Y by CRT_07

let $p$ be a prime such that $p \mid f(2^k)$ .Then we have that $p \mid f(2^k+ cp)$ , since $2^k \equiv2^k + cp$ $(mod p)$
We can choose $c$ such that $2^{2^k + cp} \equiv 2^ k$ , $c \equiv k - 2^k$ $(mod p-1)$ Then we have $p \mid f(2^{2^k + cp} ) - f(2^k) \implies f \mid f(2^{2^k + cp} )$ . A contradiction.
Which implies $f(2^k) = \pm 1$ for every $k$ which is clearly not possible.
So $f$ is a constant polynomial and the solutions are $\boxed{f\equiv \pm 1}$ .

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

377 posts

alexanderhamilton124

#19 h Jan 18, 2025, 11:23 AM • 2 Y

Y by TensorGuy666, CRT_07

If it isn't $1$ or $-1$ , consider a prime $p$ such that $p \mid f(2^x)$ , for some $x$ . Then, take $n \equiv 2^x \mod{p}$ , $n \equiv k \mod{p - 1}$ , which exists by CRT, a contradiction.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a