Euler proved that if $n$ is prime, $a^{\frac{n-1}{2}}\equiv \genfrac{(}{)}{}{}{a}{n}\pmod{n}$, which for primes is $1$ if $a$ is a quadratic residue mod $n$, $-1$ if $a$ is a non-quadratic residue mod n, and $0$ if $a\equiv 0\pmod{n}$. In fact, half of all bases a < n will be quadratic residues, and half will be non-quadratic.
When $\frac{n-1}{2}$ is odd (implying $n\equiv 3\pmod{4}$), this means $(-a)^{\frac{n-1}{2}}\equiv -a^{\frac{n-1}{2}}\pmod{n}$, so first half of bases $a$ will be the complement of the second half of bases $a$ mod $n$. If $\frac{n-1}{2}$ is instead even, the second half will be equal to the first half, reversed. The fermat primality test uses the fact that $a^{(n-1)}\equiv 1\pmod{n}$ for all $a$ not congruent to $0$ mod $n$, which implies these values should all be square roots of 1 mod $n$.
(Edit per comments) $1$ cannot have square roots mod $n$ which are not $1$ or $-1$ when $n$ is prime. However, if $n$ is composite and $gcd(totient(n),\frac{n-1}{2}) = 1$, except for the trivial case of $(-1)^k\equiv -1\pmod{n}$ for odd $k$, no base $a$ will satisfy $a^{\frac{n-1}{2}}\equiv -1 $ or $ 1\pmod{n}$ when $n\equiv 3\pmod{4}$. If any value is $1$, then its complement is $-1$, implying $n$ is prime. If the value isn't $1$ or $-1$, the number is composite.
This produces the primality test (only when $gcd(totient(n),\frac{n-1}{2}) = 1$, which implies $n\equiv 3\pmod{4}$):
- Choose any base $1 < a < n - 1$ ($2$ is the simplest) and compute $r = a^{\frac{n-1}{2}} \pmod n$
- If $r\equiv -1 $ or $ 1\pmod{n}$, then $n$ is prime.
- Otherwise, $n$ is composite.
In most cases, calculating $totient(n)$ to make use of this test is as hard as factoring which is more difficult than testing for primality in the first place. But certain number forms guarantee the condition, for instance $2p+1$ (and likely $2pq+1$, where $p$ and $q$ are sequential primes). In general, if $n = 2x+1$ and we can guarantee $gcd(totient(n), x) = 1$, this is a very fast way to determine if $n$ is prime or composite. This can also be achieved with a modified prime number sieve which also removes modulus where $p-1$ would divide $n-1$ (I do not yet have estimates on precisely what range of values of $n$ the condition would hold for given a set of primes this was applied to).
Edit: The post originally made the assumption this was true when $n\equiv3\pmod{4}$ generally, and has now been edited to use the more complete condition that $gcd(totient(n), (n-1)/2) = 1$.