AKS - proving that $\frac{n}{p}$ is introspective

Question

I have a problem with showing that $\frac{n}{p}$ is introspective.

Recall that we are in state where a composite integer $n$ fools the AKS test and $p\mid n$ a prime number.

First of all, recall the following definitions and facts

• $p\mid n$ is a prime number and $p>r>1$.
• $R\stackrel{\text{def}}{=}\mathbb{F}_p[X]\pmod{X^r-1}$
• $\mathcal{P}_n\stackrel{\text{def}}{=}\{f\in R | f(X^n)=_Rf(X)^n\}$
• $\forall 1\leq a\leq r:X+a\in \mathcal{P}_n$
• $\mathcal{G}\stackrel{\text{def}}{=}\{i\in\mathbb{N} | (i,r)=1\wedge \forall f\in\mathcal{P}_n:f(X^i)=_Rf(X)^i\}$
• $p,n\in \mathcal{G}$

We wish to show that $\frac{n}{p}\in \mathcal{G}$. Let $f\in\mathcal{P}_n$ and observe the following

\begin{align*} f\big(X^{\frac{n}{p}}\big)^p & \stackrel{(1)}{\equiv} f\Big(\big(X^{\frac{n}{p}}\big)^p\Big) & \pmod{\big(X^{\frac{n}{p}}\big)^r-1,p}\\ & \equiv f(X^n) & \pmod{X^{\frac{n}{p}\cdot r}-1,p}\\ f\big(X^{\frac{n}{p}}\big)^p & \stackrel{(2)}{\equiv} f(X^n) & \pmod{X^r-1,p}\\ & \stackrel{(3)}{\equiv} f(X)^n & \pmod{X^r-1,p}\\ & \equiv \big(f(X)^{\frac{n}{p}}\big)^p & \pmod{X^r-1,p} \end{align*} Explanations

1. $p\in\mathcal{G}$ and using the identity w.r.t. the vairable $Y=X^{\frac{n}{p}}$
2. $X^r-1\mid X^{\frac{n}{p}\cdot r}-1$
3. $n\in\mathcal{G}$

Concluding we get that $$f\big(X^{\frac{n}{p}}\big)^p-\big(f(X)^{\frac{n}{p}}\big)^p\equiv 0\pmod{X^r-1,p}$$ But, $p>r>1$ all natural numbers, so $p>2$ and in particular it is an odd prime. Therefore $$\Big(f\big(X^{\frac{n}{p}}\big)-f(X)^{\frac{n}{p}}\Big)^p=f\big(X^{\frac{n}{p}}\big)^p+\big(-f(X)^{\frac{n}{p}}\big)^p\equiv f\big(X^{\frac{n}{p}}\big)^p-\big(f(X)^{\frac{n}{p}}\big)^p\equiv 0\pmod{X^r-1,p}$$

However, $R$ is not an integral domain so we cannot deduce that $$f\big(X^{\frac{n}{p}}\big)-f(X)^{\frac{n}{p}}\equiv 0 \pmod{X^r-1,p}$$

Please help, they say in the paper that it follows immediately and I do not understands why.

Edit: I have also noted that $$f(X^p)^{\frac{n}{p}}\equiv (f(X)^p)^{\frac{n}{p}}\equiv f(X^n)\equiv f(X)^n\pmod{X^r-1,p}$$

Note: The version of the paper that I work with

https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

Answer 1

Finally, the solution is simple, I think.

We factor $X^r-1$ into irreducible elements (using UFD) and take out the $p$ exponent, trivially (the resulting quotient rings are ID).

Finally, we use the CRT for rings in order to lose the exponent in our original ring $R$.