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

Question

This came up while answering a question on the period of the decimal expansion of $1/p$. The critical factor was whether the period (aka the order of $10$ mod $p$) is even or odd, equivalently whether $-1$ is a power of $10$ mod $p$.

It’s easy to see that for some congruence classes of primes, the order is always even: if $(10/p) = -1$, then we explicitly have $10^{(p-1)/2} \equiv -1 \pmod p$. In the other direction, if $(10/p) = +1$ but $(-1/p) =-1$, then clearly $-1$ cannot be a power of $10$.

This leaves only the case $(10/p) = (-1/p) = +1$, which amounts to 4 congruence classes mod $40$ where the parity is not trivially determined as above. In 3 of those congruence classes, it was very straightforward to find primes whose parity is even and odd. But for $9 \pmod{40}$, I only found even parities, at least for the first dozen primes.

Is there a reason for this phenomenon? I know next to nothing about biquadratic reciprocity, but it surprises me if something can be said beyond quadratic reciprocity with purely modular constraints (as opposed to quadratic or higher polynomials). Is this a small number effect owing to the relatively high power of $2$ dividing $p-1$? Did I just make a simple miscalculation somewhere?

Answer 1

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.

Answer 2

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$.