PRIMES is in P, page 4, equation (5)
Edit: I should probably add that $p$ is a prime factor of some $n$. $a$ is any number from 1 to some irrelevant limit. $r$ also shouldn't matter because as far as I can see nothing we know about it is relevant. Edit 5: It is also given that $gcd(r,p)=1$, which I use in the answer below.
We are in $\mathbb{Z}[X]/(X^r-1,p)$. The authors claim
$$(X+a)^{n} \equiv X^{n}+a~~~(3)$$
together with
$$(X+a)^{p} \equiv X^{p}+a~~~(4)$$
implies
$$(X+a)^{\frac{n}{p}} \equiv X^{\frac{n}{p}}+a~~~(5)$$
I tried to prove it and even without using (3) or (4), all I got was a contradiction. Where is my mistake and what is the correct proof?
My attempt: Suppose (5) holds, then:
$$X^{\frac{n}{p}}+a \equiv (X+a)^{\frac{n}{p}} \equiv \sum_{k=0}^{n/p} \binom{n/p}{k}X^{\frac{n}{p}-k}a^{k}$$
$$\implies \binom{n/p}{k}X^{\frac{n}{p}-k}a^{k} \equiv 0~~~\forall 0 < k < \frac{n}{k}$$
Let $k=1, p \not | a, p^2 \not| n$: $$\implies \binom{n/p}{1}X^{\frac{n}{p}-1}a^{1} \equiv \frac{n}{p}X^{\frac{n}{p}-1}a \not \equiv 0 \text{ - contradiction to the previous line}$$
Edit2:
I want to add that this clearly holds for any number $c$ that we plug into the polynomial, since the value of $(c+a)^{\frac{n}{p}} \equiv (c+a)^{p\frac{n}{p}} \equiv (c+a)^n \equiv c^n+a \equiv c^{p\frac{n}{p}}+a \equiv c^{\frac{n}{p}}+a$. But the statement is that the polynomials are equal. That's also clearly what is meant by the authors because otherwise (4) would be trivial.
Edit3:
The claim can also easily be proven for $X^p$ instead of $X$, but I am not sure if that's of any use:
Left side of (3): $$(X+a)^{n} \equiv (X+a)^{p \frac{n}{p}} \equiv (X^p+a)^{\frac{n}{p}}$$ Right side of (3): $$X^n+a \equiv X^{p \frac{n}{p}}$$ And together: $$\implies (X^p+a)^{\frac{n}{p}} \equiv X^{p \frac{n}{p}} \text{ in } \mathbb{Z}[X]/(X^r-1,p)$$ Now if $r$ was a multiple of $p$ (which it is not), we could substitute $X^p$ with $X$, which would give us (5) in $\mathbb{Z}[X]/(X^{r/p}-1,p)$, which should imply (5) in our original ring $\mathbb{Z}[X]/(X^r-1,p)$ since $X^{r/p}=1 \implies (X^{r/p})^{p}=1$. But maybe this is going in the right direction?
Edit4:
It can also be proven that both sides of (5) are equal when being raised to the power of $p$. This seems the closest to the actual claim, but I can't think of an argument why it would imply (5).
Left side of (3): $$(X+a)^n \equiv ((X+a)^{\frac{n}{p}})^p$$
Right side of (3): $$X^n+a \equiv X^{p \frac{n}{p}}+a^p \equiv (X^{\frac{n}{p}}+a)^p$$
Together: $$\implies ((X+a)^{\frac{n}{p}})^p \equiv (X^{\frac{n}{p}}+a)^p$$
So I think I found the answer using the conditition $gcd(r,p)=1$, which I didn't previously mention. It would be nice if someone could verify this answer.
Since we are in $\mathbb{Z}[X]/(X^r-1,p)$, $X$ is a root of unity. But even better, since $gcd(r,p)=1$, $X^p$ is a root of $X$.
$\implies \exists h : X^{ph} \equiv X$.
From Edit3 we have
$$(X^p+a)^{\frac{n}{p}} \equiv X^{p \frac{n}{p}}+a~~~\text{ in } \mathbb{Z}[X]/(X^r-1,p)$$ which we can write as $$\iff (X^p+a)^{\frac{n}{p}} = X^{p \frac{n}{p}}+a +i(X)~~~\text{ in } \mathbb{Z}[X] \text{ with }i(X) \in (X^r-1,p)$$ The polynomials are equal, so they are still equal if we raise $X$ to the power of $X^h$: $$\implies (X^{ph}+a)^{\frac{n}{p}} = X^{ph \frac{n}{p}}+a +i(X^h)~~~\text{ in } \mathbb{Z}[X] \text{ with }i(X) \in (X^r-1,p)$$ Looking at $(X^r-1,p)$ one can see that for arbitrary positive integers $k$: $$i(X) \in (X^r-1,p) \implies i(X^k) \in (X^r-1,p)$$ In other words: $i(X^h)$ is still equivalent to zero in our ring $\mathbb{Z}[X]/(X^r-1,p)$. Thus moving back to the ring we get $$\implies (X^{ph}+a)^{\frac{n}{p}} \equiv X^{ph \frac{n}{p}}+a$$ $$\iff (X+a)^{\frac{n}{p}} \equiv X^{\frac{n}{p}}+a$$
Now if this is correct, the question still stands which part of the contradiction in my original post is wrong.
Also, considering that the authors of PRIMES is in P literally write "From equations 3 and 4 it follows that (5)" without any explanation whatsoever, I am convinced that there is a much easier proof, and so I will leave this question open.