Polynomials in Z[x]

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

Polynomials in Z[x]

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: European Mathematical Cup 2017 Problem 4

The post below has been deleted. Click to close.

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

159 posts

#1 h Dec 27, 2017, 12:25 PM • 4 Y

Y by son7, Kanep, Adventure10, Mango247

Find all polynomials $P$ with integer coefficients such that $P (0)\ne 0$ and $P^n(m)\cdot P^m(n)$ is a square of an integer for all nonnegative integers $n, m$ .

Remark: For a nonnegative integer $k$ and an integer $n$ , $P^k(n)$ is defined as follows: $P^k(n) = n$ if $k = 0$ and $P^k(n)=P(P(^{k-1}(n))$ if $k >0$ .

Proposed by Adrian Beker.

This post has been edited 1 time. Last edited by BartSimpsons, Dec 27, 2017, 12:26 PM
Reason: added source

Z K Y

The post below has been deleted. Click to close.

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

276 posts

talkon

#2 h Dec 27, 2017, 4:19 PM • 7 Y

Y by kwanglee123456, MF163, mijail, Kanep, oVlad, hakN, Adventure10

Choose a prime $p\nmid P(0)$ and plug in $(m,n)=(p,0)$ to get $p\cdot P^p(0)$ is a perfect square, so $p\mid P^p(0)$ .
Consider the orbit $0\to P(0)\to P(P(0))\to\cdots$ in $\bmod\ p$ . Clearly it is periodic, and we know that its period is not $1$ , but must divides $p$ , so it is precisely $p$ . Therefore every $p$ consecutive numbers in the orbit of $0$ forms a complete residue system $\bmod\ p$ . Now consider any $t\in\mathbb Z$ . We know that $P^k(0)\equiv t\pmod{p}$ for exactly one value of $0\leqslant k\leqslant p-1$ . Therefore,
$\{t,P(t),P(P(t)),\ldots,P^{p-1}(t)\}\equiv \{P^k(0),P^{k+1}(0),\ldots, P^{k+p-1}(0)\}\pmod{p}$ is also a CRS $\bmod\ p$

If $P(n)$ is not of the form $n+c$ , then by Schur, $\{P(n)-n\mid n\in\mathbb Z\}$ has infinitely many prime divisors, so for some prime $q\nmid P(0)$ and $n_0\in\mathbb Z$ , $q\mid P(n_0)-n_0$ , contradicting the previous paragraph.
Therefore $P(n) = n+c$ for some constant $c$ . The problem now reduces to finding all $c\in\mathbb Z$ such that
$(m+cn)(n+cm)$ is always a perfect square, and this is easy:
- If $c<0$ , when $(m,n)=(1,1-c)$ we have $(m+cn)(n+cm) = 1+(1-c)c<0$ which is obviously not a perfect square.
- If $c=0$ then it's obvious that $c$ doesn't work, and if $c=1$ it's obvious that $c$ works.
- Finally, if $c\geqslant 2$ , choose a prime $p>c^2$ and plug in $(m,n)=(p-c,1)$ to get $(m+cn)(n+cm)=p(1+pc-c^2)$ which is divisible by $p$ but not $p^2$ , and so is not a perfect square.

Therefore, the only such $P$ is $\boxed{P(n)=n+1}$

This post has been edited 1 time. Last edited by talkon, Dec 27, 2017, 4:29 PM
Reason: formatting

Z K Y

The post below has been deleted. Click to close.

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

50 posts

#3 h Dec 27, 2017, 4:23 PM • 2 Y

Y by Adventure10, Mango247

Does this problem help ?
https://artofproblemsolving.com/community/c6h6448p22328

Z K Y

The post below has been deleted. Click to close.

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

3 posts

#5 h Mar 22, 2018, 2:03 PM • 3 Y

Y by Daniil02, Adventure10, Mango247

using equivalence relations it becomes 2010 IMO #3
hint: let f(n)=P^{n}(0) and a~b iff ab is a square.

This post has been edited 1 time. Last edited by monkey322, Mar 22, 2018, 2:12 PM

Z K Y

The post below has been deleted. Click to close.

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

1576 posts

#7 h Sep 8, 2019, 3:21 PM • 1 Y

Y by Adventure10

Note that, if $m=0$ , we get $P^n(0)n$ is a perfect square, and $n=1$ gives $P(0)$ is a square. Considering the sequence $a_i=P^i(0)$ , note that $a_{i}-a_{i-1}|a_{i+1}-a_i$ since $P$ is an integer polynomial. This implies that $P(0)|a_i$ . Also, $a_{i+1}\equiv P(0)\pmod {a_i}$ , since $a_{i+1}=P(a_i)$ . Now, I will inductively show that $a_i=iP(0)$ . Clearly, the base case is true, so suppose $a_k=kP(0)$ . Note that $a_{k+1}-a_k$ must be of the form $(1+nk)P(0)$ for $n\ge 0$ . Note that as all future partial differences are divisible by this, $a_i\equiv kP(0)\pmod{(1+nk)P(0)}\forall i>k$ . So, this means that $\gcd(a_i/P(0),(1+nk))=1\forall i>k$ . Now, if $n>1$ , consider a squarefree factor, $f>1$ , of $1+nk$ , and a very large squarefree multiple of $f$ , $F$ . Of course, we want $P^F(0)F$ to be a perfect square. However, as $P(0)$ is a square, we need $F|\frac{a_F}{P(0)}$ , which is a contradiction, since $f\not\arrowvert \frac{a_F}{P(0)}$ . Therefore, we must have $n=0$ and $a_{k+1}=(k+1)P(0)$ , as desired. Now, as $P(x)-(x+P(0))$ has infinite roots, located at all $a_i$ , we must have that $P(x)=x+P(0)$ .

Denoting $P(0)$ as $c^2$ , $(n+mc^2)(m+nc^2)$ is always a perfect square. Now, if $c>1$ , choose $(m,n)$ with the following properties: $n=c^2n'$ , $m+n'$ is squarefree, $\gcd(m,n)=1$ , and $\gcd(m+n',c^4-1)=1$ . Then, this becomes $c^2(m+n')(m+n'c^4)$ . So, we must have $m+n'|m+n'c^4$ . However, $\gcd(m+n',m+n'c^4)=\gcd(m+n',n'(c^4-1))=1$ , which is a contradiction. Therefore, $c=1$ and $P(x)=x+1$ is the only solution.

This post has been edited 2 times. Last edited by william122, Sep 8, 2019, 7:52 PM

Z K Y

The post below has been deleted. Click to close.

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

1218 posts

#8 h Mar 19, 2020, 7:08 AM • 1 Y

Y by amar_04

Nice! Here's my solution (which is heavily dependent on induction): Define the sequence $(x_j)_{j \geq 0}$ with $x_0=0$ and $x_j=P(x_{j-1})$ for all $j \in \mathbb{N}$ . Then the given condition states that $nx_n$ is a perfect square for all $n \in \mathbb{N}$ . We first prove some claims which will help us strengthen our foothold over the sequence $(x_j)_{j \geq 0}$ . Throughout we'll be using the deep fact that $a-b \mid P^k(a)-P^k(b)$ for all non-negative integers $a,b,k$ .

CLAIM 1 $x_i \mid x_{iz}$ for all $i,z \in \mathbb{N}$ .

Proof of Claim 1

CLAIM 2 For all $n \in \mathbb{N}$ , we have $n \mid x_n$ .

Proof of Claim 2

CLAIM 3 Let $x_1=P(0)=A^2$ for some $A \in \mathbb{N}$ (Since $P(0)$ is a non-zero square). Then $x_i-x_{i-1}=A^2$ for all $i \in \mathbb{N}$ .

Proof of Claim 3

Return to the problem at hand. By Claim 3, we get that the equation $P(x)-x-A^2=0$ has infinitely many roots, namely $x_0,x_1,x_2 \dots$ (which are all distinct, since our claim ascertains that this sequence is an increasing sequence). Thus, we must have $P(x)=x+A^2$ . Then $P^m(x)=x+mA^2$ for all $m \geq 0$ . Suppose $A>1$ , and choose a prime $p \mid A$ . Then putting $(m,n)=(A^2,p-1)$ in the given conditions, we get that $pA^2(A^4+p-1)$ is a perfect square. But, $p \mid A$ gives that $\gcd(A^4+p-1,p)=1$ . Then $\nu_p(pA^2(A^4+p-1))=\nu_p(pA^2)=2\nu_p(A)+1$ which means that an odd power of $p$ divides $pA^2(A^4+p-1)$ , contradicting the fact that this is a square. Thus, we must have $A=1$ , and so we get the desired polynomial as $P(x)=x+1$ . This clearly works, and so we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

640 posts

#9 h Mar 19, 2020, 9:00 AM

Y by

Consider $P\ne\text{constant}.$ Since $P\equiv C$ is easy to notice.
If
$\begin{align*} n=0\to mp^m(0)&=x_m^{2}\quad\forall m\left(x_m\in\mathbb N\right)\\ \implies p\mid p^p(0)&=x_p^2\quad\forall p\in\text{(prime)}\\ \implies p\mid p^p(0)\quad\forall p\in\text{(prime)}\\ \end{align*}$ Take $p\nmid p(0)$
$\{0,p(0),\cdots,p^p(0)\}\implies\exists 0\leqslant i<j\leqslant p, p^i(0)\equiv p^j(0)[p]$ by $\text{Dirichlet's principle}$
Let $a_k=p^k(0)\implies\exists T\in\mathbb Z_p\leqslant p: a_{k+T}\equiv a_k[\pmod {p}]\forall k\ge 0$
Since $p\mid p^p(0)\implies T\mid P\implies\begin{cases} T&=1\\ T&=P\end{cases}$
$T=1\implies a_i\equiv a_{i+1}\equiv\hdots\equiv a_p\equiv a_{p+1}[p]\implies a_{p+1}=P(a_p)\equiv P(0)[\pmod {p}]\implies p\mid p(0)(\text{constant})\implies T=P$
For any $a\in\mathbb Z, P^k(0)\equiv a\pmod{p}$ for exactly one $k, 0\le k<P\implies\{a,P(a),P(P(a)),\hdots,P(a)\}\equiv\{P^k(0),P^{k+1}(0),\hdots,P^{k+p-1}(0)\}(\pmod {p}).$
This is a complete residue system $\pmod{p}.$
If $P(x)-x=Q(x)$ is a non-constant polynomial.
By $\text{Schur's theorem}$ $\{P(n)-n: n\in\mathbb Z^+\}$ has infinitely many prime.
Take $Q\mid P(0),n_0\in\mathbb Z, Q\mid P(n_0)-n_0.$
Note, $Q$ is prime this contradict to the above conditions when $q=p.$
Therefore $P(x)=x+c$ for some constant $c\in\mathbb Z.$
$(m+cn)(n+cm)$ is a square $\forall m,n\in\mathbb N.$
case 1
$c<0: m=1, n=1-c\implies(m+cn)(m+cm)=1+c-c^2<0$
case 2
$c=0: (m+cn)(n+cm)=mn$ not possible.
case 3
$c=1$ is easy to check
case 4
$\exists p\in\mathbb P : p >c^2+1$
$m=p-c,n=1\implies (m+cn)(n+cm)=p(1+pc-c^2): p\nmid p^2\implies\text{Contradiction}$
Hence, $c=1\implies P(x)\equiv x+1$

Z K Y

The post below has been deleted. Click to close.

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

694 posts

#10 h Dec 14, 2020, 4:26 PM • 4 Y

Y by RevolveWithMe101, Mango247, Mango247, Mango247

What a nice problem, took the wrong approach several times before trying "arrow" :what?:

:what?:

From the problem, we have $p \cdot P^p(0)$ is a square for any prime number $p$ , forcing $p \mid P^p(0)$ for all primes $p$ .

Take a prime number $p \nmid P(0)$ .
Claim 01. We have $\{ P(0), P^2(0), \dots, P^p(0) \}$ being complete residues modulo $p$ .
Proof. Consider
$0 \mapsto P(0) \mapsto P(P(0)) \mapsto \dots \mapsto P^p(0)$ Let $a$ be the smallest positive integer such that $P^a(0) \equiv 0 \ ( \text{mod} \ p)$ . We must have $a \mid p$ by the definition of $a$ . Thus, $a = 1$ or $a = p$ . However, we have taken $p \nmid P(0)$ , so $a = p$ . If there exists two positive integers $1 \le a < b \le p - 1$ such that $P^a(0) \equiv P^b(0) \ (\text{mod} \ p)$ . This forces $P^{p} (0) \equiv P^{p - b + a} (0) \ (\text{mod} \ p)$ , forcing $k = p - b + a < p$ to satisfy $P^k(0) \equiv 0 \ (\text{mod} \ p)$ , a contradiction. Thus, all of them must be distinct residues, resulting in a complete residue modulo $p$ .

Claim 02. This can be extended slightly to $\{ P^k(0), \dots, P^{k + p - 1}(0) \}$ is a complete residue modulo $p$ .
Proof. Since $P^p(0) \equiv 0 \ (\text{mod} \ p)$ , then since $P \in \mathbb{Z}[x]$ , then $P^{a + p}(0) = P^a (P^p (0)) \equiv P^a (0) \ (\text{mod} \ p)$ . Now, just notice that $\{ k, k + 1, \dots, k + p - 1 \} \equiv \{ 1, 2, \dots, p \}$ in $\mathbb{Z}_p$ , and we are done.

Why do we consider this?
Take any integer $t \in \mathbb{Z}$ .
Claim 03. $\{ t, P(t), \dots, P^{p - 1}(t) \}$ forms a complete residue modulo $p$ .
Proof. Since $\{ P(0), P^2(0), \dots, P^p(0) \}$ forms a complete residue modulo $p$ . Then, we can take $1 \le k \le p - 1$ such that $P^k(0) \equiv t \ (\text{mod} \ p)$ . Thus,
$\{ t, P(t), \dots, P^{p - 1}(t) \} \equiv \{ P^k(0), P^{k + 1}(0), \dots, P^{k + p - 1}(0) \} (\text{mod} \ p)$

Main Claim. $P(n) - n$ is a constant.
Proof. Now, we know that for any prime number $p \nmid P(0)$ and any integer $t \in \mathbb{Z}$ , then $p \nmid P(t) - t$ (since $\{ t, P(t) \}$ are distinct residues modulo $p$ for any $t \in \mathbb{Z}$ .)
Therefore, we conclude that if $\mathcal{P}$ is the set of primes dividing $P(n) - n$ for all $n \in \mathbb{N}$ , and $\mathcal{Q}$ is the set of primes dividing $P(0)$ , then
$\mathcal{P} \subseteq \mathcal{Q} \Rightarrow |\mathcal{P}| \le |\mathcal{Q}|$ which proves that $|\mathcal{P}|$ is finite.
However, by Schur Theorem, unless $P(n) - n$ is a constant, $|\mathcal{P}|$ is infinite, which is a contradiction.

Thus, we conclude that $P(n) = n + b$ for some integer $b$ .
We have $P^m(n) \cdot P^n(m) = (n + mb)(m + nb)$ is a square for all $n,m \in \mathbb{N}_0$ .
Take $n = 0, m = 1$ gives us $b$ being a perfect square.

Take $m = 4, n = 1$ , and we have $4b^2 + 17b + 4$ being a square. However, since
$(2b + 2)^2 = 4b^2 + 8b + 4 < 4b^2 + 17b + 4 < 4b^2 + 20b + 25 = (2b+5)^2$ We have $4b^2 + 17b + 4 = (2b + 3)^2 \rightarrow b = 1$ or $4b^2 + 17b + 4 = (2b + 4)^2 \rightarrow b = 12$ , which is not a square.
Therefore, the only solution is $\boxed{P(x) = x + 1}$ which works since
$P^m(n) \cdot P^n(m) = (m + n)^2$ is a square for all nonnegative $m,n$ .
Comments: 3 hour play and pitfalls

Z K Y

The post below has been deleted. Click to close.

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

396 posts

#11 h Sep 22, 2021, 12:01 PM

Y by

BartSimpsons wrote:

Find all polynomials $P$ with integer coefficients such that $P (0)\ne 0$ and $P^n(m)\cdot P^m(n)$ is a square of an integer for all nonnegative integers $n, m$ .

Remark: For a nonnegative integer $k$ and an integer $n$ , $P^k(n)$ is defined as follows: $P^k(n) = n$ if $k = 0$ and $P^k(n)=P(P(^{k-1}(n))$ if $k >0$ .

Proposed by Adrian Beker.

Nice Problem !!
First note that $p \mid P^{p} (0)$ , suppose there exist a $x <p$ such that $P^{x} (0) \equiv 0 mod p$ , as $p-x >0$ , choose a minimum such $x$ .

Now , $P^{x}(0) = P^{p-x}(P^{p}(0)) \equiv P^{p-x}(0) \equiv 0 mod p$ , so in general $P^{p-kx}(0) \equiv 0 modp$ .

But we can choose $k > \frac{p}{x} - 1 > 0$ , so $p-kx <x$ , a contradiction to the minimality of $x$ . , so using this we get that $P^t (0) \equiv 0 modp$ if and only if $t \equiv 0 mod p$ , for any prime $p$ , so $P^{1} (0) = P(0) = 1$ .

But now $P^{p}(0) = P^{p-1}(1)$ , but from the statement $\nu_p(P^{p}(0))$ is odd , and as $P^{p-1}(1). P(p-1)$ is perfect square this implies $P(p-1) \equiv P(-1) \equiv 0 mod p$ , but this is true for infinitely many primes $p$ , so $P(-1) = 0$ .

So we can write $P(x) = (x+1)^{r}. g(x)$ where $g(-1) \neq 0$ , suppose $g$ is not constant $P^{p}(0)= P(P^{p-1}(0)) = (P^{p-1}(0) +1)^{r} .g( P^{p-1}(0)) = p^{odd}$ , so $P^{p-1}(0) = p^{t} - 1$ , for some natural $t$ , and $g(p^{t} - 1) \equiv 0 mod p$ , but this is true for infinite $p,s$ , so $g(-1) = 0$ , a contradiction , so $g$ is indeed constant , this implies $P(x) =c(x+1)^{r}$ , but as $P(0) = c = 1$ , so $P(x) = (x+1)^{r}$ , from here we can easily prove $r = 1$ , (I will post it later as it just involved putting some values , to prove that $r = 1$ ) , Hence $P \equiv x+1$ $\blacksquare$

This post has been edited 1 time. Last edited by MatBoy-123, Sep 22, 2021, 12:14 PM

Z K Y

The post below has been deleted. Click to close.

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

658 posts

#12 h Mar 8, 2022, 11:21 AM

Y by

Answer is $P(x) \equiv x+1$ , which clearly works.

We will be showing that cycle of each negative number contains $0$ which would then be enough to imply $P(x) \equiv x+1$ .
Fix any $r \in \mathbb Z_{>0}$ , to prove $0 \in -r,f(-r),f(f(-r)),\ldots$ .
$m=0 \implies P^n(0) \cdot n \in S \qquad \qquad (1)$ Claim: $0,P(0),P(P(0)),\ldots$ is not a cycle.

Proof: Assume on the contrary the sequence is eventually periodic. Pick $k,c$ (with $c \ge 1$ ) such that $P^k(0) = x \ne 0$ and $x = P^k(0) = P^{k+c} (0) = P^{k+2c}(0) = \cdots$ Then $(1)$ gives
$x \cdot k, x \cdot (k+c), x \cdot (k+2c), \ldots \in S$ But this is an easy contradiction, say by using the fact that $S$ has density $0$ or making $\nu_p(k+yc)$ odd for prime $p \nmid x$ . $\square$

Our Claim particularly gives $P^n(0) \ne 0 ~ \forall ~ n \ge 1$ .
$m = P^r(0) \implies P^{n+r}(0) \cdot P^{P^r(0)}(n) \in S \qquad \qquad (2)$ Combining $(1),(2)$ along with our Claim gives
$Q(n) := (n+r) \cdot P^{P^r(0)} (n) \in S ~ ~ \forall ~ n \ge 0 \qquad \qquad (3)$ This forces $Q(n)$ be a square of polynomial with integer coefficients (see the proof in post #26 to Iran TST 2008/8). Then
$n+r \mid Q(n) \implies (n+r)^2 \mid Q(n) \implies n+r \implies P^{P^r (0)} (n) \implies P^{P^r(0)}(-r) =0$ So we have proven $0$ is in the cycle of $-r$ . We are ready to finish.

Claim $P$ must be linear and its leading coefficient must be $\pm 1$ .

Proof: Assume contrary. Choose a constant $\mu > 0$ such that $|P(x)| \ge |x|$ whenever $|x| \ge \mu$ . But then cycle of $-\mu$ does not contain any $0$ , which is a contradiction. $\square$

Now write $P(x) \equiv x+c$ with $c \in \mathbb Z \setminus \{0\}$ . Again, exploiting $0$ is in cycle of each negative integer we obtain $c=1$ , as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

5611 posts

#13 h Aug 10, 2023, 11:31 AM

Y by

The only solution is $\boxed{P(x) = x + 1}$ , which works. Now we prove that nothing else works.

Setting $m = 0$ , we have $P^n(0) \cdot n$ is a perfect square for nonnegative integers $n$ . Therefore $p\mid P^p(0)$ for any prime $p$ .

For any prime $p$ not dividing $P(0)$ , the period of $0,P(0), P(P(0)), \ldots,$ modulo $p$ divides $p$ , so it must be equal to $p$ . Therefore, $\{0,P(0), P(P(0)), \ldots, P^{p-1}(0) \}$ forms a complete residue set modulo $p$ . This in fact implies that $p$ cannot divide $P(n) - n$ for any integer $n$ (if $P(n)\equiv n\pmod p$ , take $P^k(0) \equiv n\pmod p$ for $k\le p-1$ ). Since $P(0)$ has finitely many prime divisors, $P(n) - n$ is constant by Schur. Let $P(n) = n+c$ . We have $(m + nc)(n + cm)$ is a perfect square. From setting $m = 0$ , we see that $c$ is a perfect square. From setting $m = 1$ and $n = 4$ , we have that $(4c + 1)(c + 4) = 4c^2 + 17c + 4$ is a perfect square. It is clearly strictly in between $(2c + 2)^2$ and $(2c + 5)^2$ , so it must be equal to $(2c+3)^2$ or $(2c+4)^2$ . This gives the only possibilities $c = 1$ and $12$ , but $12$ isn't a perfect square, so $c = 1$ , as desired.

This post has been edited 4 times. Last edited by megarnie, Aug 10, 2023, 11:37 AM

Z K Y

The post below has been deleted. Click to close.

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

194 posts

#14 h Jul 11, 2024, 3:43 PM

Y by

Substitute $m=0$ :
$P^n(0)n$ is a perfect square. Note that if $P$ is constant, then $cn$ is a perfect square, which is false when $n$ is a big prime

Now let $p$ be a prime. Because $P^p(0) \vdots p$ , the length of the cycle of $0,P(0),P^2(0),\ldots$ mod $p$ should divide $p$ , so it is $1$ or $p$ . If it is $1$ , then $p | P(0)$ , so only finitely many $p$ . For all other $p$ all residues $P(0),P^2(0),\ldots ,P^p(0)$ are different, and thus $Q(x)=P(x+1)-P(x) \not \vdots p$ for all $x$ . Because $Q$ is divisible only by finitely many primes, it should be constant, and so $P$ is linear, say $P(x)=ax+b$ . As $P(0)$ is a perfect square, $b=t^2$ . Now let $P^k(0)=t^2a_k$ . Then $a_1=1$ and $a_{k+1}=a*a_k+1$ . And $k*a_k$ is a perfect square for all $k$ . Suppose $q | a$ , where $q$ is a prime. Then $a_q \equiv 1$ (mod $q$ ), and so $v_q(qa_q)=1$ , contradicting the fact that it is perfect square. So $a$ is either one or negative one, as our values should be positive, it is $1$ .
Now the original equation tells us that $(m+nt^2)(n+mt^2)$ is always a perfect square. Take $m=p-nt^2$ , where $p$ is a large prime. Then $n-nt^4 \vdots p$ for any large $p$ , and thus $t^2=1$ . So $P(x)=x+1$ , which works because $P^n(m) \dot P^m(n)=(m+n)(m+n)=(m+n)^2$

Z K Y

The post below has been deleted. Click to close.

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

1557 posts

#15 h Jul 11, 2024, 10:03 PM

Y by

Clearly no $P$ constant works so suppose $\text{deg} P \ge 1$ , now let $P(m,n)$ the assertion.
$P(p,0)$ gives $p \mid P^p(0)$ for all $p$ primes. Now we focus on all $p>\text{max}(P(0), 1434)$ and consider the orbit $0 \to P(0) \to P(P(0)) \to \cdots$ in $\pmod p$ .
It's clear that since we found a cycle we can consider minimal $k$ for which $p \mid P^k(0)$ , but this means $k \mid p$ so since $p>P(0)$ we end up having $k=p$ and as a result $p$ is the lenght of the minimal cycle, now if there was a sub cycle in the graph we would never reach $0$ therefore $0,P(0), \cdots P^{p-1}(0)$ is a complete residue system $\pmod p$ .
Select $P^{k}(0) \equiv \ell \pmod p$ and now check that due to the cycle $\ell, P(\ell), \cdots, P^{p-1}(\ell)$ is also a complete residue system $\pmod p$ . Suppose FTSOC $P(x)-x$ isn't constant, then by Schur theorem we get that for some $p>\text{max}(P(0), 1434)$ we can find $x_0$ such that $p \mid P(x_0)-x_0$ but this means the orbit of $x_0$ has a cycle of lenght $1$ , contradicting minimality of the cycle with lenght $p$ .
Therefore $P(x)=x+c$ for all integers $x$ , now $P(p,0)$ gives $c$ is a perfect square and the problem becomes $(m+cn)(n+cm)$ perfect square for all non-negative integers $m,n$ . Trivially $c=0$ fails, and if $c<0$ then fix $m$ and set $n>-cm$ and $m+cn<0$ for large $n$ which gives that something $<0$ is a percect square, contradiction!. Therefore $c$ is a positive integer, now assume FTSOC $c \ne 1$ .
Note that by dirchlet we can get some large prime $p=m+cn$ by fixing some $m$ such that $\gcd(m,c)=1$ and setting very large $n$ , now we have $p \mid n+cm$ which means $n+cm \ge m+cn$ but clearly since $c \ge 2$ we get RHS is larger than LHS at some point, contradiction!.
Therefore $c=1$ which means $(m+n)(m+n)$ is a perfect square. This is completely true, therefore all polynomials $P \in \mathbb Z[x]$ that work are $P(x)=x+1$ thus we are done :cool:

:cool:

.

This post has been edited 2 times. Last edited by MathLuis, Jul 12, 2024, 1:26 AM

Z K Y

The post below has been deleted. Click to close.

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

1541 posts

#16 h Jul 11, 2024, 10:06 PM

Y by

Claim: $P$ has positive leading coefficient.
Proof. Suppose not, then for sufficiently large $|x|$ it follows that $|P(x)| > |x|$ , and that $x$ and $P(x)$ have negative signs.
Taking sufficiently large $n$ and $m$ of opposite parity $\pmod{2}$ gives the result. $\blacksquare$

Claim: $\nu_p(P^n(m))$ is unbounded for all primes $p$ and nonnegative $n, m$ .
Proof. FTSOC suppose that $\nu_p(P^n(0))$ is bounded above by some integer $N$ .
It then follows that if $a \equiv b \pmod{p^N}$ , that then $P(a) \equiv P(b) \pmod{p^N}$ .
Note that $P^n(0) \cdot n$ is always a perfect square. Consider the cyclic chain taken $\pmod{p^N}$ of $0, P(m), P(P(m)), \dots$ It follows that $\nu_p$ of the chain is eventually cyclic with some period $T$ .
However, this implies that $P^{kT}(0)$ and $P^{kpT}(0)$ have the same $\nu_p$ for sufficiently large $k$ , contradiction. $\blacksquare$

Claim: $P(x) = x + 1$ .
Proof. Note that $\gcd(P(x), x) \mid P(0)$ for all $x$ . Then take sufficiently large $x$ such that $\gcd(x, P(0)) = 1$ and $P(x) - x > 0$ . If any prime $p \mid P(x) - x$ , then $p \nmid x$ , so $\nu_p(P^n(x))$ is always $0$ , contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1361 posts

#17 h Nov 27, 2024, 5:28 AM

Y by

Let $a_n = P^(n)(0)$ . Plugging $m=0$ gives $na_n$ to be a perfect square for all $n \ge 0$ .

Claim: For large enough prime $p$ , we have $a_n \pmod p$ to be purely periodic with period $p$ .
Proof: Let $p > \max(0, |P(0)|)$ be a large enough prime.
Note that sequence $a_n \pmod p$ is eventually periodic, as $a_j \equiv a_i \pmod p$ for some $i, j$ (due to PHP). Thus, letting $t = j-i$ implies $a_{k+st} \equiv a_k$ for all $k \ge i$ . Let $T$ denote the period (minimum) of sequence $a_n$ .
Note that: $p a_p$ is a perfect square, which implies $p | a_p$ . Notice that: $a_{n+p} = P^{(n)}(a_p) \equiv P^{(n)}(0) \equiv a_n \pmod p$ which implies $a_n$ is purely periodic. Thus: $T|p$ which implies $T = 1$ or $T=p$ .

If $T=1$ , then $a_n \pmod p$ will be constant eventually. Notice that: $a_{np} \equiv 0 \pmod p$ which implies that, it should equal to $0$ eventually. But: $P(a_p) \equiv P(0) \pmod p$ and $P(a_p) \equiv a_p \equiv 0 \pmod p$ , thus contradiction that $p|P(0)$ .
Therefore $T=p$ .

Claim: $\deg(P) \le 1$
Proof:FTSOC, assume $\deg(P) \ge 2$ .
Thus, note that we must have: $\{ P(0), P(1), \cdots, P(p-1) \} = \{ 0, 1, \cdots, p-1 \}$ since $a_n$ is purely periodic modulo $p$ .
Let $Q(x) = P(x+1)-P(x)$ be of $\deg P -1$ polynomial with $b_n = Q(n)$ . Thus, due to Schurs theorem, infinitely many primes $q$ divide $b_n$ which implies $P(n+1) \equiv P(n) \pmod q$ . Taking $q$ to be a prime which is much larger than $p$ , it shows that $P(n+1) = P(n)$ which contradicts that $\{ P(0), P(1), \cdots, P(p-1) \} = \{ 0, 1, \cdots, p-1 \}$ .

Therefore, $P(x)=ax+b$ for some $a, b$ integers.
Consider $G(x)=P(x)-x$ . Then, by Schur's theorem, $P(n) \equiv n \pmod p$ for infinitely many primes $p$ but this contradicts that $a_n \pmod p$ has period of length $p$ , for large enough primes $p$ , unless $G$ is constant.

Thus: $P(x) = x+c$ and plugging back (followed by a NT-bash), we conclude with $c=1$ .

Z K Y

The post below has been deleted. Click to close.

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

125 posts

#18 h Mar 9, 2025, 7:10 AM

Y by

Sketch

This post has been edited 1 time. Last edited by quantam13, Mar 15, 2025, 2:26 AM
Reason: missed one detail

Z K Y

The post below has been deleted. Click to close.

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

734 posts

#19 h Apr 22, 2025, 5:52 PM

Y by

This is a similar one. Note that $P$ is non-constant since $qP^q(0)\in \mathbb{Z}^2$ and $P(0)\neq 0$ where $q|P^q(0)$ . Answer is $P(x)=x+1$ which indeed fits.
If $r|P^d(0)$ is the smallest positive integer $d$ satisfying the condition and $d<q$ , then $r|P^{d+k}(0)-P^k(0)$ and since $r|P^r(0)$ we get $d|r$ . If $r\not | P(0)$ , then $d=q$ which implies $\{P(0),P^2(0),\dots,P^{r-1}(0)P^r(0)\}$ is the complete residue system on modulo $r$ .
Let $Q(x)=P(x)-x$ . Suppose that $Q$ is non-constant. By Schur, we can pick a sufficiently large prime $p|Q(x)$ for some sufficiently large posiitve integer $x$ . Since $p\not |P^n(0)$ for $p\not | n$ we have
$1=(\frac{P^x(m)P^m(x)}{p})=(\frac{P^x(m)x}{p})\implies (\frac{x}{p})=(\frac{P^x(m)}{p})\overset{m=P^{n-x}(0)}{\implies} (\frac{x}{p})=(\frac{P^n(0)}{p})=(\frac{n}{p})$ However, this is impossible since we can choose $n$ such that $(\frac{n}{p})\neq (\frac{x}{p})$ where $p$ is sufficiently large. Thus, $Q$ is constant which implies $P(x)=x+c$ . We see that $(m+nc)(n+mc)\in \mathbb{Z}^2$ . Pick $n=q$ to get that $(\frac{c}{q})=1$ for all sufficiently large primes. This yields $c$ is a perfect square. Let $c=t^2$ . If $n=t^2$ , then $(m+t^4)(t^2+mt^2)\in \mathbb{Z}^2$ or $(m+t^4)(m+1)\in \mathbb{Z}^2$ . If $t^4\neq 1$ , we pick a sufficiently large prime $p^2|m+1-p$ where $p\not | m+t^4$ but we observe that this is impossible. Thus, $t^2=1$ or $P(x)=x+1$ as desired. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a