xᵈ-1 divides xⁿ-1 if and only if d divides n

Prove that x^d-1 divides x^n-1 if and only if d divdes n.


Suppose d|n; say n = dt.

If t = 1, there is nothing to show. Suppose t > 1; then x^n-1 = (x^d)^t - 1 = (x^d-1)(\sum_{i=0}^{t-1} (x^d)^i), so that x^d-1 divides x^n-1.

Now suppose x^d-1 divides x^n-1. By the Division Algorithm in \mathbb{N}, we have q and r such that n = qd+r. Now x^n-1 = x^{qd}x^r - 1 = x^{qd}x^r -x^r + x^r - 1 = x^r(x^{qd}-1) + (x^r-1). If q=1, then (by the uniqueness part of the division algorithm in \mathbb{Q}[x]) x^r-1 = 0, so r = 0 and d|n. If q > 1, then x^n - 1 = x^r(x^d-1)(\sum_{i=0}^{q-1} (x^d)^i) + (x^r-1), and again we have r = 0, so d|n.

Advertisements
Post a comment or leave a trackback: Trackback URL.

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

%d bloggers like this: