<s>[INST] How to solve this problem with $P(Q(n))\equiv n\pmod p$ for all integers $n$, the degrees of $P$ and $Q$ are equal. $p$ is a prime. Let $K_p$ be the set of all polynomials with coefficients from the set $\{0,1,\dots ,p-1\}$ and degree less than $p$. Assume that for all pairs of polynomials $P,Q\in K_p$ such that $P(Q(n))\equiv n\pmod p$ for all integers $n$, the degrees of $P$ and $Q$ are equal. Determine all primes $p$ with this condition
I try:Suppose that $a\not\equiv b\pmod{p - 1}$ satisfied $ab\equiv 1\pmod{p - 1}$. Then $P(x) = x^a, Q(x) = x^b$ would have $P(Q(n)) = n^{ab}\equiv n\pmod{p}$ for all integers $n$ and the degrees of $P, Q$ are unequal and less than $p$ when considering $a, b$ as least residues. then I can't,Thanks
 [/INST] To complete Peter's answer, which shows that $P=x^a$ and $Q=x^b$ works for some $(a,b)$ unless $p\in\{2,3,5,7,13\}$, here is a full explication in these cases:
If $p=2$ then, since $P$ and $Q$ can clearly not be constant, they must be linear, and so $p=2$ works.
If $p=3$, then $\deg P(Q(x))=(\deg P)(\deg Q)$ must be either $1$ or at least $3$. If it's $1$ then $\deg P=\deg Q=1$. Otherwise, neither can be $1$ (since both are $\leq 3$), so they must both be $2$, and so $p=3$ works.
For larger primes, we'll need the following result:
Lemma. If $P$ permutes the integers $\bmod p$, then $\deg P$ cannot divide $p-1$ unless $P$ is linear.
Proof. We know (for example via primitive roots or Newton sums) that
$$\sum_{x\in S}x^k\equiv \begin{cases}0&\text{if }1\leq k<p-1 \\ -1&\text{if }k=p-1,\end{cases}$$
for any complete residue system $S$ modulo $p$. if $P$ permutes such an $S$ and is of degree $d|p-1$, then
$$\sum_{x\in S}P(x)^{\frac{p-1}{d}}=0;$$
however, if you expand out $P(x)^{\frac{p-1}{d}}$ termwise, there is only one term of degree $p-1$ (which does not vanish) and all other terms are less, a contradiction. $\square$
Now, this shows that $p=5$ works, since the only nonlinear permutation polynomials mod $5$ can be of degree $3$. This can also be made to show that $p=7$ works; the only allowable polynomials are of degree $4$ and $5$. Now, consider a permutation polynomial $P$ of degree $4$. By replacing $P(x)$ with $aP(x+b)+c$ for some $b,c$ and nonzero $a$ (accompanied by corresponding changes in $Q$), we may assume that $P$ is monic and has no unit or $x^3$ coefficient. By replacing this $P(x)$ with $a^{-4}P(ax)$ for some $a\neq 0$ (and performing corresponding changes in $Q$) we may assume that the $x^2$ coefficient is either $0$, $1$, or $-1$. 
Consider $P(x)=x^4+x^2+ax$. If $a=0$ this is clearly not a permutation polynomial as $P(x)=P(-x)$; otherwise, if $-a$ is in the image of $x^3+x$ mod $7$, this is not a permutation polynomial as we can pick $x\neq 0$ so that $P(x)=0$. This image is the set
$$\{2,3,4,5\},$$
so we only have to deal with the case of $a=\pm 1$. These are isomorphic by flipping $x$ and $-x$; and if $P(x)=x^4+x^2+x$ then
$$P(1)\equiv 3\equiv P(4).$$
So, there are no permutation polynomials in this case. 
Consider $P(x)=x^4-x^2+ax$. We can deal with $a=0$ as before; now, if $-a$ is in the image of $x^3-x$ (and is nonzero) we are done by similar reasoning as the above. This happens for the set
$$a\in\{1,3,4,6\},$$
so we only care about $a=(\pm)2$. For this $a$, $P(1)\equiv P(2)\equiv 2$.
Now, consider $P(x)=x^4+ax$. By flipping the sign of the input of $P$, we need only consider $a\in\{0,1,2,3\}$. It is clear that $a=0$ does not work; also, $a=1$ fails since $P(-1)\equiv P(0)\equiv 0$, and $a=2$ fails since $P(1)\equiv P(3)\equiv 3$. However, $a=3$ works. So, we only need to consider the polynomial $x^4+3x$.
Now, we notice that $Q$ has to exactly invert $P$; from this, we know that the values of $Q$ modulo $p$ are exactly determined, and so we can find $Q$ directly using Lagrange interpolation; in other words, given $P$, only one unique $Q$ exists. Now observe the miraculous identity
\begin{align*}
(-x^4+3x)^4+3(-x^4+3x)
&\equiv(x^4-3x)^4-3x^4+2x\\
&\equiv x^{16}-12x^{13}+54x^{10}-108x^7+81x^4-3x^4+2x\\
&\equiv x^{16}+2x^{13}+5x^{10}+4x^7+x^4+2x\\
&\equiv x^4+2x+5x^4+4x+x^4+2x\\
&\equiv x\\
\end{align*}
where we have used Fermat's Little Theorem in the form $x^7\equiv x$. So, for this $P$, $Q$ is also of degree $4$, and thus $p=7$ works too. 
Now, for $p=13$, we see that $P(x)=x^9+4x^7+12x^5+4x^3+10x$ and $Q(x)=x^5+x^3+8x$ are inverses, so $p=13$ fails. Thus, our answer is $\boxed{p\in\{2,3,5,7\}}$.
</s>