91Ó°ÊÓ

Euler's Totient Function, often denoted by \( \phi(n) \), is a key component when discussing primitive roots. It represents the count of integers up to \( n \) that are relatively prime to \( n \). Essentially, \( \phi(n) \) measures the number of integers that share no common divisors with \( n \) other than 1.

When \( n \) is a power of a prime, like \( 3^e \), the formula simplifies to \( \phi(3^e) = 3^e - 3^{e-1} = 2 \cdot 3^{e-1} \).

For example, if \( e = 1 \), then \( \phi(3) = 3 - 1 = 2 \), which tells us there are two numbers less than 3, namely 1 and 2, that are coprime with 3.

Understanding how to calculate \( \phi(n) \) allows us to identify the order of potential primitive roots, which is crucial in finding if a number like 2 can indeed be a primitive root modulo \( 3^e \).

Modulo arithmetic, often referred to as "clock arithmetic," deals with numbers wrapping around at some value \( n \). This is central to defining concepts such as primitive roots and understanding how numbers behave under modulo operations.

In our context, the expression \( g^k \equiv 1 \pmod{n} \) signifies that when \( g^k \) is divided by \( n \), the remainder is 1. Finding a primitive root involves determining the smallest \( k \) for which this condition holds.

For instance, if we're examining \( 2 \mod 3 \), when we compute powers of 2, we get:

• \( 2^1 = 2 \equiv 2 \pmod{3} \)
• \( 2^2 = 4 \equiv 1 \pmod{3} \)

As shown here, 2 is a primitive root modulo 3 because \( 2^2 \equiv 1 \pmod{3} \) and fits the Euler's Totient Function condition \( k = \phi(3) = 2 \).

Induction is a powerful mathematical technique often used to prove statements that are generalized across an infinite set, like proving a property for all positive integers \( e \).

To show that 2 is a primitive root mod \( 3^e \) for all \( e \geq 1 \), we first confirm the base case (\( e = 1 \)). We see that \( 2^2 \equiv 1 \pmod{3} \), satisfying the condition. This sets the stage to apply the inductive step.

Next, we assume that 2 is a primitive root mod \( 3^k \) and seek to prove it for \( 3^{k+1} \). By assuming that our claim holds for some integer \( k \), we demonstrate it also applies to \( k+1 \) by leveraging properties of prime powers and tools like the Lift The Exponent Lemma, maintaining the validity of the order of 2.

Inductive proof ensures that if 2 works as a primitive root for one instance, it continues to do so as \( e \) grows, relying on a clear logical progression from one step to the next.

The Lift The Exponent Lemma is a useful tool when dealing with congruences involving prime powers. It provides a mechanism to simplify complex exponent relationships, particularly when examining whether an integer is a primitive root modulo a higher power of a number.

In simpler terms, this lemma tells us that if \( 2^d \equiv 1 \pmod{3^{k+1}} \), it follows that \( 2^{d/3^{k}} \equiv 1 \pmod{3} \).

This condition means \( d \) must be a multiple of \( \phi(3^{k+1}) = 2 \cdot 3^k \). Thus, by confirming \( 2^{2 \cdot 3^{k}} \) returns 1 when divided by \( 3^{k+1} \), and no smaller \( d \) holds this property, we justify that the previous modulo relationship extends naturally, ensuring full coverage over all relevant powers of 3.

Understanding this lemma grants clarity in proving that 2 remains a consistent primitive root as \( e \) increases.