Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Do you notice a pattern in the solutions $n$? – TMM Oct 6 '12 at 17:05
up vote 2 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
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.

enter image description here
enter image description here

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.