Define a period modulo $n$ as $p$ if $p$ is the smallest positive integer such that $P^p(0) \equiv 0 \ (\text{mod} \ n)$. Call the set of possible periods modulo $n$ as $P_n$. Claim 01. Given a number $N$. Let $\nu_{p_i}(N) = \alpha_i$, for every prime $p_i$ dividing $N$. Then, we have \[ P_N = \text{lcm} \left( \ P_{p_1^{\alpha_1}}, P_{p_2^{\alpha_2}}, \dots, P_{p_n^{\alpha_n}} \right) \]Proof Break apart to primes by the definition of $P_N$ and it follows immediately. Thus, the conditions become $m \in P_n$ and $(m,n) = 1$ Claim 02. The set of residues $\{ 0, P(0), \dots, P^{p - 1}(0) \}$ must all be distinct. Proof. Suppose otherwise, there exists a cycle. Obviously this cycle doesn't pass through $0$ or otherwise this contradicts the minimality of $p$, and therefore the cycle will never pass $0$, eventually, and hence $P^k (0) \equiv 0 \ (\text{mod} \ 2020)$ has no solution in $k$. Claim 03. $P_p = \{ 1 , 2 , \dots, p \}$. Proof. Notice that the construction \[ P(x) = x -2k + (2k + 2)(x - 2k)^{p - 1} \]fits the bill for having period of $k + 1$. This forces $P(x) = x - 2k + (2k + 2) = x + 2$ for $x \not= 2k$, and $P(x) = x - 2k$ when $x = 2k$. fits the construction for each of $k = 2, 3, \dots, p- 1$. For $k = 1$, take $P(x) = x$. A similar construction works for showing $\{1 , 2 , \dots, p \} \subseteq P_{p^e}$. Use: \[ P(x) = x - 2k + (2k + 2)(x -2k)^{p^{e - 1}(p - 1)} \] Claim 04. If $m \in P_n$, then $\forall q | m$, we have $q \in P_n$. Proof. Notice that since we have $m \in P_n$, let $m = aq$, for $a \in \mathbb{N}$, we have \[ 0 \to P^a (0) \to P^{2a} (0) \to \dots \to P^{qa} (0) = 0 \]which is a cycle of length $q$. By Claim 02, all of the members are distinct modulo $n$ as well. So this fits the original condition. Claim 05. If $P(a) \equiv b \cdot p^x \ (\text{mod} \ p^{x + 1})$, then $P(a') \equiv b \cdot p^x \ (\text{mod} \ p^{x + 1})$, if $a \equiv a' \ (\text{mod} \ p)$. Proof. Since $P \in \mathbb{Z}[x]$, then we have \[ p^{x + 1} | p^x (a' - a) | P(a') - P(a) \] Claim 06. If $q$ is a prime such that $q > p_k$, then $q \notin P_{p_k^{\alpha_k}}$ Proof. Suppose otherwise, that there exists a prime number $q$ such that $q > p_k$ and $q \in P_{p_k^{\alpha_k}}$. Then we have $0 \to P(0) \to P^2(0) \to \dots P^{q - 1}(0)$ are are all distinct modulo $p_k^{\alpha_k}$. Notice that this gives us \[ 0 \to P(0) \to \dots \to P^q (0) = 0\]a cycle modulo $p_k$ as well. Since $q > p_k$, then we have some of the residues are the same in the cycle. If that cycle doesn't contain $0$, this is impossible as it won't reach $P^q(0)$. Otherwise, then let $k$ be the length of its cycle. We then have $k | q$. This forces $k = 1$. Now, induct on $\alpha_k$. We claim that if the cycle is constant modulo $p_k^a$. It is also constant modulo $p_k^{a + 1}$. Proceed as follow: Since each element of the cycle is $0 \ (\text{mod} \ p_k^a)$, we can write everything as $p_k^a \cdot t_i$ in modulo $p_k^{a + 1}$ where there are $p_k$ residues possible for $t_i$. Since $q > p_k$, there are residues that cycles. Notice that by Claim 05, these residues must cycle through $0$, let the period be $k$. Hence, $k | q$, forces $k = 1$ as well. Therefore, we can eventually lift the power of the prime and get that in modulo $p_k^{\alpha_k}$, they are constant which is a contradiction. Hence, by all the claim together, we have \[ P_N = \ \text{LCM}_{i \in \mathbb{N}} \{ 1, 2, \dots, p_i \}^{\alpha_i} \] Now, we want to find all $n$ such that there exists $m$ such that we can find $(m,n) = 1$ and \[ m = \text{LCM}_{i \in \mathbb{N}} \{ 1, 2, \dots, p_i \}^{\alpha_i} \]This can only be done if $\boxed{\text{ there exists a prime number } P < \max \{ p_1, p_2, \dots, p_k \} \text{which doesn't divide } n. }$ The construction is easy; using Chinese Remainder Theorem on: \[ P(x) \equiv x \ (\text{mod} \ p_i^{\alpha_i}) \]Everywhere except for $p_i = \max \{ p_1, p_2, \dots, p_k \}$. Where in that case, use \[ P(x) \equiv (x - 2P) + (2P + 2)(x - 2P)^{p_i^{\alpha_i - 1} \cdot (P - 1)} \ (\text{mod} \ p_i^{\alpha_i} ) \]

I will just provide the construction, as the first part is proven above rather simply Consider a prime number $p$ not dividing $n$, such that there exist at least one prime number greater than $p$ dividing $n$ (assuming it such $p$ exists) Consider a prime $q | n, g > p$. It is well known that every function from $\mathbb{Z}_q$ to itself can be represented as a polynomial in $\mathbb{Z}_q$. Using the following construction, there is a polynomial $Q$ with coefficients mod $q$ such that $Q(i)=i+1$ for $0\leq i\leq p-2$, $Q(p-1)=0$, $Q(i)=i$ for $p\leq i \leq q-1$ all mod $q$. Considering all prime numbers $q>p$ that divide $n$, and using CRT on the coefficients, we can conclude there is a polynomial (mod product of all those primes, but that is not important) $Q$ that satisfies the above condition for every such prime simultaneously.

Take $N = \prod_{q|n, q<p}q^{v_q(n)}$ and $M = \prod_{q|n, q>p}q$ and consider the polynomial $P(x)= N^{\phi(M)}(Q(x))^{(\phi(M)+1)^k}$, where $k$ is any integer sufficiently large, we can just choose it later. We have $P(x)\equiv N^{\phi(M)}(Q(x))^{(\phi(M)+1)^k} \equiv (Q(x))^{(\phi(M)+1)^k} \equiv Q(x) (\text{mod } q|M)$, using Fermat's little theorem. This also implies $P^n(x)\equiv Q^n(x) (\text{mod }q|M)$. From here it follows that obviously $n|P^k(0)$ first time when $k=p$, and $gcd(n,p)=1$, so we have our $m$ and $P$ (exponent $k$ in the expression of $P$ is just to make $v_q(P)$ larger than $v_p(n)$).

I dont know about all n but all odd n satisfy this for each odd n choose m=2 then we have the first condition complete.then choose P(x)=(n-1)X^q + 1. for Q an positive integer we see that P(0)=1 which is not divisible by n and then we see that P^m(x)=P^2(x)=P(1)=n-1+1=n which is divisible by n. Hence all odd n satisfy this

For each integer $n>1$, let $f(n)$ be the smallest prime that is not divisble by $n$. We call $n$ bad if all prime factors of $n$ are smaller than $f(n)$, and call it good otherwise. We claim that $n$ satisfies the condition of the problem if and only if $n$ is good. Suppose $n$ is bad. Suppose on the contrary that there exists $m$ and $P(x)$ satisfying those conditions. Let $a_0=0$ and $P^{i}(0)=a_i$. We consider all numbers mod $n$, moreover since the sequence is periodic with period $m$, we may consider all the indices mod $m$. Now let $p$ be a prime dividing $n$. CLAIM 1. Let $d$ be a fixed integer, then the number $$v_p(a_{i+d}-a_i)$$is a fixed value, which does not depend on $i$. Proof. Indeed, we have $$v_p(a_{i+d+1}-a_{i+1})=v_p(P(a_{i+d})-P(a_i))\geq v_p(a_{i+d}-a_i)$$Therefore, since the sequence is periodic we must have that the quantity is a fixed value. $\blacksquare$ CLAIM 2. Let $v_p(n)=k$, then for all $i\leq k$ we have $p^{i}|a_j$ for each $1\leq j\leq m$ Proof. We proceed by induction on $i$, the case $i=0$ is trivial. Suppose $p^{i-1}|a_j$ for all $j$, let $d$ be the smallest integer such that $v_p(a_d)\geq j$. By pigenohle principle there exists some $1\leq x<y\leq p$ such that $v_p(a_{y}-a_{x})\geq j$. Therefore from CLAIM 1 we have $d<y-x<p$. Meanwhile since $v_p(a_m)=v_p(n)=k>j$, we have $d|m$. However, since $n$ is bad, we have $(n,d)>1$, hence $(m,d)>1$ as well, contradiction. $\blacksquare$ CLAIM 2 implies that $n|a_j$ for all $j$, which is obviously a contradiction. For the construction, we firstly show the following lemma. Lemma. Let $n$ be an integer, and $a_0,a_1,...,a_k$ be integers such that $$(a_i-a_j,n)=1$$for each $0\leq i<j\leq k$, then for any integers $b_0,b_1,...,b_k$ there exists a polynomial $P$ with integer coefficients such that $f(a_i)\equiv f(b_i)\pmod n$ for all $0\leq i\leq k$ Proof. We proceed by induction on $k$. The base case $k=0$ is trivial. Suppose all smaller cases holds, then by inductive hypothesis there exists a polynomial $g$ such that $$g(a_i)=(b_i-b_0)(a_i-a_0)^{-1}\pmod n$$We complete the inductive step by taking $f(x)=(x-a_0)g(x)+b_0$ $\blacksquare$ Now let $f(n)=p$ and $n=qr$, such that all prime factors of $q$ are greater than $p$ and all prime factors of $r$ are smaller than $p$. By the lemma there exists a polynomial $P_1$ such that \begin{align*} P_1(0)&\equiv q\pmod r\\ P_1(q)&\equiv 2q\pmod r\\ &...\\ P_1((p-2)q)&\equiv (p-1)q\pmod r\\ P_1((p-1)q)&\equiv 0\pmod r \end{align*}Now we are done by taking $P=pP_1$

Enumerate the list of primes $p$ as $\{p_i\}_{i=1}^{\infty}$ with $p_1<p_2<\cdots$. We claim that such a $P$ does not exist for $n$ iff the set $Q$ of all primes $p\mid n$ is $\{p_1,\dots , p_k\}$ for some integer $k$. We first show that if the set $Q$ of primes $p\mid n$ is $\{p_1,\dots , p_k\}$ for some integer $k$, then no $P$ exists. Suppose otherwise. Let $n=p_1^{e_1}\cdots p_k^{e_k}$. Claim: The value of $m$ such that $P(0),\dots,P^{m-1}(0)$ are all nonzero modulo $p_i^{e_i}$ and $P^m(0)$ is $1$ for each $i$. Solution: The following stupid argument works. First, note $P$ repetitively applied to $0$ has order $1$ modulo $p_i$; otherwise, some $1<r<p_i$ would have to divide the order of $P$ modulo $n$, but $r$ must have some prime divisor in $\{p_1,\dots,p_k\}$, so the order of $P$ repetitively applied to $0$ modulo $n$ would not be relatively prime to $n$. Similarly, $P$ must have order $1$ modulo $p_i^2$ for the same reason, as $P^k(0)$ can only take values $1\pmod{p}$. Iterating shows that $P$ has order $1$ modulo $p_i^{e_i}$ as desired. $\fbox{}$ This implies that $P(0)\equiv 0\pmod{n}$, so we have a contradiction because the problem mandated that $m>1$. We now apply the sophisticated technique of ``Haha Lagrange Interpolation go brr.'' First, if $2\nmid n$, take $P(x)=(n-1)x+1$, which clearly works. Now, let the prime divisors of $n$ be $2=p_1<\cdots<p_i<p_{i+1}<\cdots<p_k$ where there is a prime $q$ between $p_i$ and $p_{i+1}$. Let $n=p_1^{e_1}\cdots p_k^{e_k}$. Let $p_{i+1}=p$ for ease of typing. We set \[P(X)=p_1^{{(p-1)\cdot p^{e_{i+1}}\left\lceil \displaystyle\frac{e_1}{p-1}\right\rceil}}\cdots p_i^{{(p-1)\cdot p^{e_{i+1}}\left\lceil \displaystyle\frac{e_i}{p-1}\right\rceil}}p_{i+2}^{{(p-1)\cdot p^{e_{i+1}}\left\lceil \displaystyle\frac{e_{i+2}}{p-1}\right\rceil}}\cdots p_k^{{(p-1)\cdot p^{e_{i+1}}\left\lceil \displaystyle\frac{e_k}{p-1}\right\rceil}}Q(X)\]for some polynomial $Q$ we determine now. This definition ensures that $P(0)\equiv 0$ modulo any $p_j^{e_j}$ with $j\ne i+1$, and moreover ensures that $P(X)\equiv Q(0)\pmod{p^{e_{i+1}}}$. Now, define the polynomial $\overline{Q}(X)$ with degree $q$ such that \[\overline{Q}(0)=1,\overline{Q}(1)=2,\dots,\overline{Q}(q)=0.\]By Lagrange Interpolation, this polynomial exists and is moreover rational, and can be written as \[\frac{R(X)}{k}\]for some integer $k$ and $R(X)\in\mathbb{Z}[x]$, with $p\nmid k$. Hence, we can define the polynomial $Q(X)$ to be $R(X)\cdot c$ where $c$ is a positive integer such that $ck\equiv1\pmod{p^{e_{i+1}}}$. Now, note that $Q$ satisfies the same properties as $\overline{Q}$ over $\mathbb{Z}/p^{e_{i+1}}\mathbb{Z}$, so our definition of $Q$ works and hence our polynomial $P$ works.

Say a positive integer is $\emph{tight}$ if its prime factors are the first $k$ primes for some $k$ and $\emph{loose}$ otherwise. The answer is $\boxed{\text{all loose }n}.$ $\textbf{Claim: }$ All tight $n$ don't work. $\emph{Proof: }$ Suppose FTSOC there exists $m,P(x)$ satisfying the condition, and let $p$ be the largest prime dividing $n.$ Since $P(x+p)\equiv P(x)\pmod{p}$ for all $x,$ we know $P$ is a function on $\mathbb{F}_p.$ Therefore, cycles have length at most $p,$ so every element of $\mathbb{F}_p$ has order at most $p.$ This implies that $m\le p,$ which is a contradiction as all numbers less than $p$ are divisible by a prime less than $p.$ $\blacksquare$ $\textbf{Claim: }$ All loose $n$ work. $\emph{Proof: }$ Let $n=p_{1}^{e_1}p_{2}^{e_2}\dots p_{c}^{e_c},$ where $p_1<p_2<\dots<p_c.$ Choose a prime $p$ such that $p_k<p<p_{k+1}$ for some $k<m.$ For $a\in\{0,1,\dots,p-1\}$ and $b\in\{k+1,k+2,\dots,c\},$ choose $x_{ab}$ such that $$x_{ab}\equiv a\pmod{p_{b}^{e_b}},$$$$x_{ab}\equiv -1\left(\bmod\frac{p_{k+1}p_{k+2}\dots p_c}{p_b}\right).$$By construction, $p_{k+1},p_{k+2},\dots,p_c\nmid x_{a_1b_1}-x_{a_2b_2}$ for all $a_1,b_1,a_2,b_2.$ Therefore, we can choose $y_{ab}$ such that $$\left(\prod_{(i,j)\ne (a,b)}(x_{ab}-x_{ij})\right)\mid y,$$\[ y_{ab}\equiv \begin{cases} a+1\pmod{p_b^{e_b}} & a\ne p-1\\ 0\pmod{p_b^{e_b}} & a=p-1 \end{cases} \]By Lagrange Interpolation, the polynomial $P$ passing through $(x_{ab},y_{ab})$ for all $a,b$ has integer coefficients. Moreover, for $i\in\{k+1,k+2,\dots,c\},$ $$0\to 1\to 2\to\dots\to p-1\to 0$$is a cycle of $P$ over $\mathbb{Z}/p_{i}^{e_i}\mathbb{Z}.$ To finish, use CRT to change the constant term of $P$ such that it is divisible by $p_{1}^{e_1}p_{2}^{e_2}\dots p_{k}^{e_k}.$ $\blacksquare$

The answer is odd $n$ and even $n$ such that there exists a prime $p | n$ where some $i < p$ exists and $\gcd(n, i) = 0$. $n$ odd works, since we can choose $m = 2, P(x) = (n-1)x + 1$, so our attention goes to $n$ even. Our even condition is necessary because, if no such prime existed, then for each $p | n$, let $v_{p}(n) = k$. Consider the graph with vertices as residues $\mod p^{k}$. Draw an arrow between $x$ and $P(x)\mod p^{k}$ for each $x$. I claim the length of the cycle containing $0$ only contains prime divisors less than or equal to $p$. For each residue in that cycle, consider those residues $\mod p^{k-1}$. Each residue $\mod p^{k-1}$ can appear at most $p$ times in that cycle, and each residue $\mod p^{k-1}$ appears the same amount of times. Now, we can do the same for $p^{k-2}$, all the way to $p$, to show that the length of the cycle is a product of numbers all less than or equal to $p$. If the length of the cycle was greater than $1$, then it divides $m$ (since $p^{k} | P^{m}(0)$ and we're going around the cycle $m$ times) but this is a contradiction, since the gcd of the length of the cycle with $n$ is greater than $1$, which contradicts $\gcd(m ,n) = 1$. Thus, the length of the cycle is $1$, and this holds for all $p$, which means $n | P(0)$, another contradiction. This means that this condition is necessary. Now I will prove sufficiency. Let $p$ be the prime that satisfies the condition (if there are multiple, choose any). Furthermore, let $m$ be the number such that $m < p, \gcd(m, n) = 1$ (possible by our condition). I claim we can choose a rational polynomial $Q$ such that \[Q^{m}(0)\equiv 0\mod p^{k}, Q^{i}(0)\equiv i, Q(i)\equiv i+1 \mod p^{k} \]By Lagrange Interpolation, this polynomial exists and is rational; multiply the coefficients by some factor $k$ to get an integer polynomial. Furthermore, $p\not | k$, which means this new polynomial, let's denote as $R$, satisfies \[R^{m}(0)\equiv 0\mod p^{k}, R^{i}(0)\not\equiv 0\mod p^{k} \text{ for } 0 < i < m\]Now, consider all the other prime divisors of $n$. For each coefficient of $p$, we can keep adding $p^{k}$ to it until, for all $q | n, q\neq p$, we have that coefficient is divisible by $q^{v_{q}(n)}$. This is possible by the chinese remainder theorem. I claim this polynomial as $P(x)$ works. Clearly, $\mod p^{k}$ is still only $0$ at $P^{m}(0)$, since we can still just take $\mod p^{k}$. For all other primes that divide $n$, if $q^{k} | n$, then by our construction, $P(0)\equiv 0\mod q^{k}$, so $P(P(0)) \equiv 0\mod q^{k}$, and so on. This means that the only time possible for $n| P^{i}(0)$ is at $i = m$, and since all other primes also work at that stage, this polynomial satisfies the condition.

amuthup wrote: Moreover, for $i\in\{k+1,k+2,\dots,c\},$ $$0\to 1\to 2\to\dots\to p-1\to 0$$is a cycle of $P$ over $\mathbb{Z}/p_{i}^{e_i}\mathbb{Z}.$ To finish, use CRT to change the constant term of $P$ such that it is divisible by $p_{1}^{e_1}p_{2}^{e_2}\dots p_{k}^{e_k}.$ $\blacksquare$ What's "a cycle of P"? "CRT to change the constant term of $P$ such that it is divisible by $p_{1}^{e_1}p_{2}^{e_2}\dots p_{k}^{e_k}.$" You can detail?

A shorter solution (I hope?) Let $\omega(n)$ be smallest prime not dividing $n$ and $\Omega(n)$ be the largest prime dividing $n$, we claim that the answer is all $n$ such that $\omega(n)<\Omega(n)$ Neccessity - Let $n,m,P$ satisfy given conditions. As $n$ does not divide $P(0)$ we must have a prime $q$ dividing $n$ such that $\nu_q(P(0))< \nu_q(n)$, let $n' = q^{\nu_q(P(0))+1}$, so $n'|n$ . Let $m'$ be smallest number such that $P^{m'}(0)$ is divisible by $n'$ (so $m'>1)$, then we have $m' | m$ and hence gcd$(m',n)=1$. Modulo $n' ; 0,P(0),\cdots,P^{m'-1}(0)$ are all distinct. But $\frac{n'}{q}$ divides $P(0)$ implies it divides all $P^k(0)$ and hence we have at most $q$ possibilities for $0,P(0),\cdots,P^{m'-1}(0)$ mod $n'$. Hence we get $m' \leq q$, so if a prime $r$ divides $m'$ we have $r<q$ and $r$ does not divide $n$. Hence $\omega(n)\leq r < q \leq \Omega(n)$ as required . Sufficiency - Let $\omega(n) = r < q = \Omega(n)$ Let $\nu_q(n) = \alpha$ , and find an integer $u$ such that $n| uq^\alpha$ and $u \equiv 1$ ( mod $q^{\alpha}$) . We will find a $Q(x)$ such that modulo $q^{\alpha}$, $Q(0) = 1, Q(1) = 2 , .... , Q(r-1) = r, Q(r) = 0$, this is just langrange interpolation and using that all factors in denominator are less than $r$ and hence invertible mod $q^{\alpha}$. Now define $P(x) = u Q(x) $, so that $P(x) = Q(x)$ mod $q^{\alpha}$ and $P(x)$ is always divisible by $u$. Therefore the least $m$ such that $P^m(0)$ is divisible by $n$ is $r$ and we ofcourse have gcd$(r,n) = 1$. Hence proved .

We start with the following claim. Claim: If $n$ is divisible by the first $k$ primes for any $k$, then it doesn't satisfy our conditions. Proof: Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. We look at cycles modulo powers of the primes. Say we pick some prime $p_i$, now the residues of $p_i^{\alpha_{i}-1}$ occur atmost $p_i$ times if we consider the residues of the cycles of iterations of $P(0) \pmod{p_i^{\alpha_{i}}}$. Then we look at residues $\pmod{p_i^{\alpha_{i}-2}}$ and so on and realize that the length of the cycle is divisible by all these numbers less than and equal to $p$ and since $m$ would be the lcm of the lengths of cycles of all the primes we have a contradiction to the fact that $gcd(m, n)=1$. $\blacksquare$ Now for the construction, we pick $m=q$ to be the prime which is coprime to $m$ and is less than some other prime dividing $m$. We begin with the following claim Claim: $0, P(0), P^2(0), \cdots P^{q-1}(0)$ are distinct residues $\pmod{q}$. Proof: FTSOC, $P^i(0) \equiv P^j(0) \pmod{q}$ for some $i<j \leq q$, then clearly the length of the cycle doesnt remain $q$ which is clearly a contradiction. $\blacksquare$ Now, suppose $r$ is some random prime greater than $q$ dividing $n$, we consider the lagrange interpolation polynomial $\pmod{r^{\nu_r (n)}}$ $$P(x)_= \sum_{0 \leq i \leq q} y_i \prod_{i \neq j} \frac{(x-x_j)}{(x_i-x_j)} \pmod{r^{\nu_r (n)}}$$where $x_i$ are distinct modulo $r$. Now we can just use inverses $\pmod{r^{\nu_r (n)}}$ to fix the fractions and we have a nice polynomial $P(x) \in \mathbb{Z}[x]$. $\blacksquare$

Nice problem! Solved with rama1728. For any positive integer $n,$ call the orbit of $P(x)$ mod $n$ the smallest $l > 0$ where $P^l(0) \equiv 0 \pmod{n}.$ For some integer $n$ with prime factorization $p_1^{a_1}p_2^{a_2} \dots p_k^{a_k},$ note the orbit of $P(x)$ mod $n$ is the LCM of the orbits of $P(x)$ mod all the $p_i^{a_i},$ by CRT. We claim $n$ works if $p_1,p_2, \dots p_k$ are not the $k$ smallest primes. For a construction, let $p_k$ be the largest prime dividing $n$ WLOG. Take a prime $q$ less than $p_k$ not dividing $n.$ Then, take any polynomial $P(x)$ such that $$P(x) \equiv x+1-q\cdot \frac{x(x-1) \cdots (x-q+2)}{(q-1)!} \pmod{p_k^{a_k}}$$ and note $P(0),P^2(0), \dots P^{q-1}(0),P^{q}(0)$ correspond to $1,2, \dots q-1, 0 \pmod{p_k^{a_k}}$ respectively. So the orbit of $P(x)$ mod $p_k^{a_k}$ is $q.$ Setting the orbit of $P(x)$ mod any of the other $p_i^{a_i}$ as 1 gives us an orbit mod $n$ of $q,$ as desired. Suppose $p_1,p_2, \dots p_k$ are the $k$ smallest primes. If the orbit of $P(x) \pmod{n}$ is greater than $1$ and relatively prime with $n,$ then the orbit of $P(x)$ mod some $p_i^{a_i}$ is an integer greater than $1$ but sharing no factors with $n.$ We show that for any prime power $p^a,$ the orbit of $P(x)$ mod $p^{a}$ cannot have a prime factor greater than $p.$ That would mean the orbit of $P(x)$ mod $p_i^{a_i}$ has some prime factor at most $p_i,$ contradiction. We induct on $a.$ For the base case of $a=1,$ note the sequence $0, P(0), P^2(0), \dots $ can only take at most $p$ values mod $p,$ so the orbit of $P(x)$ mod $p$ cannot be larger than $p$ by PHP. For the inductive step, suppose $a > 1.$ Let $j$ be the orbit of $P(x)$ mod $p^{a-1}.$ So by the inductive hypothesis $j$ has no prime factors greater than $p.$ Then the orbit of $P(x)$ mod $p^{a}$ is just $j$ times the orbit of the polynomial $P^j(x)$ mod $p^a.$ But the sequence $0, P^j(0), P^{2j}(0), \dots $ can only take at most $p$ values mod $p^a,$ so the orbit of $P^j(x)$ mod $p^{a}$ cannot be larger than $p$ by PHP, which finishes. $\square$

The answer is all $n$ such that the set of prime factors of $n$ is not the set of the first $k$ primes for positive integer $k$. Let $n = \prod_{i=1}^t p_i^{a_i}$, where $p_1, p_2, \ldots, p_t$ are the distinct prime divisors of $n$, and also let $\mathrm{ord}_(a)$ denote the smallest positive integer $k$ with $P^k(0) \equiv 0\pmod k$. We have $m = \mathrm{ord}(N) = \mathrm{lcm}_{i=1}^t (\mathrm{ord} p_i^{a_i})$. Proof of sufficiency: Choose $q<p_t$ not dividing $n$. Consider the polynomial \[P(x)=x+1-(q+cp_t^{a_t})\cdot \frac{x(x-1)(x-2)\cdots (x-(q-2))}{(q-1)!} + d p_t^{a_t}\]in such a way that $P(0) \equiv 0\pmod{p_i^{a_i}}$ for any $1\le i\le t-1$ and $(q-1)\mid q + cp_t^{a_t}$ (this is possible by CRT). Notice this polynomial satisfies $\mathrm{ord}(p_i^{a_i}) = 1$ for any $1\le i\le t-1$. We claim that $\mathrm{ord}(p_t^{a_t})$ is equal to $q$. Note that $a\equiv b\pmod{p_t^{a_t}}$ implies that $P(a)\equiv P(b)\pmod{p_t^{a_t}}$, so we can take everything modulo $p_t^{a_t}$. We have $P(0)\equiv 1, P(1)\equiv 2, P(2)\equiv 3, \ldots, P(q-1)\equiv 0$, hence $\mathrm{ord}(p_t^{a_t}) = q$, which means we can set $m=q$ and this polynomial works. Proof of necessity: Suppose $p_1, p_2, \ldots, p_t$ are the first $t$ primes. We prove the following crucial claim: Claim: For any prime $p$ and positive integer $k$, $\mathrm{ord}(p^k)$ (if it exists) does not contain a prime factor larger than $p$. Proof: We will induct on $k$. First we prove the base case $k=1$. Suppose $\mathrm{ord}(p)$ existed and contained a prime factor larger than $p$. We have $P(0), P^2(0), \ldots, P^p(0)$ are all nonzero modulo $p$. This implies for some distinct $i,j \in \{1,2,\ldots, p\}$, $P^i(0)\equiv P^j(0) \pmod p$. Thus the sequence $(P(0), P(P(0)), \ldots, )$ eventually cycles modulo $p$, and the cycle does not contain $0$, which means $\mathrm{ord}(p)$ doesn't exist, absurd. Now assume its true for $k-1$ and below. If $\mathrm{ord}(p^{k-1})$ doesn't exist, the result is obvious, so assume it does, and set it equal to $o$. Suppose that $\mathrm{ord}(p^k)$ exists and contains a prime factor greater than $p$. The idea is that $(P^{o}(0), P^{2o}(0), \ldots, P^{p \cdot o}(0))$ are all nonzero mod $p^k$ and divisible by $p^{k-1}$. Hence by Pigeonhole Principle, we have distinct $i,j \in \{1,2,\ldots, p\}$ such that $P^{i\cdot o}(0)\equiv P^{j\cdot o}(0) \pmod{p^k}$. We notice that the sequence $(P^o(0), P^{2o}(0), \ldots,)$ eventually cycles modulo $p^k$ and the cycle does not contain $0$, which means $\mathrm{ord}(p^k)$ doesn't exist, contradiction. $\square$ Now, $\mathrm{ord}(n)$ does not contain any prime factors greater than $n$, so it cannot be relatively prime to $n$, done.

The answer is all $n$ which are not of the form $2^{a_1}3^{b_1}........p_i^{a_i}$.Let the $\text{orb}_n(P)$ denote the smallest positive integer s.t $P^{\text{orb}_m(P)}(0) \equiv 0 \pmod m$ where $P^k(0)=\underbrace{P(P.....P(0))))...)}_{k}$. Let $P^k(0)=a_k$.Note that $a_{k+\text{orb}_n(P)} \equiv a_k \pmod n$.Also $\text{orb}_n(P)=\text{lcm}(\text{orb}_{p_1^{a_1}}(P),...........,\text{orb}_{p_n^{a_n}}(P))-(1)$. Claim:- $\text{orb}_{p^n}(P)$ has a prime factor $<p$. Proof:- Use induction on $n$:-For $n=1$ we must have $\text{orb}_p(P)<p$ so it is right;now we prove it for $n=k+1$. By induction $\text{orb}_{p^k}(P)$ has a factor which is less than $p$.Consider $P^{\text{orb}_{p^k}(P)},..........,P^{p \cdot \text{orb}_{p^k}(P)}$.By $(1)$ $\text{orb}_{p^{k+1}}(P) \in \{ \text{orb}_{p^k}(P),2 \cdot {\text{orb}_{p^k}(P)},.........,p \cdot \text{orb}_{p^k}(P) \}$. All these numbers are $<p$ and so they must have a prime factor less than $p$, which finishes the induction. This proves that $\gcd(m,n)>1$ whenever $n=2^{a_1}3^{b_1}........p_i^{a_i}$ For the construction use Lagrange Interpolation.

The answer is all $n$ such that $\text{rad}(n) \neq \text{rad}(k!)$ for all $k$. By CRT each prime power $p^k \mid n$ is independent. Then notice the period mod $p^k$ is a multiple of the period mod $p$, which is from $1$ to $p$ by Lagrange interpolation, so since the overall period is the lcm of all these periods by CRT, having periods that are multiples of these strictly harms the process. All these can be constructed simply by Lagrange interpolation for periods $1$ to $p-1$ and $x+p^{k-1}$ for period $p$. It is also pointless to construct LCM if any divisor of the LCM exists already. Finding a solution thus requires and is equivalent (just take period $1$ in modulo every prime power other than the largest) to find a number less than the largest prime dividing $n$ which is coprime to $n$. This condition is equivalent to the claim, so we are done.

The answer is any $n$ such that the prime divisors of $n$ are not the first $k$ primes for any $k$. To see that this is necessary, suppose that the prime divisors of $n$ are precisely the first $k$ primes for some $k$. By constructing an arrow graph on $\mathbb{Z}/n\mathbb{Z}$, it is clear that there must exist a "minimal period", i.e. some $i>0$ such that $P^i(0) \equiv 0 \pmod{n}$ and if $P^j(0) \equiv 0 \pmod{n}$, then $i \mid j$. This minimal period must therefore not be divisible by any of the first $k$ primes, since otherwise $\gcd(m,n) \neq 1$. But by constructing an arrow graph on $\mathbb{Z}/p\mathbb{Z}$, where $p$ is a divisor of $n$, it is clear that the minimal $i_{p1}>0$ such that $P^{i_{p1}}(0) \equiv 0 \pmod{p}$ is at most $p$. But since $i$ has no divisors in the first $k$ primes, it follows that $i_{p1}$ must be exactly $1$. Now draw the arrow graph on $\mathbb{Z}/p^2\mathbb{Z}$ and note that by our previous result the only vertices which $0$ is connected to are those divisible by $p$, of which there are $p$, so the minimal $i_{p2}>0$ such that $P^{i_{p2}}(0) \equiv 0 \pmod{p^2}$ is at most $p$, hence it must be $1$. Repeating this, we find that for every prime power power $p^e$ dividing $n$, the minimal $i_{pe}$ such that $P^{i_{pe}}(0) \equiv 0 \pmod{p^e}$ is $1$, so by CRT $P(0) \equiv 0 \pmod{n}$, contradicting the fact that $m>1$. For a construction, pick a prime $p \nmid n$ and a prime $q>p$ dividing $n$. Let $e=\nu_q(n)$ and let $K=\frac{n}{q^e}$. Let $C$ be an integer such that $C(p-1)!K^{p-1} \equiv pK \pmod{q^e}$, which exists since $q \nmid (p-1)!K^{p-1}$. Take $$P(x)=(x+K)-Cx(x-K)\ldots(x-(p-2)K).$$Then $P(0)=K$, $P^2(0)=P(K)=2K$, and in general for $i \leq p-1$ we have $P^{p-1}(0)=(p-1)K$, which is never divisible by $q$. Now, observe that clearly $P^p(0) \equiv P(0) \equiv 0 \pmod{K}$. On the other hand, we also have $$P^p(0)=P((p-1)K)=pK-C((p-1)K)((p-2)K)\ldots(K)=pK-C(p-1)!K^{p-1} \equiv 0 \pmod{q^e},$$so $P^p(0) \equiv 0 \pmod{n}$ and taking $m=p$ works. $\blacksquare$

As long as there exists a prime $p' < p$ for some $p \mid n$, the integer $n$ works. For sufficiency, we can pick such a pair of primes $(p', p)$, and first set all $q^\alpha \mid P(0)$ for $\nu_q(n) = \alpha$ and $q \neq p$. Then, we can just do a quasi-Lagrange interpolation: set $$P(x) \equiv \frac{x(x-1)\cdots (x-p' + 2)}{(p'-1)!} - 1 \pmod p.$$ On the other direction, it suffices to show that the order of $P$ mod any prime power $p^\alpha$ has factors which are at most $p$; from here the result will follow by CRT. This follows by induction: for the base case, notice that $P^i(0) \equiv 0 \pmod p$ for some $i \leq p-1$, or else by cyclicity the order will not exist. Now observe that if $P^i(0) \equiv 0 \pmod {p^r}$, then $P^{ki}(0) \equiv 0 \pmod {p^r}$ for every $k$. In particular, set $Q(x) = P^i(x)$ and repeat the argument for $Q$ to produce another prime factor of the order. In particular, all these factors are less than $p$, as needed.

The answer is all $n$ such that, if $p$ is the largest prime dividing $n$, there there is another prime $q$ such that $q$ doesnt divide $n$. Such $n$ as described above work. I claim that for such $n$, $q$ as described above works as $m$. First, notice that $\gcd(n,q)=1$ trivially. Then, let $n=\prod_{i=1}^k p_i^{e_i}$ where $p_1<p_2<\dots<p_k$, and we aim to construct $P(x)$ that works. For brevity, let $K=p_k^{e_k}$ First, take $P(x)\equiv 0 \pmod{p_i^{e_i}}$ for $1\leq i \leq k-1$ so \[P(x)\equiv 0 \pmod {p_1^{e_1}\dots p_{k-1}^{e_{k-1}}}\qquad (1)\]Then, we choose \[P(x)\equiv c\cdot x(x-1)(x-2)\dots(x-(q-2))+x+1 \pmod{K}.\]Here, $P(i)=i+1$ for $i=0,1,\dots,q-2$ so we can see $P^{q-1}(0)\equiv q-1 \pmod K$. Thus, $P^q(0)\equiv c\cdot (q-1)!+q \pmod K$. As $q<p_k$, we see that $\gcd((q-1)!,K)=1$ so $(q-1)!$ has an inverse. This guarantees that we can pick such $c$ such that $c\cdot (q-1)!+q\equiv 0 \pmod K$. Therefore, we have $P^i(0)=i$ for $i<q$ and $p^q(0)=0$. Combining this with $(1)$ by crt on each coefficient, we get a working $P(x)$. All other $n$ fail Suppose that $(n,m)$ worked with $p_k$ being the maximal prime divisor of $n$ and all primes less than $p_k$ divide $n$. Given a polynomial $P$ and integer $p$, say the $p$ cycle of $P$ is equal to the smallest $k$ such that $P^k(0)\equiv 0 \pmod p$. Claim: For an integer $N$, its $N$ cycle has length at most $N$ Proof. If this cycle has length $k$, then note no two $P^a(0)\equiv p^b(0) \pmod{N}$ for $a,b<k$ since otherwise we'd get trapped in a mini cycle. The result follows since there are only $p_i$ residues to choose from. $\blacksquare$ Claim: For any prime $p_i$ dividing $n$, we have that the $p_i^{e_i}$ cycle of $p$ is $1$ or it has a divisor les than or equal to $p$. Proof. First, if the $p$ cycle is not $1$, then it is $k$ such that $k\leq p$ by the claim. Then, in this case $k$ clearly divides the cycle in question. If the $p$ cycle is $1$, take the arrows graph approach and the problem is equivalent to the one with $p_i^{e_i}-1$ and we can induct downwards. $\blacksquare$ Note that clearly $m$ must be the least common of all $p_i^{e_i}$ cycles of $P$ for $p \mid n$. But as all $p$ cycles are less than the largest prime divisor of $n$ this is a contradiction and we finish. Remark: Most of this was done in spanish class lol

nice problem

Hi, someone please check this. The construction seems simpler than the random ones i looked through (but didn't look through everything).

which now by lcm(ord($p_i^{e_i}$s))=ord(n)=m implies that m doesn't have any prime factors >the $p_i$s; our answer that we claim is that n cannot be the product of a group of powers of block of consecutive primes, which satisfies the necessity as in the earlier argument gcd(m,n)$\ne1$. For the sufficiency, $m=q<p_{l}<n\implies i\nmid n\forall i\in[1,m-1]\cap\mathbb Z\implies P(0)=1,P(1)=2,...,P(m-2)=m-1,P(m-1)=n$ works.

Let $g(n)$ be the smallest prime which does not divide $n$ and let $f(n)$ be the largest prime which does divide $n$, suppose that $g(n)>f(n)$, than we note that for the result to hold if we consider modulo every prime dividing $n$, the length of each cycle cannot be $1$ and thus must be divisible by a value that is not coprime to $n$ for at least one of the cycles, thus we get that the result is impossible. Now I will prove that for any prime power $p^n$ we can obtain such a $P$ for any value $1\leq m\leq P$, we can operate modulo $p^n$, thus we can choose $m$ distinct values modulo $P$, with the final value being $0$ and legrange interpolate it, as these values are all distinct none of the denominators in the legrange interpolation are $0$, this means we can turn the rational polynomial into an integer polynomial, and this polynomial will work. Now let a value $n=p_1^{\alpha_1}\dots$ such that $p_1$, is the largest prime dividing $n$ and such that $g(n)<p_1$, now let the polynomial such that it creates a cycle where every $k$ values it is divisible by $p_i^j$ be denote $P_{k,p_i^j}$, now consider the polynomial $\frac{n}{p_1^{\alpha_1}}P_{g(n)+p_1^{\alpha_1}}+\frac{n}{p_2^{\alpha_2}}P_{1, p_2^{\alpha_2}}+\frac{n}{p_3^{\alpha_3}}P_{1, p_3^{\alpha_3}}+\dots$ clearly this polynomial works with $m=g(n)$.

The answer is when $\operatorname{rad}n$ is not a primorial. Let $p$ be the smallest prime that does not divide $n$. Note that all prime factors of $m$ are at least $p$, so $m\ge p$. Note that we are saying there is a cycle of length $m$ starting from $0$ mod $n$. Now consider any prime $q<p$, so by definition it divides $n$. Now consider the length of the cycle, say $\ell$, of $0$ mod $q$. This has to exist, because otherwise it will never cycle mod $n$. But note that when it cycles back to $0$ mod $n$, it also has to cycle back to $0$ mod $p$. So $\ell\mid m$, meaning that $\ell=1$. This suffices to show that such $m$ does not exist when $\operatorname{rad}n$ is a primorial. Otherwise, I claim that we can construct such a polynomial where $m=p$, and where the entire cycle stays $0$ mod any prime power $q^r\mid n$ where $q<p$ but goes in the order $0,1,2,\dots,p-1,0$ for any prime power $q^r\mid n$ where $q>p$. This clearly suffices, so we can construct the polynomial multiplicatively by CRT. It is easy to do this when $q<p$ so we will focus on when $q>p$. So basically, we want to construct a polynomial $P$ over the integers mod $q^r$ such that $P(0)=1,P(1)=2,\dots,P(p-2)=p-1,P(p-1)=0$. Clearly this is possible mod $q$ by polynomial interpolation. But we can lift to mod $q^2$ by adding on $q$ times some polynomial to fix everything (utilizing polynomial interpolation mod $q$ and not mod $q^2$), and then lift to mod $q^3$, etc. $\blacksquare$