imagine getting a 7

This is not a difficult problem to solve, but one needs to be very careful and not skip steps. The answer is $P(x)\equiv x^2+x+1$ and $P(x)\equiv (x^2+x+1)^2$ only. It works by taking $a=1,m=6$, for we can check $$x^2+x+1 \mid (x+1)^{x+1} - x^x$$if $x\equiv 1(\bmod\; 6)$. I will discuss why $P(x)\equiv (x^2+x+1)^2$ works later. Now I check it is the only one that works. Fix $a,m$. By Schur's theorem, since $P$ is nonconstant, there exists arbitrarily large primes $p$ such that $p\mid P(a+mx)$ for some $x$. Since $p>2022,$ $$p\mid (a+mx+1)^{a+mx+1} - (a+mx)^{a+mx}$$ Also, since $p\mid P(a+m(x+p))$, $$p\mid (a+mx+1)^{a+mx+mp+1} - (a+mx)^{a+mx+mp}$$ Thus, $$(a+mx+1)^m \equiv (a+mx)^m (\bmod\; p)$$by Fermat's Little Theorem. We can check $$(a+mx+1)^m \equiv 1(\bmod\; p)$$ Thus, if $Q(t)=\gcd( x^m-1, (x+1)^m-1)$ (in polynomials), then $p\mid Q(t)$ Claim: $Q(t)\in \{c, c(x^2+x+1)\}$ where $c$ is dependent on $m$. Proof: If $x^m-1, (x+1)^m-1$ don't share any roots, then $Q$ is a constant. Otherwise, suppose $\omega^m=(\omega+1)^m=1$. We can see $|\omega|=|\omega+1|=1$, so $\omega = \frac{-1}{2} + \frac{\sqrt{3}}{2}i$. Since $x^m-1$ has no repeated roots, $Q(t)=c(x^2+x+1)$ It follows that $p\mid \gcd(P,Q)$. If $P$ has an irreducible factor (in $\mathbb{Z}[x]$) that isn't $x^2+x+1$, we can use that irreducible factor $R$ to get $\gcd(R, c(x^2+x+1))$ is a constant, and thus can't be divisible by arbitrarily large primes. It remains to show $P(x)=(x^2+x+1)^2$ works and $P(x)=(x^2+x+1)^3$ fails. To see that $P(x)=(x^2+x+1)^2$ works, we need to show if $p^k\mid x^2+x+1$ then $p^{2k} \mid (x+1)^{x+1}-x^x$ if $x\equiv 1(\bmod\; 6)$. First, we can find $y=x+6tp^k$ such that $p^{2k}\mid y^2+y+1$ (check it works). Clearly, $p^{2k}\mid (y+1)^{y+1}-y^y$. We check $$(x+1)^{x+1}-x^x\equiv (y+1-6tp^k)^{y+1-6tp^k}-(y-6tp^k)^{y-6tp^k}$$ $$\equiv ((y+1)^{y+1-6tp^k} + (y+1-6tp^k)(y+1)^{y-6tp^k} (-6tp^k)) - (y^{y-6tp^k} +y^{y-6tp^k-1} (y-6tp^k) (-6tp^k)) (\bmod\; p^{2k})$$ $$\equiv (1-6tp^k) ((y+1)^{y+1-6tp^k}-y^{y-6tp^k})) (\bmod\; p^{2k})$$ By lifting the exponent, $$\nu_p( (y+1)^{6tp^k} - y^{6tp^k}) \ge k+\nu_p((y+1)^{6}-y^6) \ge k+\nu_p(y^2+y+1)\ge 2k$$so $$(y+1)^{y+1-6tp^k} \equiv (y+1)^{y+1} (y+1)^{-6tp^k} \equiv y^y y^{-6tp^k} \equiv y^{y-6tp^k} (\bmod\; p^{2k})$$ Therefore, $P(x)=(x^2+x+1)^2$ works. To see $P(x)=(x^2+x+1)^3$ fails, pick a large prime $p>m, p\mid x^2+x+1$. We can see $p^3\mid P(x) \mid (x+1)^{x+1}-x^x$. Consider all $A$ such that $p^3\mid (x+Ap+1)^{x+Ap+1}-(x+Ap)^{x+Ap}$. Clearly, $A$ can be any multiple of $m$, and suppose $p\nmid A$. We expand and bash mod $p^3$ (note fractions have denominators coprime to $p$, and $x(x+1)\equiv -1(\bmod\; p)$) We rearrange this to $$\left(\frac{x+1+Ap}{x+1}\right)^{x+1} (x+1+Ap)^{Ap} \equiv \left( \frac{x+Ap}{x}\right)^x (x+Ap)^{Ap} (\bmod\; p^3)$$ $$\iff \left( 1+\frac{Ap}{x+1}\right)^{x+1} (x+1+Ap)^{Ap} \equiv \left(1+\frac{Ap}{x}\right)^x (x+Ap)^{Ap} (\bmod\; p^3)$$ $$\iff \left(1+Ap+\binom{x+1}{2}\left( \frac{Ap}{x+1} \right)^2\right) \left((x+1)^{Ap}+(Ap)(x+1)^{Ap-1}(Ap)\right)$$ $$\equiv \left(1+Ap+\binom x2 \left(\frac{Ap}{x}\right)^2\right) (x^{Ap}+(Ap)x^{Ap-1}(Ap)) (\bmod\; p^3)$$ $$\iff \left(1+p^2 \frac{A^2 x}{2(x+1)}\right) \left((x+1)^{Ap}+p^2 \frac{A^2}{x+1}\right) \equiv \left(1+p^2 \frac{A^2 (x-1)}{2x}\right) \left(x^{Ap}+p^2 \frac{A^2}{x}\right)$$ This is true because by LTE, $p^2\mid (x+1)^{Ap}-1$ and $p^2\mid x^{Ap}-1$ for all $m\mid A$. Recall $(1+up^2)(1+vp^2)\equiv 1+(u+v)p^2(\bmod\; p^3)$ and I am multiplying $1$ mod $p^2$ stuff in the above equation. $$\iff \left(1+p^2 A^2\left(\frac{x}{2(x+1)}-\frac{x-1}{2x}\right) \right) \left( (x+1)^{Ap} +p^2 A^2\left(\frac{1}{x+1}-\frac 1x\right) \right) \equiv x^{Ap} (\bmod\; p^3)$$ We know $p^2\mid (x+1)^{6p}-x^{6p}$ because $p\mid x^2+x+1 \mid (x+1)^6-x^6$. Therefore, as $6\mid A$ (which is true because we've proven $6\mid m\mid A$), $(x+1)^{Ap} \equiv ((x+1)^{6p})^{\frac A6}\equiv (1+cp^2)^{\frac A6} \equiv 1+\frac{Ac}{6}p^2 (\bmod\; p^3)$ Where $(x+1)^{6p} \equiv 1+cp^2, x^{6p} \equiv 1+dp^2 (\bmod\; p^3)$ Hence, $\left(1+p^2A^2\frac{1}{2x(x+1)}\right) \left(1+\frac{Ac}{6}p^2+p^2A^2\frac{-1}{x^2+x}\right) \equiv 1+\frac{Ad}{6}p^2 (\bmod\; p^3)$ $A^2\frac{-1}{2} + \frac{Ac}{6} + A^2\equiv \frac{Ad}{6}(\bmod\; p)$, which is not true for all residues $A$ mod $p$ because this is a quadratic polynomial in $\mathbb{Z}_p[x]$

Here is a cleaner answer-extraction step:

There is an easier method to verify why $(x^2+x+1)^2$ works than @2above,and show why $(x^2+x+1)^3$ fails. https://drive.google.com/file/d/1yjw_fyUY98EH2sAB92acpSU34s5klfm2/view?usp=sharing

The answers are $P(n)=n^2+n+1,(n^2+n+1)^2$. Both work with $a=1,m=6$. I couldn't think of a better verification method than expanding the numerator and bashing everything (I did do that), so I will skip that part for now. To show that no other solution exists, I will prove that $P$ cannot have any irreducible factors outside of $n^2+n+1$. Through inspecting every residue mod $lcm(9,\phi (9))=18$, the numerator never becomes a multiple of $9$, and since $n^2+n+1$ is a multiple of $3$ whenever $3\nmid n$, if $\gcd(a,m) \nmid 3$, $P$ cannot be a multiple of $(n^2+n+1)^3$. When $n$ is a multiple of $3$, consider any prime divisor $p$ of $n^2+n+1$; since $n^3\equiv 1\pmod{p}$, the numerator is equivalent to $(n+1)^{n+1}-1\equiv (-n^2)^{n+1}-1\equiv \pm n^2-1$ modulo $p$, which evidently doesn't work. Hence, the result I assert is equivalent to the original problem. The following two lemmas are key to this solution. Lemma 1: $\gcd((x+1)^{b+1}-x^b,(x+1)^m-x^m)$ is either $1$ or $x^2+x+1$ for any nonnegative integer $b\le m$ and any choice of $m$. Proof: a root of the latter satisfies $|x+1|=|x|$, and a root of the former satisfies $|x+1|^{b+1}=|x|^b$. Hence any common root $r$ has $|r|=1$, and that forces $r=-\frac{1}{2}\pm \frac{\sqrt{3}}{2}i$. Obviously by conjugacy, if one number of this form is a common root, the other is too. Lemma 2: for all sufficiently large prime $p$ and any integer polynomials $f(x),g(x)$, any common root of $f(x)$ and $g(x)$ modulo $p$ is a root modulo $p$ of $\gcd(f(x),g(x))$. Proof: By Bezout, there exists integer polynomials $h(x),j(x)$ wth $\frac{f(x)}{\gcd(f(x),g(x))}h(x)+\frac{g(x)}{\gcd(f(x),g(x))}j(x)=c$ for some constant $c$. Now, choose any prime that's not a factor of $c$; on the LHS, plug in a common root that's not a root of $\gcd(f(x),g(x))$, and it becomes a multiple of $p$ while the RHS isn't. By Schur, since $P(a+mn)$ is an integer polynomial, the set of its prime divisors is infinite. Pick any sufficiently large prime $q$ that ever divides the denominator such that any common root of $(x+1)^{b+1}-x^b,(x+1)^m-x^m$ in $Z_q$ is a root of $\gcd((x+1)^{b+1}-x^b,(x+1)^m-x^m)$ for all nonnegative integers $b<m$, and $q$ is relatively prime to $m$ and $2022$. Let $n_0$ be the first value of $n$ such that the numerator is a multiple of $q$. $n_0+kmq$ for any positive integer $k$ also makes the denominator a multiple of $q$. Since $kmq\equiv km\pmod{q-1}$, we have $(n_0+1)^{n_0+1+km}-n_0^{n_0+km}$ is a multiple of $q$ for all $k$, which means $(n_0+1)^m\equiv n_0^m\pmod{q}$. Moreover, there exists a value of $k$ such that $n_0+1+km\pmod{q-1}$ is positive and at most $m$. Let that value be $b$; we have $(n_0+1)^{b+1}\equiv n_0^b\pmod{q}$. By lemmas 1 and 2, hence, any sufficiently large prime that ever divides the denominator is a prime divisor of $n^2+n+1$. By lemma 2, if the denominator has an irreducible factor other than $n^2+n+1$, it can only ever share a finite set of prime divisors with $n^2+n+1$. This loses by Schur's once again.

Quite hard for me to finish the last part, take me a lot of times

Didn't get this in-contest but looked up a bunch of cyclotomic polynomial facts afterwards and sort of solved it, except I thought $P(x)=(x^2+x+1)^2$ didn't work (note to self: headsolved computations are not legit), so here's a proof that any solution equals $P(x)=(x^2+x+1)^k$ for some $k$. First note that if $P(n)$ works, then any factors of $P(n)$ must as well, so we only consider $P$ irreducible and wish to show that $P(n)=n^2+n+1$ in this case. Note that by Schur's, $P(mx+a)$ has infinitely many prime divisors $p>2022$. For any of these, if $p \mid P(n)$, then $p \mid P(n+mp)$ as well, which means $$(n+1)^{n+1+mp} \equiv (n+1)^{n+1+m} \equiv n^{n+m} \equiv n^{n+mp} \pmod{p}$$dividing by $(n+1)^{n+1} \equiv n^n \pmod{p}$ yields $p \mid (n+1)^m-n^m$. Thus $P(n)$ and $(n+1)^m-n^m$ share a factor by Bezout's (as their GCD is unbounded), hence $P(n) \mid (n+1)^m-n^m$. The irreducible factors of $(n+1)^m-n^m$ are precisely the transformed cyclotomic polynomials $n^d \Phi_d(\tfrac{n+1}{n})$ for $d \mid m$, so $P(n)=n^d \Phi_d(\tfrac{n+1}{n})$ for some $d \mid m$. Now, the key idea is that because $n \equiv a \pmod{m}$, it must also be $a \pmod{d}$. Defining $p$ as before, with $p \mid P(n)$, this means that \begin{align*} \left(\frac{n+1}{n}\right)^{n+1} &\equiv \frac{1}{n} \pmod{p}\\ \left(\frac{n+1}{n}\right)^{a+1} &\equiv \frac{1}{n} \pmod{p}\\ (n+1)^{a+1} &\equiv n^a \pmod{p}. \end{align*}Since we also have $(n+1)^d \equiv n^d \pmod{p}$, this means that $$(n+1)^{ad} \equiv n^{ad} \equiv (n+1)^{d(a+1)} \implies (n+1)^d \equiv 1 \pmod{p},$$as clearly we cannot have $n \equiv -1 \pmod{p}$. This readily implies that $n^d \equiv 1 \pmod{p}$ as well. Switching over to $\mathbb{C}$, this means that for every primitive $d$-th root of unity $z$, $\tfrac{1}{z-1}$ is a $d$-th root of unity as well, as if $z=\tfrac{n+1}{n}$ then $\tfrac{1}{z-1}=n$. Then it is necessary to have $|z-1|=1$ with $|z|=1$, so $z=e^{\pm \pi/3}$ and $d=6$. After some manual computation, this implies that $P(n)=n^2+n+1$ as desired. $\blacksquare$

By the way, the fact that \[\frac{(n^2+n+1)^2}{3} \mid (n+1)^{n+1}-n^n\]for $n \equiv 1 \pmod{6}$ is an old problem (I saw it on a training competition seven years ago, and I doubt it was original back then). But of course the fact that this is essentially the only such identity is an interesting feature of this problem I did not know before.

The answer is $x^2 + x + 1$ and $(x^2 + x + 1)^2$. We first show that these work. For $x^2 + x + 1$, we can just take $n \equiv 1\pmod 6$. Since $n^6$ and $(n+1)^6$ are $1$ modulo $n^2 + n + 1$, we have\[(n+1)^{n+1} - n^n \equiv (n+1)^2 - n \equiv 0\pmod{n^2 + n + 1}\]Now we show $(x^2 + x + 1)^2$ works for $m = 12$ and $a = 1$. Let $n = 12k + 1$ and $t = n^2 + n + 1$. We have $n^3 = (n-1) t + 1$, so\[n^{12k + 1} = n \cdot (n^3)^{4k} = n\cdot ((n-1) t + 1)^{4k} \equiv 4kn(n-1) t + n \pmod{t^2}\]using binomial theorem. Now, $(n+1)^2 = t + n$, so\[(n+1)^{n+1} = ((n+1)^2)^{6k + 1} = (t + n)^{6k + 1} \equiv (6k + 1) t n^{6k} + n^{6k + 1} \pmod{t^2}\]Now, $n^{6k} = (n^3)^{2k} \equiv 2k(n-1) t + 1 \pmod{t^2}$. So,\[ (6k + 1)t n^{6k} \equiv (6k + 1) t \pmod{t^2}\]We have $n^{6k + 1} \equiv 2kn(n-1) t + n \pmod{t^2}$, so altogether,\[ (n+1)^{n+1} - n^n \equiv (6k + 1) t + 2kn(n-1) t + n - 4kn(n-1) t - n \equiv t(6k + 1 - 2kn(n-1) ) ,\]so $2022 ((n+1)^{n+1} - n^n)$ equals\[2022 t \left( \frac{n+1}{2} - \frac{n-1}{6} n(n-1) \right) = 337 t \left( 3(n+1) - (n-1)^2 n \right) \equiv 337t (3(n+1) + 3n^2)\equiv 1011 t^2 \equiv 0 \pmod{t^2}\]so $t^2 \mid 2022(n+1)^{n+1} - n^n$ for all $n \equiv 1\pmod{12}$, meaning $P(n) = (n^2 + n + 1)^2$ works. Let $p\mid n^2 + n + 1$. Then $(n+1)^{n+1} - n^n$ notice that $p\mid (n+1)^2 - n$, so $\nu_p((n+1)^{2n} - n^n) = \nu_p(n^2 + n + 1) $ then $(n+1)^{n+1} ((n+1)^{n-1} - 1) $. Now we prove that nothing else works. Let $d = \deg P$, $Q(x) = P(mx + a)$ and $f(n) = (mn + a + 1)^{mn + a + 1} - (mn + a)^{mn + a}$. Clearly $Q(n)$ is a polynomial of degree $d$ and leading coefficient $m^d$, is not constant, and is nonzero for nonnegative integers $n$. We also have\[ 2022 \cdot \frac{f(n)}{Q(n) } \]is an integer for all nonnegative integers $n$. Notice by Schur, $Q(n)$ takes on infinitely many prime divisors as $n$ varies. Let $p>2022, p > m + 1$ be some large prime dividing $Q(n)$ for some $n$. We get that $p$ divides $Q(n+kp)$ for any integer $k$. So $p\mid f(n + kp)$. This implies $(mn + a + 1 + k \cdot mp)^{mn + a + 1 + k \cdot mp} \equiv (mn + a + k \cdot mp)^{mn + a + k \cdot mp} \pmod p$. If $mn + a + 1 \equiv 0\pmod p$ or $mn + a \equiv 0\pmod p$, we get an obvious contradiction. Now divide both sides of the equation by $(mn + a + k \cdot mp)^{mn + a + 1 +k \cdot mp} $. We have that $ \left( \frac{mn + a + k \cdot mp +1 }{mn + a + k \cdot mp} \right)^{mn + a + k \cdot mp + 1} \equiv \frac{1}{mn + a + k \cdot mp } \pmod p$ now taking modulo $p$ on both sides, we have\[ \left( \frac{mn + a + 1}{mn + a }\right)^{mn + a + k \cdot mp + 1} \equiv \frac{1}{mn + a } \pmod p \]Now using FLT, the LHS is $ \left( \frac{mn + a + 1}{mn + a} \right)^{m(n+k) + a + 1} $ modulo $p$, so for all positive integers $t > n$,\[ \left( \frac{mn + a + 1}{mn + a} \right)^{mt + a + 1} \equiv \frac{1}{mn + a} \pmod p , \]so\[ \left( \frac{mn + a + 1}{mn + a} \right)^{a + 1} \equiv \frac{1}{mn + a} \pmod p\]and by comparing $t$ and $t + 1$, we have $\left( \frac{mn + a + 1}{mn + a} \right)^m \equiv 1\pmod p$. Now taking the first of the two equations to the power $m$ on both sides gives that $(mn + a)^m \equiv 1\pmod p$, so $(mn +a + 1)^m \equiv 1\pmod p$ also. Let $x \equiv mn + a\pmod p$. We have that $x^m \equiv (x+1)^m \equiv 1\pmod p$. So then $p$ divides $(x+1)^m - x^m$. Also, $(mn + a + 1)^{a+1} \equiv (mn + a)^a \pmod p$, so $p\mid (x + 1)^{a+1} - x^a$. Claim: Any complex number $r$ with $(r+1)^m - r^m = 0$ and $(r+1)^{a+1} - r^a = 0$ satisfies $r^3 = 1$. Proof: We have $|(r+1)^m| = |r^m|$, so $|r+1|^m = |r|^m$, implying that $|r+1| = |r|$. Now, we also have $|r|^{a+1} = |r+1|^{a+1} = |r|^a$, so $|r|^a (|r| - 1) = 0$, so $|r|\in \{0,1\}$. Since $r\ne 0$, $|r| = 1$ and therefore $|r+1| = 1$ also. Let $r = a_1 + bi$ for reals $a_1, b$. We have $a_1^2 + b^2 = 1$ and $(a_1 + 1)^2 + b^2 = 1$, so $2a_1 + 1 = 0 \implies a_1 = -\frac{1}{2}$. Now this implies $b^2 = \frac{3}{4}$, so $b = \pm \frac{\sqrt{3}}{2}$. Thus, if we write $r = \cos \theta + i \sin \theta$, either $\theta = \frac{2\pi}{3}$ or $\theta = \frac{4\pi}{3}$, so $r^3 = \cos (3 \theta) + i \sin (3 \theta) = 1$, as desired. $\square$ Clearly any such complex number $r$ can't satisfy $r = 1$, so it must satisfy $r^2 + r + 1 = 0$. Hence $\gcd((X+1)^m - X^m, (X+1)^{a+1} - X^a)$ in polynomial gcd divides $X^2 + X + 1$. Now for some positive integer $M$ there exist integer polynomials $p_1, q_1$ satisfying\[p_1(X) ((X+1)^m - X^m) + q_1(x) ((X+1)^{a+1} - X^a) = M(X^2 + X + 1),\]meaning that setting $X = x$ gives $p \mid M(x^2 + x + 1)$, so $p\mid x^2 + x + 1$ for all $p > \max(M,m,337)$ dividing $Q(n) = P(x)$. Case 1: $P(x)$ is not a power of $x^2 + x + 1$. We may assume $P(x)$ is irreducible (since if one polynomial work, all its nonconstant factors also work) and not equal to $x^2 + x + 1$ (and $x^2 + x + 1$ is irreducible), $\gcd(P(x), x^2 + x + 1) = 1$. Then for some positive integer $C$ and integer polynomials $p_2, q_2$, we have\[ p_2(X) P(X) + q_2(X) (X^2 + X + 1) = C,\]implying for all primes $p > C$ dividing $P(x)$ don't divide $x^2 + x + 1$. Using Schur again, we may take some prime $p$ dividing $P(x)$ for some $x$ with $p > \max(M,m,337,C)$, so $p$ can't divide $x^2 + x + 1$, absurd. Thus, the only working irreducible polynomial is $P(x) = x^2 + x + 1$. Case 2: $P(x)$ is a power of $x^2 + x + 1$ Assume $P(x) = (x^2 + x + 1)^3$. Then we see that all primes $p\mid P(x)$ divide $x^2 + x + 1 \mid x^3 - 1$ and also divide $x^m - 1$. If $3\nmid m$, it implies they divide $x - 1$, so they can't divide $x^2 + x + 1$, absurd. Hence $3\mid m$. Now, if $\gcd((X+1)^m - X^m, (X+1)^{a+1} - X^a) = 1$, then we could choose $p_1, q_1$ integer polynomials and some integer $K$ such that $p_1(X) ((X+1)^m - X^m) + q_1(x) ((X+1)^{a+1} - X^a) = K$, which is a contradiction for large primes $p$ dividing $P(x)$. Hence $X^2 + X + 1$ divides $(X+1)^m - X^m$ and $(X+1)^{a+1} - X^a$. Since $3 \mid m$, we $X^m \equiv 1\pmod{X^2 + X + 1}$, so $X^2 + X + 1$ must divide $(X+1)^m - 1$, meaning $6\mid m$. We must have $X^2 + X + 1 \mid (X+1)^{a+1} - X^a$. This is clearly a solution for $a = 1$ but not $a \in \{0,2,3,4,5\}$, meaning that we must have $a \equiv 1\pmod 6$. Therefore, $n \equiv 1\pmod 6$. But $P(n) = (n^2 + n + 1)^3$ is a multiple of $27$, but $(n+1)^{n+1} - n^n \equiv (n+1)^2 - n = n^2 + n + 1$ is not a multiple of $9$, so $P(n)$ can't divide $2022 ((n+1)^{n+1} - n^n)$, absurd.