I have a question to the Pocklington-Lehmer criterion for primality testing which is commonly stated as follows:
Let $n\in\mathbb{N}$ s.t. $n-1=a\cdot b$ where $a>\sqrt{n}$ and $a,b$ are coprime. Then $n$ is prime iff for each prime divisor $p$ of $a$ there is some $a_p\in\mathbb{N}$ s.t. $a_p^{n-1}\equiv 1 (n)$ and $\mathrm{gcd}\left(a_p^{\frac{n-1}{p}}-1,n\right)=1$.
My question is: Why and where do we need that $a$ and $b$ are coprime?
I suggest the following proof (which is mostly the standard one, as e.g. on Wikipedia):
$\Rightarrow$: Take $a_p$ to be a primitive root mod $p$ and the claims are immediate.
$\Leftarrow$: Assume that the stated conditions hold and $n$ is not a prime. Then there is a prime divisor $q$ of $n$ that satisfies $q\leq\sqrt{n}$. Let $a=\prod_{p\in L} p^{e_p}$ where $L$ is a finite set of primes and $e_p>0$. Clearly (by Chinese Remainder), it suffices to prove that $q\equiv 1 (p^{e_p})$ for each $p\in L$. Let's show this: Let $a_p$ as in the stated condition and define $k$ to be the order of $a_p$ mod $q$. By Fermat we have $k|q-1$. On the other hand the stated conditions imply that $k|n-1$, but $pk\not| n-1$. Let $m_p>0$ be maximal s.t. $p^{m_p}|n-1$. We then get $e_p\leq m_p$ and $p^{m_p}|k|q-1$. Thus it follows that $p^{e_p}|p^{m_p}|k|q-1$ and the proof is complete.
Is there a mistake in this proof? Do we need that gcd($a,b$) is 1?
Thanks a lot in advance!