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$
2
  • 1
    $\begingroup$ Isn't that the definition of a primitive root? How is primitive root defined? $\endgroup$
    – user44197
    Commented Feb 19, 2014 at 3:13
  • 1
    $\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$
    – Brandon
    Commented Feb 19, 2014 at 3:21

2 Answers 2

2
$\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$
1
  • $\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$
    – Brandon
    Commented Feb 19, 2014 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .