<s>[INST] Is $n = k \cdot p^2 + 1$ necessarily prime if $2^k \not\equiv 1 \pmod{n}$ and $2^{n-1} \equiv 1 \pmod{n}$? $p$ is an odd prime and $k$ is a positive integer.
Let $n=k \cdot p^2+1$. 
If $2^k \not\equiv 1 \pmod n$ and $2^{n-1} \equiv 1 \pmod n$, is $n$ prime? If it is, why?
 [/INST] Not necessarily.  Let $p = 3$ and $k = 154$.  Then $n = 3^2 * 154 + 1 = 1387$, $2^{154} \equiv 1024 \not\equiv 1 \pmod{1387}$, and $2^{1386} \equiv 1 \pmod{1387}$.  But $n = 1387 = 19 * 73$ is not prime.
</s>