2
$\begingroup$

I'm asked the following question: Prove that $b$ is a primitive root modulo $p \implies$ the smallest positive exponent $e$ such that $b^e \equiv 1 \pmod p$ is $p - 1$.

I know that this could probably be shown easily with Fermat's Little Theorem, but it's posed to the reader before Fermat's Little Theorem is even discussed.

How should I approach this problem? Is there a simple argument for why this is true that doesn't require quite as much ingenuity as the proofs of Fermat's Little Theorem? (i.e., the ones that involve $(p-1)!$ or group theory)

$\endgroup$
  • 1
    $\begingroup$ Isn't that the definition of a primitive root? How is primitive root defined? $\endgroup$ – user44197 Feb 19 '14 at 3:13
  • $\begingroup$ A primitive root modulo $p$ is an integer b such that $\{0 \mod p, b \mod p, b^2 \mod p, ..., b^{p-1} \mod p\} = \{0, 1, 2, ..., p - 1\}$ $\endgroup$ – Trent Bing Feb 19 '14 at 3:21
1
$\begingroup$

In that case, look at all the powers of $b$, i.e. $b, b^2, b^3 \cdots$ modulo $p$ If $b^e\equiv 1 \mod p$, then the pattern repeats after $b^e$, i.e you get the same $e$ terms. So the totality of all numbers you can generate is $e+1$. But for a primitive root, you generate $p$ terms. So, $e=p-1$.

By the way the same holds for non-primes also. You just replace the condition by $e=\phi(p)$ using the same logic.

$\endgroup$
  • $\begingroup$ "If $b^e \equiv 1 \mod p$, then the pattern repeats after $b^e$" how do you show this? I definitely get what you're saying aside from that. $\endgroup$ – Trent Bing Feb 19 '14 at 3:32
1
$\begingroup$

If you regard a primitive root module $p$ as being a number $b$ that, when raised to a suitable power, can achieve equivalence with any number coprime to $p$, then the argument can go as follows:

By the definition above, there must be a value $s$ such that $b^s \equiv 1 \bmod p$, which we'll take as the smallest such positive value. However this means that $b^{s+k} \equiv b^k \bmod p$, so $b$ can achieve at most $s$ different equivalences. Since our definition of $b$ requires that powers of $b$ are equivalent to each non-zero residue class of $p$, $s$ must be at least $(p-1)$.

If two positive powers of $b$ less than $p-1$ are in the same equivalence class, say $p-1>d>c$ and $b^c \equiv b^d$, then we would have $b^{d-c}\equiv 1$ and this is not allowed by the previous argument on the definition of $b$. So all $b^k$, $0<k\le s$, are in different equivalence classes, and $s= p-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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