<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] I'm able to find a proof of the $k=2$ case, which is the first non-trivial case.
Result:  Let $p$ be an odd prime and $n=2p^2+1$ such that $2^{n-1} \equiv 1 \pmod n$.  Then $n$ is prime.
This proof splits into four steps:


*

*We will prove that if $p$ divides $\varphi(n)$, then $n$ is prime.

*We will prove that if $2^{2p} \equiv 1 \pmod n$, then $p$ divides $\varphi(n)$.

*We will prove that if $2^{p^2} \equiv 1 \pmod n$, then $p$ divides $\varphi(n)$.

*The Lucas primality test implies that if $2^{2p} \not\equiv 1 \pmod n$ and $2^{p^2} \not\equiv 1 \pmod n$, then $n$ is prime.


Lemma: Let $p$ be a prime and $n=2p^2+1$.  If $p$ divides $\varphi(n)$, then $n$ is prime.
Proof:  Since $\varphi(n)$ is multiplicative and $p$ is prime, $p$ divides $\varphi(q^t)$ for some prime power divisor $q^t$ of $n$.  Since $\varphi(q^t)=q^{t-1}(q-1)$, and $q$ divides $n$ while $p$ does not divide $n$, we must have that $p$ divides $q-1$.
Since $q$ divides $n$, we know $n=bq$ for some $b \geq 1$.  Since $p$ divides $q-1$, we know $q=cp+1$ for some $c \geq 1$.
Hence $$n=b(cp+1)=bcp+b$$ and from before $$n=2p^2+1.$$  By taking these equations modulo $p$, we must have that $b \equiv 1 \pmod p$.
Case I: $b \geq 2p+1$.  Then $n=bcp+b>2p^2+1$, giving a contradiction.
Case II: $b=p+1$.  Then $n=cp(p+1)+p+1=cp^2+2cp+1$.  Since $n$ is odd, we must have that $c$ is even, and thus $n>2p^2+1$, giving a contradiction.
Thus $b=1$, and hence $c=2p$, and hence $q=2p^2+1=n$.  Hence $n$ is prime (since $q$ is a prime divisor of $n$).  End proof.


*

*Now assume $2^{2p} \equiv 1 \pmod n$.  Then $4^p \equiv 1 \pmod n$.  Since $\gcd(4,n)=1$, we know $4$ is a member of the group $(\mathbb{Z}_n)^{\times}$.  Hence the order of $4$, which we will denote $o_4$, divides $|(\mathbb{Z}_n)^{\times}|=\varphi(n)$.  However, since $4^p \equiv 1 \pmod n$, we know that $o_4$ divides $p$.  But since $n \geq 19$, we know that $o_4>1$, so $o_4=p$.  Hence $p$ divides $\varphi(n)$.

*Now assume $2^{p^2} \equiv 1 \pmod n$.  Since $\gcd(2,n)=1$, we know $2 \in (\mathbb{Z}_n)^{\times}$.  Hence the order $o_2$ of $2$ divides $|(\mathbb{Z}_n)^{\times}|=\varphi(n)$.  However, since $2^{p^2} \equiv 1 \pmod n$, we know that $o_2$ divides $p^2$.  But since $n \geq 19$, we know that $o_2>1$, so $p$ divides $o_2$ (more specifically, we know $o_2 \in \{p,p^2\}$).  Hence $p$ divides $\varphi(n)$.
</s>