On proof of AKS primality test algorithm

Solution 1:

Actually, the first paper (version 6) you read is the more recent version; the annals of mathematics version was published first and contains an mistake in Lemma 4.3 (there's an acknowledgment in the version 6 paper noting the error). The problem is with the last line of the proof, which is exactly where you got stuck.

Mistake in Lemma 4.3 of AKS (Annals of Math version)

Given that $s \not \in \{r_1,\ r_2,\ ...,\ r_t\}$ and $(s,n) > 1$, it is not necessarily true that $\frac{s}{(s,n)} \not \in \{r_1,\ r_2,\ ...,\ r_t\}$. Consider the following:

Since $s \not \in \{r_1,\ r_2,\ ...,\ r_t\}$, we know that $s$ doesn't divide $n$, and either $o_s(n) > \log_2^2(n)$ or $o_s(n)$ doesn't exist. If $(s,n) > 1$, then $o_s(n)$ doesn't exist, but that doesn't imply that the order of $n$ modulo $\frac{s}{(s,n)}$ is greater than $\log_2^2(n)$.

Suppose $n = 8$. Then 6 is the first number we encounter that is not in $\{r_1,\ r_2,\ ...,\ r_t\}$, because $o_6(8)$ doesn't exist, and 6 doesn't divide 8. However, $\frac{6}{(6,8)} = \frac{6}{2} = 3$, and $3 \in \{r_1,\ r_2,\ ...,\ r_t\}$, because $o_3(8) = 2$, and $2 \leq \log_2^2(8) = 9$.

My proof of Lemma 4.3

It turns out that the $n^{\lfloor\log(B)\rfloor}$ introduced in the newer version of the paper is necessary to address this kind of counterexample. I also found the version 6 proof rather difficult to understand; a lot of steps were left out. So below is an expanded proof I wrote myself! Hopefully it is more clear; let me know if anything doesn't make sense :) It breaks the proof down into three steps: finding a small enough $r$, proving that $o_r(n)$ exists, and finally showing that $o_r(n) > \log^2{n}$.

Claim: There exists an $r \leq$ max$\{3,\lceil\log^5{n}\rceil\}$ such that $o_r(n) > \log^2{n}$.

Proof: We know $n>1$. If $n=2$, we can let $r=3$, and since $2^2 = 4 \equiv 1 \text{ mod } 3$, $o_3(2) = 2$, while $\log^2{2} = 1$, so the statement holds. From here on, assume $n>2$. Note that $\lceil \log^5 3 \rceil = 11$, and since the logarithm function is monotonically increasing, we know that $\lceil \log^5 n \rceil > 10$ for all $n>2$. Let $B = \lceil \log^5 n \rceil$. Applying lemma 3.1, we have that $LCM(B) \geq 2^{B}$. First we will prove that there exists a number $r\leq B$ that doesn't divide the product $$N=n^{\lfloor\log{B}\rfloor} \cdot \displaystyle\prod_{i=1}^{\lfloor\log^2(n)\rfloor}(n^i-1)$$ Suppose, by contradiction, that for all $1\leq r \leq B$, $r$ divides $N$. Then clearly $LCM(B) \leq N$, because $N$ itself is a common multiple of all numbers less than or equal to $B$. Notice that \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*} Therefore $N < 2^{B}$. Recall that $LCM(B) \geq 2^{B}$, so we have $LCM(B) > N$. However, we saw above that $LCM(B) \leq N$; a contradiction. Therefore the set of numbers between 1 and $B$ that do not divide $N$ is non-empty; let $r$ be the smallest element of this set.

We've found an $r\leq B$; now we need to prove that $o_r(n)$ exists, and that $o_r(n) > \log^2{n}$. Recall that the order of $n$ modulo $r$ only exists if $(r,n) = 1$. We shall prove that this is the case. Write $r=ab$, where the prime factors of $a$ are precisely the prime factors of $r$ which divide $n$, and $b$ is made up of the remaining prime factors. Clearly $(b,n) = 1$, since $n$ and $b$ have no common prime factors. Notice that the highest power any prime could be raised to in the prime factorization of $a$ is $\lfloor \log{B}\rfloor$, since otherwise $a \leq r$ would be greater than $B$ (this is from the observation that "the largest value of $k$ for any number of the form $m^k \leq B$ , for $m\geq2$ is $\lfloor \log{B}\rfloor$" from the AKS paper). Therefore, every prime factor in $a$ is raised to a smaller exponent than the same factor in $n^{\lfloor\log{B}\rfloor}$, and since every prime factor of $a$ is present in $n$, it must be the case that $a$ divides $n^{\lfloor\log{B}\rfloor}$. It follows that $b$ does not divide $\displaystyle\prod_{i=1}^{\lfloor\log^2(n)\rfloor}(n^i-1)$, because if it did, then $r = ab$ would divide $N$, and we chose $r$ such that this isn't the case. However, it is also true that $b$ does not divide $n^{\lfloor\log{B}\rfloor}$, since $(b,n) = 1$. Therefore $b$ doesn't divide $N$. But we know $r$ is the smallest number that doesn't divide $N$ and $b \leq r$, so it must be the case that $r = b$. So since $(b,n) = 1$, we have $(r,n) = 1$. Therefore, the order of $n$ modulo $r$ exists.

All that remains to be shown is that $o_r(n) > \log^2{n}$. This, fortunately, is almost trivial. Suppose by contradiction that $o_r(n) = d \leq \log^2{n}$. Then by definition, $n^d \equiv 1$ mod $r$, which implies $n^d -1 \equiv 0$ mod $r$, and so $r | (n^d -1)$, for a value of $d$ which is less than or equal to $\log^2{n}$. But then $r$ would divide one of the factors within the product of $N$, and we know that $r$ does not divide $N$. Therefore, $o_r(n) > \log^2{n}$.

Solution 2:

I can't make any sense of that section, it appears if you assume $r < B$ then other things follow and then $r < B,$ so seemingly circular, but in any case clumsy.

Otherwise, Andrew Granville did the whole thing over, see GRANVILLE. On page 20, Lemma 4.4, he switches to prime $r$ such that $(\log n)^5 < r < 2 (\log n)^5,$ where $\log$ always means logarithm base $2.$ Note that the fact that there is at least one prime between those bounds is Bertrand's Postulate, first proved by Chebyshev and later, in elementary fashion, by Erdos.