From [SMOOTH NUMBERS: COMPUTATIONAL NUMBER THEORY AND BEYOND Andrew Granville pp.13-14](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.5030&rep=rep1&type=pdf):


> **2j. Lenstra’s polynomial time test as to whether an integer that is conjecturally prime, is rigorously squarefree.**
> If $n > 32$ ... (note that if the Generalized Riemann Hypothesis (GRH) holds and $a^{n-1} \equiv 1 \pmod{n}$ for all $a < 2 \log^2{n}$ $(*)$ then $n$ is indeed prime).

Searching the web for about 20 minutes couldn't find reference for this.

>Q1 What is a reference for this claim?

Alleged counter example:

Let $k=9981$ and $n=(6k+1)(12k+1)(18k+1)=1288666276813009$.

$n$ has only three prime factors coming from the closed form
form and according to [Wikipedia](https://en.wikipedia.org/wiki/Carmichael_number#Discovery) it is Carmichael number. By the definition, the
smallest $a$ s.t. $a^{n-1} \ne 1 \pmod{n}$ is $6k+1$, which is larger
than the RHS of $(*)$.


Pari session:


    ? k=9981;n=(6*k+1)*(12*k+1)*(18*k+1)
    %28 = 1288666276813009
    ? for(a=1,2*log(n)^2,b=Mod(a,n)^(n-1);if(b!=1,print(a)));
    ? \\nothing printed

> Q2 What is wrong with the alleged counterexample?

**Added**

Voters to close are recommended to read on meta [Is it frowned upon to answer a question and vote to close?](https://meta.mathoverflow.net/questions/1700/is-it-frowned-upon-to-answer-a-question-and-vote-to-close)