Return to Answer

The correct statement is given by the deterministic Miller-Rabin test coupled with an estimate of Bach under GRH.

Theorem. Assume GRH. Let $n$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<2\log^2 n$ such that $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.

For more details see Section V.1 in Koblitz: A course in number theory and cryptography (2nd edition, GTM 114, Springer, 1994).

Added 1. 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 Koblitz's book (or the original papers by Miller, Rabin, Bach).

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.

Added 2. A more complete exposition of this material can be found in Sections 10.2 and 10.5 of Shoup: A computational introduction to number theory and algebra (version 2).

Added 3. Using Theorem 1.1 of Lamzouri-Li-Soundararajan in place of Theorem 2 of Bach, we get the following stronger version of the above theorem.

Theorem. Assume GRH. Let $n>3000$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<\log^2 n$ such that either $b\mid n$, or $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.

Added 4. In deducing the above theorems it is good to have in mind the following supplement to Theorem 10.3 in Shoup's book: if $n$ is composite, then $L_n'$ generates a proper subgroup of $\mathbb{Z}_n^\times$. Indeed, this supplement follows by the proof of the quoted theorem.

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). 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 shows that $L_n'$ generates a proper subgroup of $\mathbb{Z}_n^\times$. Combining these statements with Theorem 2 of Bach, 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 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.

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.

The correct statement is given by the deterministic Miller-Rabin test coupled with an estimate of Bach under GRH.

Theorem. Assume GRH. Let $n$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<2\log^2 n$ such that $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.

For more details see Section V.1 in Koblitz: A course in number theory and cryptography (2nd edition, GTM 114, Springer, 1994).

Added 1. 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 Koblitz's book (or the original papers by Miller, Rabin, Bach).

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.

Added 2. A more complete exposition of this material can be found in Sections 10.2 and 10.5 of Shoup: A computational introduction to number theory and algebra (version 2).

Added 3. Using Theorem 1.1 of Lamzouri-Li-Soundararajan in place of Theorem 2 of Bach, we get the following stronger version of the above theorem.

Theorem. Assume GRH. Let $n>3000$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<\log^2 n$ such that either $b\mid n$ or $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.

The correct statement is given by the deterministic Miller-Rabin test coupled with an estimate of Bach under GRH.

Theorem. Assume GRH. Let $n$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<2\log^2 n$ such that $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.

For more details see Section V.1 in Koblitz: A course in number theory and cryptography (2nd edition, GTM 114, Springer, 1994).

Added 1. 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 Koblitz's book (or the original papers by Miller, Rabin, Bach).

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.

Added 2. A more complete exposition of this material can be found in Sections 10.2 and 10.5 of Shoup: A computational introduction to number theory and algebra (version 2).

Added 3. Using Theorem 1.1 of Lamzouri-Li-Soundararajan in place of Theorem 2 of Bach, we get the following stronger version of the above theorem.

Theorem. Assume GRH. Let $n>3000$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<\log^2 n$ such that either $b\mid n$, or $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.

Added 4. In deducing the above theorems it is good to have in mind the following supplement to Theorem 10.3 in Shoup's book: if $n$ is composite, then $L_n'$ generates a proper subgroup of $\mathbb{Z}_n^\times$. Indeed, this supplement follows by the proof of the quoted theorem.

The correct statement is given by the deterministic Miller-Rabin test coupled with an estimate of Bach under GRH.

Theorem. Assume GRH. Let $n$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<2\log^2 n$ coprime with $n$ such that $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.

For more details see Section V.1 in Koblitz: A course in number theory and cryptography (2nd edition, GTM 114, Springer, 1994).

Added 1. 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 Koblitz's book (or the original papers by Miller, Rabin, Bach).

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.

Added 2. A more complete exposition of this material can be found in Sections 10.2 and 10.5 of Shoup: A computational introduction to number theory and algebra (version 2).

The correct statement is given by the deterministic Miller-Rabin test coupled with an estimate of Bach under GRH.

Theorem. Assume GRH. Let $n$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<2\log^2 n$ such that $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.

For more details see Section V.1 in Koblitz: A course in number theory and cryptography (2nd edition, GTM 114, Springer, 1994).

Added 1. 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 Koblitz's book (or the original papers by Miller, Rabin, Bach).

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.

Added 2. A more complete exposition of this material can be found in Sections 10.2 and 10.5 of Shoup: A computational introduction to number theory and algebra (version 2).

Added 3. Using Theorem 1.1 of Lamzouri-Li-Soundararajan in place of Theorem 2 of Bach, we get the following stronger version of the above theorem.

Theorem. Assume GRH. Let $n>3000$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<\log^2 n$ such that either $b\mid n$ or $b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for all $0\leq r<s$.