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
 A: Note: Not a complete answer (yet).
First of all, it's easy to verify that $p=2$ works: Neither $P$ nor $Q$ can be constant and the only remaining polynomials in $K_2$ are of degree $1$. From now on, we will assume that $p\geq 3$ is an odd prime.
If $1\leq a<p$ is any integer such that $\gcd(a,p-1)=1$, there is an integer $1\leq b<p$ such that $$ab\equiv 1\pmod{p-1}$$ Set $P(x)=x^a$ and $Q(x)=x^b$.


*

*If $x\equiv 0\pmod p$, we clearly have $P(Q(x))\equiv 0\equiv x\pmod p$.

*Otherwise $x^{p-1}\equiv 1\pmod p$ and thus $P(Q(x))\equiv x^{ab}\equiv x^{ab \bmod (p-1)}\equiv x\pmod p$
According to the condition given in the problem statement, we must have $a=b$. This further implies that $(a^2-1)$ must be divisible by $(p-1)$ and thus either $a=1$ or $p\leq a^2$. However, the only restriction on $a$ we have is that it is coprime to $(p-1)$, so any $a$ such that $1<a^2<p$ must not be coprime to $(p-1)$. In particular, it needs to be true for prime values of $a$, for which not being coprime to $a$ is the same as being divisible by $a$. Thus, $(p-1)$ must be divisible by product of all primes smaller than $\sqrt{p}$.
Let $p_1,p_2,\ldots,p_k$ be the primes in their natural order. We will show by induction that for $k\geq $4: $$\prod_{i=1}^k p_k\geq p_{k+1}^2$$
The base case, $k=4$ is obvious ($2\times 3\times 5\times 7=210\geq 11^2$). In the inductive case, it is sufficient to note that Bertrand's postulate tells us $p_{k+2}^2\leq 4p_{k+1}^2$ but the product on the left-hand side gets multiplied by $p_k\geq 11$.
If $(p-1)$ was divisible by first $k\geq 4$ primes, the square root of $p$ would exceed $p_{k+1}$, so it would have to be divisible by $p_{k+1}$ too, ad infinitum. We can now consider the remaining small cases:


*

*For $1<p< 4$, we do not have any restrictions, so $p=3$ remains.

*For $4<p<9$, we have $(p-1)$ divisible by $2$, which is satisfied by both $p=5$ and $p=7$.

*For $9<p<25$, $(p-1)$ must be divisible by $2\times 3=6$, which yields $p=13$ and $p=19$.

*Finally, for $25<p<49$, $(p-1)$ must be divisible by $2\times 3\times 5 = 30$, yielding $p=31$.


Of course, $(p-1)$ being divisible by the small primes is only a necessary condition, not a sufficient one. We can further eliminate $p=19$ and $p=31$ by noting that $a=7$ is coprime to $(p-1)$ but $7^2-1=48$ is not divisible by $(p-1)$.
Thus, the list of candidate primes narrows down to $p=\{3,5,7,13\}$.
A: 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\}}$.
