It is not equivalent to ## 2^{p-1} - 1 ≡ 0\ (mod\ p) ##. That is just Fermat's Little Theorem with a=2. It is true for primes and base-2 pseudoprimes, of which there are almost 119 million below ## 2^{64} ##. AKS is a deterministic test for all input sizes, meaning there are no pseudoprimes...