Order Of A Modulo N And Cyclotomic Polynomials

Let's dive into a fascinating connection between the order of an integer modulo $n$ and cyclotomic polynomials. Specifically, we're going to explore the theorem that states if $d$ is the order of $a$ modulo $n$, then $n$ divides $\Phi_d(a)$, where $\Phi_d(a)$ is the $d$-th cyclotomic polynomial evaluated at $a$. This is a cool result in number theory, blending abstract algebra concepts with polynomial arithmetic.

Understanding the Basics

Before we jump into the proof, let's make sure we're all on the same page with the terminology. Guys, it's important to have these definitions locked down. First, the order of $a$ modulo $n$, denoted as $ord_n(a)$, is the smallest positive integer $d$ such that $a^d \equiv 1 \pmod{n}$. This means $n$ divides $a^d - 1$, and $d$ is the smallest positive exponent for which this is true. Crucially, we assume that $gcd(a, n) = 1$, because the order is only defined when $a$ and $n$ are coprime.

Next, let's talk about cyclotomic polynomials. The $d$-th cyclotomic polynomial, denoted as $\Phi_d(x)$, is a polynomial whose roots are the primitive $d$-th roots of unity. In other words, it's the monic polynomial whose roots are the complex numbers $e^{2\pi i k/d}$ where $k$ ranges from $1$ to $d$ and $gcd(k, d) = 1$. A key property of cyclotomic polynomials is that they are irreducible over the rational numbers. Another important property is the identity:

$x^n - 1 = \prod_{d|n} \Phi_d(x)$

This identity tells us that $x^n - 1$ can be factored into cyclotomic polynomials whose indices are the divisors of $n$. For example, if $n = 6$, we have:

$x^6 - 1 = \Phi_1(x) \Phi_2(x) \Phi_3(x) \Phi_6(x)$

where $\Phi_1(x) = x - 1$, $\Phi_2(x) = x + 1$, $\Phi_3(x) = x^2 + x + 1$, and $\Phi_6(x) = x^2 - x + 1$.

Theorem Statement

Given an integer $a$ such that $gcd(a, n) = 1$, prove that $ord_n(a) = d$ if and only if $n | \Phi_d(a)$.

We are going to prove that $ord_n(a)=d$ if and only if $n | \Phi_d(a)$.

Proof

We will prove this in two directions:

Part 1: If $ord_n(a) = d$, then $n | \Phi_d(a)$

Suppose $ord_n(a) = d$. This means that $a^d \equiv 1 \pmod{n}$, and $d$ is the smallest positive integer for which this holds. Since $a^d \equiv 1 \pmod{n}$, it follows that $n | (a^d - 1)$. Now, using the identity relating $x^n - 1$ to cyclotomic polynomials, we can write:

$a^d - 1 = \prod_{k|d} \Phi_k(a)$

This means that $n$ divides the product $\prod_{k|d} \Phi_k(a)$. Our goal is to show that $n$ specifically divides $\Phi_d(a)$.

Since $n | (a^d - 1)$, we have $a^d \equiv 1 \pmod{n}$. Also, $a^d - 1 = \Phi_d(a) \prod_{k|d, k<d} \Phi_k(a)$. Let's assume, for the sake of contradiction, that $n$ does not divide $\Phi_d(a)$.

Since $ord_n(a) = d$, we know that $a^k \not\equiv 1 \pmod{n}$ for any $k < d$. This is crucial. Now, let's consider the product $\prod_{k|d, k<d} \Phi_k(a)$. If we can show that $gcd(n, \prod_{k|d, k<d} \Phi_k(a)) = 1$, then since $n | (a^d - 1)$ and $a^d - 1 = \Phi_d(a) \prod_{k|d, k<d} \Phi_k(a)$, it must be the case that $n | \Phi_d(a)$.

However, proving that $gcd(n, \prod_{k|d, k<d} \Phi_k(a)) = 1$ directly can be tricky. Instead, we'll use a slightly different approach.

Consider the minimal polynomial $m(x)$ of $a$ modulo $n$. This is the monic polynomial of smallest degree such that $m(a) \equiv 0 \pmod{n}$. Since $a^d \equiv 1 \pmod{n}$, the polynomial $x^d - 1$ is a polynomial that vanishes at $a$ modulo $n$. Therefore, $m(x)$ must divide $x^d - 1$. Also, since $\Phi_d(a) \equiv 0 \pmod{n}$ (we want to show this), it means that $m(x)$ divides $\Phi_d(x)$.

Now, because $x^d - 1 = \prod_{k|d} \Phi_k(x)$, we know that all irreducible factors of $x^d - 1$ modulo $n$ must be among the $\Phi_k(x)$ for $k|d$. Since $ord_n(a) = d$, it means that $d$ is the smallest positive integer such that $a^d \equiv 1 \pmod{n}$. Thus, if we consider any $k < d$ such that $k|d$, we must have $a^k \not\equiv 1 \pmod{n}$.

This implies that $n$ cannot divide $a^k - 1$ for any $k < d$. Therefore, $n$ cannot divide $\Phi_k(a)$ for any $k < d$. If $n$ divides $a^d - 1 = \prod_{k|d} \Phi_k(a)$ and $n$ does not divide $\Phi_k(a)$ for any $k < d$, then it must be that $n | \Phi_d(a)$.

Part 2: If $n | \Phi_d(a)$, then $ord_n(a) = d$

Now, suppose that $n | \Phi_d(a)$. This means that $\Phi_d(a) \equiv 0 \pmod{n}$. We want to show that $ord_n(a) = d$.

Since $\Phi_d(a) \equiv 0 \pmod{n}$, we know that $a$ is a root of $\Phi_d(x)$ modulo $n$. Also, we know that $x^d - 1 = \prod_{k|d} \Phi_k(x)$. Therefore, $a^d - 1 = \prod_{k|d} \Phi_k(a)$. Since $n | \Phi_d(a)$, it follows that $\Phi_d(a) \equiv 0 \pmod{n}$, and thus $a^d - 1 \equiv 0 \pmod{n}$. This implies that $a^d \equiv 1 \pmod{n}$.

Now, we need to show that $d$ is the smallest positive integer such that $a^d \equiv 1 \pmod{n}$. Suppose, for the sake of contradiction, that there exists a positive integer $k < d$ such that $a^k \equiv 1 \pmod{n}$. Then $ord_n(a) = k < d$.

If $a^k \equiv 1 \pmod{n}$ for some $k < d$, then $n | (a^k - 1)$. We also know that $x^k - 1 = \prod_{j|k} \Phi_j(x)$. Thus, $a^k - 1 = \prod_{j|k} \Phi_j(a)$. Since $n | (a^k - 1)$, it means that $n$ must divide $\prod_{j|k} \Phi_j(a)$.

However, this contradicts the fact that $ord_n(a) = d$. To see why, consider the identity $x^d - 1 = \prod_{k|d} \Phi_k(x)$. If $a^k \equiv 1 \pmod{n}$ for some $k < d$, it means that $ord_n(a) \leq k < d$. But we assumed that $ord_n(a) = d$, which is a contradiction. Therefore, there cannot exist any $k < d$ such that $a^k \equiv 1 \pmod{n}$.

Thus, $d$ must be the smallest positive integer such that $a^d \equiv 1 \pmod{n}$, which means $ord_n(a) = d$.

Conclusion

In conclusion, we have shown that $ord_n(a) = d$ if and only if $n | \Phi_d(a)$. This theorem provides a powerful connection between the order of an element modulo $n$ and cyclotomic polynomials, illustrating the deep interplay between number theory and abstract algebra. This is a beautiful result, and I hope this explanation has made it clear and understandable for everyone!