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)



What is wrong with this counterexample to primality test assuming GRH?
This is a revised version of my original answer. I fixed some inconsistencies and made the text more readable.


The correct statement is given by the deterministic Miller-Rabin test coupled with an estimate of Bach under GRH. Let us follow Sections 10.2 and 10.5 of [Shoup: A computational introduction to number theory and algebra (version 2)](http://shoup.net/ntb/). Let $n$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Consider


$$ L\_n':=\left\{a\in\mathbb{Z}\_n^\times:\ a^{2^s t}=1\quad\text{and}\quad a^{2^{r+1}t}=1\Longrightarrow a^{2^rt}=\pm 1\quad\text{for}\quad 0\leq r<s \right\} $$


For $n$ prime, $L\_n'$ equals $\mathbb{Z}\_n^\times$. For $n$ composite, the proof of Theorem 10.3 in [Shoup's book](http://shoup.net/ntb/) shows that $L\_n'$ generates a proper subgroup of $\mathbb{Z}\_n^\times$. Combining these statements with Theorem 2 of [Bach](http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023756-8/S0025-5718-1990-1023756-8.pdf), we get:


**Theorem 1.** Assume GRH. Let $n$ be an odd integer. Then $n$ is composite if and only if there is $1<b<2\log^2 n$ such that $b$ mod $n$ lies outside $L\_n'$.


Using Theorem 1.1 of [Lamzouri-Li-Soundararajan](http://arxiv.org/abs/1309.3595) in place of Bach's result, we get the following stronger version:


**Theorem 2.** Assume GRH. Let $n>3000$ be an odd integer. Then $n$ is composite if and only if there is $1<b<\log^2 n$ such that either $b\mid n$, or $b$ mod $n$ lies outside $L\_n'$.


**Added.** The OP wanted more specific answers to his questions Q1 and Q2. Here they are:


Q1: The quoted paragraph without the parentheses gives a complete proof for the square-free test, so Granville's paper can be taken as a reference (although I am sure Lenstra wrote this down earlier in some form). The part in parentheses is false, so there is no reference for it. A corrected version for this part is given above, and a reference for it is [Shoup's book](http://shoup.net/ntb/).


Q2: There is nothing wrong with the quoted counterexample. It is a genuine counterexample to the part in parentheses, which shows in particular that the part in parentheses is false.


