# Around the property $(X+a)^n = X^n +a \pmod{X^r-1,p}$.

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 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.

• Appears to be asked already. Dec 27 '18 at 19:22
• Indeed I can't understand their answer so I'm happy you provided yours.
– Kuba
Dec 27 '18 at 19:27

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$$.