Primitive roots & cyclotomic polynomials

Posted: December 17, 2009 in Elementary Algebra; Problems & Solutions, Rings and Modules
Tags: ,

Problem. Let \Phi_n(x) be the nth cyclotomic polynomial and p a prime number. Show that r is a primitive root \mod p if and only if \Phi_{p-1}(r) \equiv 0 \mod p.

Solution. If r is a primitive root modulo p, then modulo p: \ r^d - 1 \neq 0, for any 0 < d < p - 1. So modulo p: \ \Phi_d(r) \neq 0 because \Phi_d(r) \mid r^d - 1. But we also have

\Phi_{p-1}(r)\prod \Phi_d(r)=r^{p-1} - 1 \equiv 0 \mod p,

where the product is over \{d: \ \ d \mid p-1, \ d < p-1 \}. Therefore \Phi_{p-1}(r) \equiv 0 \mod p. Conversely, suppose that \Phi_{p-1}(r) \equiv 0 \mod p and r^d - 1 \equiv 0 \mod p, for some d < p-1, \ d \mid p-1. Then in (\mathbb{Z}/p\mathbb{Z})[x] we’ll have x-r \mid \Phi_d(x), \ x-r \mid \Phi_{p-1}(x). Thus x^{p-1} - 1=(x-r)^2f(x), for some f(x) \in (\mathbb{Z}/p \mathbb{Z})[x]. Then taking (formal) derivative will give us (p-1)r^{p-2} \equiv 0 \mod p, which is obviously impossible. \Box

Advertisements

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