I'm reading the AKS primality test paper as it is found here. I'm confused about a statement in Lemma 4.3:

"Note that $(r, n)$ cannot be divisible by all the prime divisors of $r$ since otherwise $r$ will divide $n^{\left \lfloor{log(B)}\right \rfloor}$ by the observation above."

Here $(r, n)$ is short-hand for $gcd(r, n)$ (I think) and the observation referred to is "the largest value of k for any number of the form $m^k ≤ B = \left \lceil{log^5(n)}\right \rceil$, $m ≥ 2$, is $\left \lfloor{log(B)}\right \rfloor$".

How does the observation above imply that $(r, n)$ cannot be divisible by all prime divisors of $r$?

The furthest I can get to understanding this is follows:

Let $s= \prod_{p\in PRIMES, p | r}p$.

Assume $s | (r,n) \Rightarrow s | n $. Let $k$ be the highest exponent in the product-of-primes representation of $r$. Then $r| s^k$. But then $r|s^k|n^k$. But if we've defined $r$ such that $r \nmid n^k$ then we must conclude that our initial assumption, $s|(r,n)$, was wrong. This logic makes sense.

But the paper is claiming this $k$ is at most $\left \lfloor{log(B)}\right \rfloor$. I get if $r \leq B$, then the highest exponent in the product of primes representation of r is less that $\log(r)$, and therefore is less than $\log(B)$. But we cannot assume $r \leq B$ as that is one of the things the lemma is trying to prove.

Am I missing something?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.