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.

  • 1
    $\begingroup$ Appears to be asked already. $\endgroup$
    – metamorphy
    Dec 27 '18 at 19:22
  • $\begingroup$ Indeed I can't understand their answer so I'm happy you provided yours. $\endgroup$
    – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.