ABSTRACT
Pratt showed in [41] that prime is in NPHco-NP. The difficult part is to show that prime e NP. He used Fermat’s Little Theorem and the cyclicity of F*. Miller proved in [30] that under an Extended Riemann Hypothesis, prime is in P. The connection to /Ao 4-fii is the following: Buss in [8] isolated a natural subsystem Sj of / Ao + fii and showed that any predicate provably in NP n co-NP over S\ is in fact in P. This is the motivation for studying Fermat’s Little Theorem over / Ao + Q i.
