The Fermat Test base $a$ checks for a number $n$ whether or not $(a,n) = 1$ and $a^{n-1} \equiv 1 \pmod n$.
If for some base $a$, $n$ does not pass this test then we know $n$ is composite. But, realistically, how many values of $a\geq 2$ do we need to test?
Clearly, due to checking for the greatest common divisor we never need $\sqrt n < a$ but can we decrease this bound? Is there a worst case scenario where a composite number only fails the test for $a = \lfloor\sqrt{n}\rfloor$?