Berkeley Math Circle: Monthly Contest 6

Solution:
The answer is $p = 179$. To see this works, take $a = 4$; by Fermat's little theorem, $4^{89} - 1 = 2^{178} - 1$ is divisible by $179$.

Now suppose $a^{89} \equiv 1 \pmod{p}$. We consider two cases:
- If $a \equiv 1 \pmod{p}$, then
$$0 \equiv 1 + a + \cdots + a^{88} \equiv 89 \pmod{p}$$
which forces $p = 89$.
- Otherwise, since $89$ is prime, it follows $a$ has order $89$ modulo $p$. So $89 \mid p - 1$. The smallest prime which obeys this is $p = 179$.