There's an unexplained step in a paper (AKS: Agrawal, Kayal, Saxena: PRIMES is in P) I'm reading that I don't understand. (equation (5))
Let $n$ be an integer divisible by a prime $p$. Additionally, $r<n$ is coprime with $n$.
$a$ is a fixed arbitrary constant in $\mathbb{Z}_p$.
Then the following two equalities $$(X+a)^n = X^n + a \pmod{X^r-1, p}$$ $$(X+a)^p = X^p + a \pmod{X^r-1, p}$$
imply the third one: $$(X+a)^{n/p} = X^{n/p} + a \pmod{X^r-1, p}$$
I do not expect that the$\pmod{X^r-1}$ will be relevant but I included it just in case it is.
Explanation of notation: $a = b \pmod{X^r-1, p}$ means $a = b$ in the ring $\mathbb{Z}_p[X]/(X^r-1)$.
I don't know how to approach proving this. I expect this is easy as it was not explained in any way in the paper. Thanks for any help.
In the ring $\mathbb{Z}_p[X]/(X^r-1)$ we have $A^p=B^p\implies A=B$.
This follows from $(A\pm B)^p=A^p\pm B^p$ (which holds already in $\mathbb{Z}_p[X]$) and $A^p=0\implies A=0$ (which can be deduced from $r$ being coprime to $n$ and thus to $p$; for an alternate way to go, if $A=\sum_{k=0}^{r-1}a_k X^k$, then $A^p=\sum_{k=0}^{r-1}a_k X^{pk\bmod r}$, and $k\mapsto pk\bmod r$ is a bijection).
It remains to put $A=(X+a)^{n/p}$ and $B=X^{n/p}+a$.