A Generalization of Carmichael Numbers

Question

Obviously, from Fermat's Little Theorem, the condition of $p$ being prime is equivalent to there being some number $a$ of multiplicative order $p-1$ mod $p$. Moreover, this is equivalent to saying that, for every proper factor $k$ of $p-1$, the value $a^k\not\equiv 1\pmod{p}$ but that $a^{p-1}\equiv 1 \pmod{p}$. However, the similar statement that $a^{p-1}\equiv 1 \pmod{p}$ for any coprime $a$ to $p$ does not establish primality - the composite numbers satisfying that being called Carmichael numbers.

Noting that $p-1$ is always even for $p>2$, it follows that $\frac{p-1}{2}$ is always a factor of $p-1$. It follows from the fact that the multiplicative group mod a prime is cyclic that there it must be that, for a prime $p$, there exists exactly $\frac{1}2(p-1)$ values $a$ such that $$a^{\frac{1}2(p-1)}\equiv -1\pmod{p}.$$ Are there any odd composite $p$ that have the same property of having $\frac{1}2(p-1)$ solutions to the above? Are the infinitely many such $p$?

Answer 1

Suppose that your condition holds, and let $a$ be any solution to $T^{\frac{p-1}{2}} \equiv -1 \pmod{p}$.

Then $x\mapsto ax$ gives a bijection between the solutions to $T^{\frac{p-1}{2}} \equiv -1 \pmod{p}$ and the solutions to $T^{\frac{p-1}{2}} \equiv 1 \pmod{p}$.

But then there are at least $\frac{p-1}{2} + \frac{p-1}{2} = p-1$ invertible elements in $\mathbb{Z}/p$, in other words $p$ is prime.

Answer 2

It is not difficult to find "some" $a$. For primes there are $(p-1)/2$ such $a$, see Euler's criterion. For Carmichael numbers $n$, we have that $a^{n-1}\equiv 1$ for all $a$ coprime to $p$.
Suppose that $p$ is a composite number such that there exists an $a$ with $a^{p-1}\equiv 1\mod p$, but $a^{\frac{p-1}{2}}\not\equiv 1 \mod p$. Then we have $$ (a^{\frac{p-1}{2}}+1)(a^{\frac{p-1}{2}}-1)=a^{p-1}-1\equiv 0 \mod p. $$ This means, we have $a^{\frac{p-1}{2}}\equiv -1 \mod p$, and we are done.

Edit: Regarding the new question, this is discussed in the article Euler-Jacobi pseudoprime.