Primitive roots of twice the powers of odd primes

In a previous post, we show that there exist primitive roots modulo the power of an odd prime number (see Primitive roots of powers of odd primes). In this post we show that there exist primitive roots modulo two times the power of an odd prime number. Specifically we prove the following theorem.

    Theorem 1

      Let p be an odd prime number. Let j be any positive integer. Then there exist primitive roots modulo p^j.

We make use of the Chinese Remainder Theorem (CRT) in proving Theorem 1. We use the following version of CRT (also found in this post)

    Theorem 2 (CRT)

      Let m and n be positive integers that are relatively prime. Then a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n) if and only if a \equiv b \ (\text{mod} \ mn).

Proof of Theorem 2
\Longrightarrow
Suppose a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n). Converting these into equations, we have a=b+mx and a=b+ny for some integers x and y. It follows that mx=ny. This implies that m \ \lvert \ ny. Since m and n and relatively prime, m \ \lvert \ y and y=mt for some integer t. Now the equation a=b+ny can be written as a=b+mnt, which implies that a \equiv b \ (\text{mod} \ mn).

\Longleftarrow
Suppose a \equiv b \ (\text{mod} \ mn). Then a=b+mns for some integer s, which implies both congruences a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n). \blacksquare

Proof of Theorem 1
Let a be a primitive root modulo p^j (shown to exist in the post Primitive roots of powers of odd primes). When a is odd, we show that a is a primitive root modulo 2p^j. When a is even, we show that a+p^j is a primitive root modulo 2p^j.

First the odd case. Since a is a primitive root modulo p^j, a^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j). Since a is odd, a^k is odd for all integers k \ge 1. So a^k \equiv 1 \ (\text{mod} \ 2) for all integers k \ge 1. By CRT (Theorem 2), a^k \not \equiv 1 \ (\text{mod} \ 2p^j) for all positive k<\phi(p^j)=\phi(2 p^j). This implies that a is a primitive root modulo 2p^j.

Now the even case. Note that a+p^j is odd (even + odd is odd). It is also the case that (a+p^j)^k is odd for all k \ge 1. Thus (a+p^j)^k \equiv 1 \ (\text{mod} \ 2) for all k \ge 1.

In expanding (a+p^j)^k using the binomial theorem, all terms except the first term a^k is divisible by p^j. So (a+p^j)^k \equiv a^k \ (\text{mod} \ p^j). Furthermore, a^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j) since a is a primitive root modulo p^j. So (a+p^j)^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j).

By CRT (Theorem 2), we have (a+p^j)^k \not \equiv 1 \ (\text{mod} \ 2p^j) for all positive k<\phi(p^j)=\phi(2p^j). This implies that a+p^j is a primitive root modulo 2p^j. \blacksquare

The remainder of the proof of the primitive root theorem is found in The primitive root theorem.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

One thought on “Primitive roots of twice the powers of odd primes

  1. Pingback: The primitive root theorem revisited | Exploring Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s