# On proof of AKS primality test algorithm

Just studying the paper PRIMES is in P, although I've tried great efforts, some proofs are still not so clear(or obvious) to me, especially the proof of Lemma 4.3. The problem is by choosing r the smallest number that does not divide the product $n^{\lfloor logB \rfloor}\prod_{i=1}^{\lfloor log^2n\rfloor}{(n^i-1)}$, why the fact $(r, n)$ cannot be divisible by all the prime divisors of r holds? And why if violated, r will divide $n^{\lfloor logB \rfloor}$? Any relation with the observation "the largest value of $k$ for any number of the form $m^k \leq B$ , for $m > 2$ is $\lfloor logB \rfloor$"? And finally, the conclude of this proof, I cannot find trivial relation between $r$ and $B$, any theorem or fact I miss?

Thanks and Best Regards!

EDIT:

Follow Will's advice below, I found the article linked above is a draft and referred to the published version. Much more clear indeed! However, there is still one point I'm not sure:

At nearly the end of proof to lemma 4.3, the authors say "If $(s,n)>1$, then since $s$ does not divide $n$ and $(s,n)\in {r_1,r_2,…,r_t }$" then "$r=\frac{s}{(s,n)}\not\in {r_1,r_2,…,r_t }$". Where $r_i$ is defined as numbers either $o_r(n)\leq \log^{2} n$(which is the bound we want to approach, I think) or $r_i$ divides $n$ and $s$ is a number $\leq \lceil \log^{5}n\rceil$ such that $s\neq r_i$(previous lemma shows we can always find such an $s$ under the hypothesis). Why there is no pobability $o_r(n)\leq \log^{2}n$? In which case, seems no assumptions are voilated.

Thank you!

-
Dear readers: In case you don't notice, there's a link to the PDF paper if you hover over  PRIMES is in P! – user2468 Mar 13 '12 at 4:58
read terry taos blog on it, he makes it really simple – user58512 Jan 22 '13 at 21:14

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.