2
$\begingroup$

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.

  • 1
    Do you notice a pattern in the solutions $n$?2012-10-06

3 Answers 3

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.

enter image description here
enter image description here