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.
Solving congruences like $3^p\equiv 1\pmod{\! p}$, $p$ prime [order computation]
2
$\begingroup$
elementary-number-theory
prime-numbers
-
1Do you notice a pattern in the solutions $n$? – 2012-10-06
3 Answers
1
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$.
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$.
-
0@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.... – 2012-10-06
0
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.