Let $p=40k+9$ be prime. Does $10$ always have even order mod $p$?

There are $2090$ primes $\equiv 9 \mod 40$ less than or equal $400009$. Of these, there are $323$ for which the order of $10$ is odd, the first being $1609$.


By brute force, $1/1609$ gives a repetend period of $201$.

We note that if the Euler totient function is a multiple of $2^k$ then $10$ has to be a $2^k$ power residue in order to make the repetend odd. Because $10$ is always a quadratic residue, this has probability $1/2^{k-1}$ where $k=3$ for half of the relevant primes, $k=4$ for one quarter, $k=5$ for one eighth, etc., giveng the total probability

$(1/4)(1/2)+(1/8)(1/4)+(1/16)(1/8)+...=\color{blue}{1/6}$

The number of primes you need to try in order to get a success is thus predicted to be exponentially distributed with mean $6$. The actual count is $18$, which had about a 5% chance of being that large given the predicted exponential distribution. The issue in finding a prime was one of simple probability rather anything more profound.

Another answer notes that with 2000+ primes almost exactly one-sixth of them are successes. Thus with enough statistical data we get what we should have expected all along.