Polynomial mapping set of divisors to set of divisors

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

Polynomial mapping set of divisors to set of divisors

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: CMO 2023 P4

The post below has been deleted. Click to close.

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

6610 posts

#1 h Mar 11, 2023, 1:36 AM • 1 Y

Y by Rounak_iitr

Let $f(x)$ be a non-constant polynomial with integer coefficients such that $f(1) \neq 1$ . For a positive integer $n$ , define $\text{divs}(n)$ to be the set of positive divisors of $n$ .

A positive integer $m$ is $f$ -cool if there exists a positive integer $n$ for which $f[\text{divs}(m)]=\text{divs}(n).$ Prove that for any such $f$ , there are finitely many $f$ -cool integers.

(The notation $f[S]$ for some set $S$ denotes the set $\{f(s):s \in S\}$ .)

Z K Y

The post below has been deleted. Click to close.

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

2726 posts

#2 h Mar 11, 2023, 1:44 AM • 1 Y

Y by Ru83n05

Take prime $p$ dividing $f(1)$ and $m >> N$ where $f$ is strictly increasing past $N$ . $f$ of largest factors of $m$ must correspond to largest factors of $n$ , and size argument (relying on the fact that $l^n$ cannot equal $p$ ever for n > 1) wins

This post has been edited 2 times. Last edited by jj_ca888, Mar 11, 2023, 1:49 AM

Z K Y

The post below has been deleted. Click to close.

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

14 posts

js104

#3 h Mar 11, 2023, 2:35 AM • 1 Y

Y by A64298347

alternatively: there are finitely many $a$ where $f(a)=1$ (at most degree of $f$ ), so one must divide infinitely many $m$ , so then $f(m/a)\mid f(m) \implies f(x)\mid f(ax)$ has infinitely many solutions (again for large enough $m$ where it's strictly increasing and $f(m)>f(n)$ for all $0<n<m$ ). do division algorithm, $f(ax)=qf(x)+g(x)$ where deg g < deg f, so $f(x)\mid g(x)$ infinitely many times. after some point $|f(x)| > |g(x)|$ so $g(x)=0$ for infinitely many $x$ and has to be the zero polynomial; $f(ax)=qf(x) \implies f(x)$ is a monomial $cx^d$ , but this is clearly bad (no integer sols to $f(a)=1$ )

Z K Y

The post below has been deleted. Click to close.

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

1184 posts

L567

#4 h Mar 11, 2023, 2:47 AM • 4 Y

Y by VicKmath7, mathscrazy, Ru83n05, jmiao

Note that eventually the function will be strictly increasing, therefore we must have $f(m) = n$ and $f(\frac{m}{p}) = \frac{n}{q}$ , where $p$ and $q$ are the smallest prime divisors of $m$ and $n$ respectively. These two can be rewritten to $f(\frac{m}{p}) = \frac{f(m)}{q}$ But note that $f(1) \neq 1$ be among the divisors of $n$ and hence divide $n$ , so the value of $q$ is actually bounded. As a consequence, due to the above equation, $p$ is bounded too, therefore there exist infinitely many values of $m$ which have the same value of $p$ , and for all of these we have that $f(k) \mid f(kp)$ for $k = \frac{m}{p}$ . Since this is true for infinitely many big integers, it forces that $f(kp) = Q(k)f(k)$ , implying $f$ can only be a monomial. But this is clearly impossible since nothing goes to one here except one itself.

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#5 h Mar 11, 2023, 2:58 PM • 1 Y

Y by centslordm

Some people might get a -1 by not considering $f(1)<0$ (in particular $f(1)=-1$ )?

We will prove that there are finitely many cool pairs of positive integers $(m,n)$ such that $f(\text{divs}(m))=\text{divs}(n)$ . Throwing out the finitely many pairs with $m=1$ or $n=1$ , The key is to consider the least prime divisor of $m$ and $n$ . If $f(1)\leq 0$ we cannot have any $f$ -cool pairs because $f(\text{divs}(m))$ will always have a nonpositive number but $\text{divs}(n)$ cannot. Thus $f(1)>1$ , so since $f(1)$ must divide $n$ the least prime divisor of $n$ in any cool pair $(m,n)$ is bounded. Furthermore, since $1 \in \text{divs}(n)$ , one of the divisors $d$ of $m$ must have $f(d)=1$ . Since there are finitely many solutions in the positive integers to this, and $1$ is not one of them, the least prime divisor of any $m$ in a cool pair $(m,n)$ is also bounded (in particular, by the largest prime divisor over all these solutions).

For $m$ large enough, the largest value in $f(\text{divs}(m))$ should be $f(m)$ , and the second-largest should be $f(m/p)$ , where $p$ is the least prime divisor of $m$ . Thus for a good pair $(m,n)$ we should have $(m,n)$ , we should have $f(m)=n$ and $f(m/p)=n/q$ where $q$ is the least prime divisor of $n$ . Since we proved $p$ and $q$ were bounded, if there are infinitely many cool pairs $(m,n)$ , by pigeonhole there should be some pair of primes $(p,q)$ that occurs infinitely often, i.e. there are infinitely many $m$ with
$f\left(\frac{m}{p}\right)=\frac{f(m)}{q}.$ Thus this must be a polynomial equality. But if there is an $x^k$ term in $f$ with nonzero coefficient, it gets multiplied by $p^{-k}$ on the LHS and $q^{-1}$ on the RHS, implying that $k$ must be unique, so $f(x)=cx^d$ is the only polynomial we must consider, where $c>1$ . However, such polynomials will not have any integers solutions to $f(x)=1$ by taking modulo $c$ , which is necessary for any pair $(m,n)$ to be cool, so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

254 posts

#6 h Mar 11, 2023, 5:06 PM

Y by

Sad problem. Assume contradiction and notice that there are finitely many $a_i$ such that $f(a_i)=1$ and suppose $\mathbb{P}$ is the prime-set of these numbers $a_i$ . Let $1 < d_a < d_{a-1} < \cdots < d_1 <m$ and $1 < e_a < e_{a-1} < \cdots < e_1 <n$ be the divisors of $m$ and $n$ respectively where $m$ is cool and $n$ is its cool conjugate. WLOG assume that the leading coefficient of $f$ is positive and we can find $N$ such that for all $m \geq N$ , $f(m)=n$ and $f(d_i)=e_i$ where $1 \leq i \leq a$ . This means, $f(d_a) \mid f(m)=f(d_ad_1)$ Notice that $d_a$ is bounded as $d_a \in \mathbb{P}$ , thus for some prime $d_a = p_i \in \mathbb{P}$ , the divisibility is true infinitely many times. Now we can force $f(d_1x) = f(x)g(x)$ for some polynomial $g$ for all $x$ (say by the euclidean algorithm), thus $f(x) = cx^d$ but then $f$ is never mapped to $1$ which is a contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

256 posts

#7 h Apr 9, 2023, 10:54 PM • 2 Y

Y by jmiao, khina

The original (harder) version of this problem had the condition that $f(x)\neq x$ (as polynomials) instead of $f(1)\neq 1$ , with the goal to prove that there are finitely many $f-$ cool composite integers.

Z K Y

The post below has been deleted. Click to close.

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

7 posts

#8 h Aug 24, 2023, 1:47 PM

Y by

Bacteria wrote:

The original (harder) version of this problem had the condition that $f(x)\neq x$ (as polynomials) instead of $f(1)\neq 1$ , with the goal to prove that there are finitely many $f-$ cool composite integers.

May I ask which problem you referred to above or in which competition?

Z K Y

The post below has been deleted. Click to close.

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

8857 posts

#9 h Dec 21, 2023, 9:43 PM

Y by

Suppose WLOG that the leading coefficient of $f$ is positive. Let $M$ be the largest local maximum of $f$ , and let $N$ be the largest number such that $f(N) = M$ . Assume that there exist infinitely many $f$ -cool integers $m$ ; then there exists such a $m$ with $m > N$ .

Let $p_1$ be the smallest prime factor of $m$ and $q_1$ the smallest factor of $n$ . It follows that $f(n) = m > M$ and $f\left(\frac n{p_1}\right) = \frac m{p_1}$ . But setting $c$ to be the leading coefficient of $f$ , by taking $n$ sufficiently large, we can force $(p_1^d - 1) f\left(\frac n{p_1}\right) < f(n) < (p_1^d + 1) f\left(\frac n{p_1}\right).$ In particular, this implies that $q_1 = p_1^d$ , which is absurd for $d \geq 2$ .

Thus $d=1$ ; but because there exists an integer $k$ with $f(k) = 1$ , it follows the leading coefficient of $f$ is $\pm 1$ . Having $f(1) < 0$ , on the other hand, is clearly impossible, so this yields an immediate contradiction.

Z K Y

The post below has been deleted. Click to close.

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

266 posts

L13832

#10 h Aug 8, 2024, 7:30 PM

Y by

Impossible to write the solution correctly

FTSOC assume there there are infinitely many $f-$ cool integers.
Claim I: $f(m)=n$
Proof: It is easy to see that $f$ has positive coefficients. So $f(m)$ and $n$ are the largest value in the sets $f[d(m)]$ and $d(n)$ respectively , so $f(m)=n$ .

Also note that $1$ is the smallest $d(m)$ , so let $f(k)=1$ for some $k$ . Also $k\neq 1$ according to the problem.
Claim II: $f(k)\mid f(ak)$ , for $f(k)=1$
Proof: $\exists k$ such that $\displaystyle f\biggl(\frac{m}{k}\biggr) \in f[d(m)]=d(f(m))\implies f\biggl(\frac{m}{k}\biggr)\bigg|f(m)\implies f(k)\mid f(ak)$ which has infinite solutions.

Let $\text{deg}(f)=d$ and $f(ak)=g\cdot f(k)+h(k) \implies f(k)\mid h(k)$ , but $\text{deg}(h)<\text{deg}(f)$ hence we have a contradiction, so $h$ is $0$ . We get $f(ak)=g \cdot f(k) \implies f(k)=ck^d$ . But if $c=1$ then $f(1)=1$ which is a contradiction so there are finitely $f-$ cool integers. $\blacksquare$

This post has been edited 1 time. Last edited by L13832, Sep 9, 2024, 4:18 PM

Z K Y

The post below has been deleted. Click to close.

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

SomeonesPenguin

128 posts

SomeonesPenguin

#11 h Aug 8, 2024, 11:52 PM • 1 Y

Y by zzSpartan

Notice that since $f$ is eventually positive, there exists $N$ such that for every $u \ge N$ and $u > v$ we have $f(u) > f(v)$ . Hence if $m$ is big enough we get that $f(m)$ is the biggest so $f(m) = n$ . We also exclude prime $m$ because we can only have finitely many of these. Now let $p$ be the smallest prime dividing $m$ and $q$ be the smallest prime dividing $n$ . Since $m$ isn't prime, we have that $\frac{m}{p} \ge p$ so it can be sufficiently large. So we get that $f\left(\frac{m}{p}\right)$ is the second biggest and so $f\left(\frac{m}{p}\right)=\frac{n}{q}$ . So we finally get: $f\left(\frac{m}{p}\right)=\frac{f(m)}{q}$
Also notice that $f(1)$ must be greater than $1$ hence we have that $f(1)\ge q$ since $f(1)\in \text{divs}(n)$ . So we get that $f\left(\frac{m}{p}\right)\ge \frac{f(m)}{f(1)}$
Therefore $p \le f(1)$ (for sufficiently large $m$ ). And so $p$ is bounded meaning that there are infinitely many $f$ -cool integers with least prime factor $p$ . Hence we must have $f(x)=P(x)f\left(\frac{x}{p}\right)$ . Hence $\text{deg}P = 0$ and looking at some non-zero coefficient of $x^{k}$ we get $P(x) = 1$ which is clearly a contradiction.

This post has been edited 1 time. Last edited by SomeonesPenguin, Aug 9, 2024, 11:08 AM

Z K Y

The post below has been deleted. Click to close.

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

612 posts

#12 h Apr 26, 2025, 4:34 AM

Y by

Obviously note that the leading coefficient of $f$ must be positive. Clearly, there are finitely many values of $f$ such that $f(a) = 1.$ Hence, there has to exist a value $a$ so that there are infinitely many $k$ such that $ak$ is $f$ -cool. Take an arbitrarily large value of $k$ such that $f$ is increasing over this interval. Hence, $f(ak)$ is the largest value in the set in the left hand side, which implies $m = f(ak).$ Thus, $f(k)\mid f(ak)$ for infinitely many values $k$ . Let $d = \operatorname{deg} f$ . Suppose $f(ax) = a^d f(x) + g(x),$ where $g \in \mathbb Z[x]$ by division algorithm. Clearly, $\operatorname{deg}g < \operatorname{deg}f.$ However, we also have $f(x)\mid g(x)$ for infinitely many values of $x.$ This implies that $g \equiv 0.$ Thus, $f(x) = ax^d,$ which is impossible to achieve $f(x) = 1.$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a