En realidad, el primer documento ( versión 6 ) que ha leído es la versión más reciente; la anales de matemáticas se publicó primero y contiene un error en el lema 4.3 (hay un reconocimiento en el documento de la versión 6 que señala el error). El problema está en la última línea de la prueba, que es exactamente donde te has quedado atascado.
Error en el lema 4.3 de AKS (versión de Annals of Math)
Dado que $s \not \in \{r_1,\ r_2,\ ...,\ r_t\}$ y $(s,n) > 1$ no es necesariamente cierto que $\frac{s}{(s,n)} \not \in \{r_1,\ r_2,\ ...,\ r_t\}$ . Considere lo siguiente:
Desde $s \not \in \{r_1,\ r_2,\ ...,\ r_t\}$ sabemos que $s$ no divide $n$ y, o bien $o_s(n) > \log_2^2(n)$ o $o_s(n)$ no existe. Si $(s,n) > 1$ entonces $o_s(n)$ no existe, pero eso no implica que el orden de $n$ modulo $\frac{s}{(s,n)}$ es mayor que $\log_2^2(n)$ .
Supongamos que $n = 8$ . Entonces el 6 es el primer número que encontramos que no está en $\{r_1,\ r_2,\ ...,\ r_t\}$ porque $o_6(8)$ no existe, y 6 no divide a 8. Sin embargo, $\frac{6}{(6,8)} = \frac{6}{2} = 3$ et $3 \in \{r_1,\ r_2,\ ...,\ r_t\}$ porque $o_3(8) = 2$ et $2 \leq \log_2^2(8) = 9$ .
Mi prueba del lema 4.3
Resulta que el $n^{\lfloor\log(B)\rfloor}$ introducido en la nueva versión del documento es necesario para abordar este tipo de contraejemplo. También me pareció que la prueba de la versión 6 era bastante difícil de entender; se omitían muchos pasos. Así que a continuación hay una prueba ampliada que escribí yo mismo. Espero que sea más clara; hazme saber si algo no tiene sentido :) La prueba se divide en tres pasos: encontrar un valor lo suficientemente pequeño $r$ , lo que demuestra que $o_r(n)$ existe, y finalmente mostrando que $o_r(n) > \log^2{n}$ .
Afirmación: Existe un $r \leq$ max $\{3,\lceil\log^5{n}\rceil\}$ tal que $o_r(n) > \log^2{n}$ .
Prueba: Sabemos que $n>1$ . Si $n=2$ podemos dejar que $r=3$ y como $2^2 = 4 \equiv 1 \text{ mod } 3$ , $o_3(2) = 2$ , mientras que $\log^2{2} = 1$ por lo que la afirmación es válida. A partir de aquí, supongamos que $n>2$ . Tenga en cuenta que $\lceil \log^5 3 \rceil = 11$ y como la función logaritmo es monótonamente creciente, sabemos que $\lceil \log^5 n \rceil > 10$ para todos $n>2$ . Sea $B = \lceil \log^5 n \rceil$ . Aplicando el lema 3.1, tenemos que $LCM(B) \geq 2^{B}$ . Primero demostraremos que existe un número $r\leq B$ que no divide el producto $$N=n^{\lfloor\log{B}\rfloor} \cdot \displaystyle\prod_{i=1}^{\lfloor\log^2(n)\rfloor}(n^i-1)$$ Supongamos, por contradicción, que para todo $1\leq r \leq B$ , $r$ divide $N$ . Entonces, claramente $LCM(B) \leq N$ porque $N$ es un múltiplo común de todos los números menores o iguales a $B$ . Observe que \begin{align*} N&=n^{\lfloor\log{B}\rfloor} \cdot \displaystyle\prod_{i=1}^{\lfloor\log^2(n)\rfloor}(n^i-1) \\ &< n^{\lfloor\log{B}\rfloor} \cdot \displaystyle\prod_{i=1}^{\log^2(n)}(n^i) \\ &= n^{\lfloor\log{B}\rfloor+1+2+...+\log^2(n)} \\ &= n^{\lfloor\log{B}\rfloor+\frac{1}{2}(\log^2(n)((\log^2(n)+1))} \\ &= n^{\lfloor\log{B}\rfloor+\frac{1}{2}(\log^4(n)+\log^2(n))} \\ &< n^{\log^4(n)} \\ &= (2^{\log(n)})^{\log^4(n)} \\ &= 2^{\log(n)\cdot \log^4(n)}\\ &= 2^{\log^5(n)}\\ &\leq 2^{B} \end{align*} Por lo tanto, $N < 2^{B}$ . Recordemos que $LCM(B) \geq 2^{B}$ , por lo que tenemos $LCM(B) > N$ . Sin embargo, ya hemos visto que $LCM(B) \leq N$ una contradicción. Por lo tanto, el conjunto de números entre 1 y $B$ que no dividen $N$ es no vacía; que $r$ sea el elemento más pequeño de este conjunto.
Hemos encontrado un $r\leq B$ Ahora tenemos que demostrar que $o_r(n)$ existe, y que $o_r(n) > \log^2{n}$ . Recordemos que el orden de $n$ modulo $r$ sólo existe si $(r,n) = 1$ . Demostraremos que esto es así. Escribe $r=ab$ donde los factores primos de $a$ son precisamente los factores primos de $r$ que dividen $n$ et $b$ se compone de los restantes factores primos. Es evidente que $(b,n) = 1$ , ya que $n$ y $b$ no tienen factores primos comunes. Obsérvese que la potencia más alta a la que se puede elevar cualquier primo en la factorización primaria de $a$ es $\lfloor \log{B}\rfloor$ ya que de lo contrario $a \leq r$ sería mayor que $B$ (esto se debe a la observación de que "el mayor valor de $k$ para cualquier número de la forma $m^k \leq B$ , para $m\geq2$ es $\lfloor \log{B}\rfloor$ "del documento AKS). Por lo tanto, cada factor primo en $a$ se eleva a un exponente menor que el mismo factor en $n^{\lfloor\log{B}\rfloor}$ y como todo factor primo de $a$ está presente en $n$ debe ser el caso que $a$ divide $n^{\lfloor\log{B}\rfloor}$ . De ello se desprende que $b$ no divide $\displaystyle\prod_{i=1}^{\lfloor\log^2(n)\rfloor}(n^i-1)$ porque si lo hiciera, entonces $r = ab$ dividiría $N$ y elegimos $r$ para que no sea así. Sin embargo, también es cierto que $b$ no divide $n^{\lfloor\log{B}\rfloor}$ , ya que $(b,n) = 1$ . Por lo tanto, $b$ no divide $N$ . Pero sabemos que $r$ es el número más pequeño que no divide $N$ y $b \leq r$ por lo que debe ser el caso que $r = b$ . Así que desde $(b,n) = 1$ tenemos $(r,n) = 1$ . Por lo tanto, el orden de $n$ modulo $r$ existe.
Lo único que queda por demostrar es que $o_r(n) > \log^2{n}$ . Esto, afortunadamente, es casi trivial. Supongamos por contradicción que $o_r(n) = d \leq \log^2{n}$ . Entonces, por definición, $n^d \equiv 1$ mod $r$ , lo que implica $n^d -1 \equiv 0$ mod $r$ y así $r | (n^d -1)$ para un valor de $d$ que es menor o igual que $\log^2{n}$ . Pero entonces $r$ dividiría uno de los factores dentro del producto de $N$ y sabemos que $r$ no divide $N$ . Por lo tanto, $o_r(n) > \log^2{n}$ .
