Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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|improve this question
1  
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

3 Answers

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|improve this answer
up vote 1 down vote

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|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
1  
@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
up vote 0 down vote

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|improve this answer

Your Answer

 
discard

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.