Tengo un problema con mostrar que $\frac{n}{p}$ es introspectivo.
Recordemos que estamos en un estado en el que un entero compuesto $n$ engaña a la prueba AKS y $p\mid n$ un número primo.
En primer lugar, recuerde las siguientes definiciones y hechos
- $p\mid n$ es un número primo y $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}$
Queremos demostrar que $\frac{n}{p}\in \mathcal{G}$ . Sea $f\in\mathcal{P}_n$ y observe lo siguiente
\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*} Explicaciones
- $p\in\mathcal{G}$ y utilizando la identidad con respecto a la vairable $Y=X^{\frac{n}{p}}$
- $X^r-1\mid X^{\frac{n}{p}\cdot r}-1$
- $n\in\mathcal{G}$
Concluyendo obtenemos que $$f\big(X^{\frac{n}{p}}\big)^p-\big(f(X)^{\frac{n}{p}}\big)^p\equiv 0\pmod{X^r-1,p}$$ Pero, $p>r>1$ todos los números naturales, por lo que $p>2$ y en particular es un primo impar. Por lo tanto, $$\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}$$
Sin embargo, $R$ no es un dominio integral por lo que no podemos deducir que $$f\big(X^{\frac{n}{p}}\big)-f(X)^{\frac{n}{p}}\equiv 0 \pmod{X^r-1,p}$$
Por favor, ayuda, dicen en el papel que sigue inmediatamente y no entiendo por qué.
Editar : También he observado que $$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}$$
Nota : La versión del papel con la que trabajo
https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
