# Solving equations of form $3^n - 1 \bmod{k} = 0$, $k$ prime

In particular, I've used python to brute-force results of $3^n-1\bmod{7} = 0$ but was hoping there is a more elegant method.

-
Do you notice a pattern in the solutions $n$? – TMM Oct 6 '12 at 17:05
@TMM yes, they were multiples of 6. However, I didn't know if there was a theoretical basis for the phenomenon. – maxerize Oct 6 '12 at 20:38

When $p\neq 3$, Fermat's little theorem gives:

$$3^{p-1}-1\equiv 0\pmod{p}$$

Thus $n=p-1$ is a solution. It follows that all multiples of $p-1$ are also solutions. Clearly for $p=3$ the only solution is $n=1$.

-

You know from Fermat’s little theorem that $3^{p-1}\bmod p=1$ if $p$ is a prime greater than $3$. There may be smaller solutions: $3^5\bmod 11=1$, for instance. However, they must divide $p-1$, so there’s only a limited number to try. Once you find the minimum solution $m$, you have all solutions: they’re the positive integer multiples of $m$.

-
Out of interest, is there any constraint one can apply to the possible smaller solutions (to avoid trial and error)? – user39572 Oct 6 '12 at 17:24
@J.G.: I don’t know of one. – Brian M. Scott Oct 6 '12 at 17:25
@j.g.:no; it's the "discrete logarithm"-problem. What you can do to reduce the trial-and-error effort is to factorize $p-1$ because the "cycle-length" must be a divisor of $p-1$ But as far as I know you can't do less... – Gottfried Helms Oct 6 '12 at 17:28
@GottfriedHelms Thanks for the info. – user39572 Oct 6 '12 at 17:29
@J.G. As far as I know the question of when $3$ is a primitive root modulo $p$ is open. Any method which would tell you which is the smallest such $n$ would be a stronger result than the question of primitive roots.... – N. S. Oct 6 '12 at 19:13

For the state-of-the-art on the order computation problem see Andrew Sutherland's 2007 MIT Thesis Order Computations in Generic Groups. Below is an excerpt from p. 14.

-