Let $n$ be a natural number, with the prime factorisation \[ n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r} \]where $p_1, \ldots, p_r$ are distinct primes, and $e_i$ is a natural number. Define \[ rad(n) = p_1p_2 \cdots p_r \]to be the product of all distinct prime factors of $n$. Determine all polynomials $P(x)$ with rational coefficients such that there exists infinitely many naturals $n$ satisfying $P(n) = rad(n)$.
Problem
Source: Indonesian Stage 1 TST for IMO 2022, Test 2 (Number Theory), Canadian MO Qualification Repechage 2018 No 7
Tags: polynomial, number theory, prime, Product, infinite
23.12.2021 21:23
When you have zero effort in making test problems. Canada RepĂȘchage 2018/7 wrote: Let $n$ be a positive integer, with prime factorization$$n = p_1^{e_1}p_2^{e_2} \cdots p_r^{e_r}$$for distinct primes $p_1, \ldots, p_r$ and $e_i$ positive integers. Define$$rad(n) = p_1p_2\cdots p_r,$$the product of all distinct prime factors of $n$. Find all polynomials $P(x)$ with rational coefficients such that there exists infinitely many positive integers $n$ with $P(n) = rad(n)$.
17.04.2022 05:05
So easy.
26.04.2022 07:20
Since $0<rad (n) \leq n$ for all $n\in \mathbb{Z}$, $0<P(n)\leq n$ for infinitely many $n$. This leads to $\lim_{n\to \infty}\frac{P(n)}{n} \leq 1$ and hence $\deg P(x)\leq 1$. Case 1: $P(x)\equiv c \in \mathbb{Q}$, it's easy to see that $c$ is square-free is all we need. Case 2: $\deg P(x)=1$, let $P(x)=\frac{ax+b}{c}$ for some $a,b,c \in \mathbb{Z}$ and $ a,c>0$. For $b\ne 0$ Since $P(n)=rad(n)$ for infinitely many $n$, $rad(n) | b$ for infinitely many $n$. Thus, for infinitely many $n$, $an=c.rad(n)-b\leq c.|b|+|b|$, a contradiction! $P(x)$ must be of the form $\frac{ax}{c}$. For infinitely many $n$, $an=c.rad(n)$ or $c=a\frac{n}{rad(n)}$ so $a|c$ and we can consider $a$ as $1$, $P(x)=\frac{x}{c}$. For every positive integer $c=p_1^{\alpha_1}\dots p_m^{\alpha_m}$, and consider: $$S:=\{c.p: p \;\text{runs in the set of all prime number which is not}\; p_1,\dots,p_m\}$$$S$ is a infinite set and $P(n)=rad(n)$ for all $n\in S$ which means $P(x)=\frac{x}{c}, c\in \mathbb{N}$ is all polynomials we need to find.