Can someone prove or disprove the conjecture below? Thanks. Much appreciated.
Show that if $2^n$ $=$ $1$ $\pmod p$ ($n$ prime) with $p$ $=$ $1$ $\pmod n$ and $3^{p-1}$ $=$ $1$ $\pmod p$, $p$ $≠$ $±1$ $\pmod {12}$, then $p$ is prime. A more general conjecture to prove:
If
$b^n$ $=$ $1$ $\pmod p$ ($n$ prime) with $p$ $=$ $1$ $\pmod n$ and $b-1$ relatively prime to $n$ and $p$.
$a^{p-1}$ $=$ $1$ $\pmod p$ ($a-1$ relatively prime to $n$ and $p$) and ($a$ | $p$) $=$ $-1$ (the Legendre Symbol or that $a$ is a quadratic nonresidue modulo $p$)
then $p$ is prime.
My understanding for this conjecture (the specific example with $b$ $=$ $2$ and $a$ $=$ $3$) is that if $n$ is prime, every prime dividing $p$ $2^n-1$, $p$ $=$ $±1$ $\pmod 8$. Likewise in my last post, for base $3$ every prime $p$ dividing $3^n-1$ $=$ $±1$ $\pmod {12}$. When $n$ is prime, it must be the case that all primes dividing $p$ $=$ $1$ $\pmod n$. Therefore concluding that if $3^{p-1}$ $=$ $1$ $\pmod p$, and $p$ is composite, then $3^n$ $=$ $1$ $\pmod p$. By the law of quadratic reciprocity, we also would have all primes dividing $p$ congruent to $±1$ $\pmod {12}$. If $p$ $≠$ $±1$ $\pmod {12}$, then there is some prime dividing $p$ which is not $±1$ $\pmod {12}$. Therefore $3^n$ $≠$ $1$ $\pmod p$ and the multiplicative order of $p$ is not $n$ and is $p-1$ implying $p$ is prime.
Counterexample to the title of the question: $n=43$.