# What is the least solution to $2^n \equiv 1 \pmod k$ for a given (odd) $k$?

I came across this problem in a Numberphile video regarding perfect shuffles.

First up, there are no solutions for even $k$. This is made clear from the division algorithm; there are unique $r,s$ such that $2^n = sk + r$ with $r<k$. If $k$ is even, since $2^n$ is even, then clearly $r$ must be even so it cannot be $1$.

Now for odd $k$, there is a set of solutions given by Fermat's little theorem, since $2^{(p-1)}\equiv 1 \pmod p$ for all odd primes. So if $p$ is prime, $p-1$ is a solution but not necessarily the least solution, since e.g. $2^{11}\equiv 1 \pmod {23}$ as is easily checked. I didn't see a relation with the remainder modulo 4, since $19\equiv 23\equiv 3 \pmod 4$ but the least solution for $k=19$ is $n=18$.

Here's a few visualizations of the solutions up to $k<200$, $k<20000$, and $k<200000$. It's interesting that the solutions tend to form in several lines, mainly of slopes $1$ and $1/2$. I couldn't prove, for primes, conditions for the existence of solutions less than $p-1$.

• I had done something similar for $10^n \equiv 1 \mod k$, and let me tell you, other than the fact that there were regularities in the form of lines of slope $1$ and $\frac{1}{2}$, I found no conclusive pattern of anything emerging. I too worked on existence of smaller solutions, but you see, it's like this: If $10^{k-1} \equiv 1 \mod k$, then $k | (10^{k-1/2} -1)(10^{k-1/2}+1)$, so $k$ either divides one of these numbers, or has non-zero gcd with both numbers. If it comes down to a problem like this, I thought it possibly won't have a very clean solution. Quite random, from my side. – астон вілла олоф мэллбэрг Aug 11 '16 at 0:16
• No good answer is know even for the base case of prime $k$, I believe. All you know is that $n$ will be a divisor of $p-1$. – Thomas Andrews Aug 11 '16 at 0:18