If a is an integer greater than 1, then aᵈ-1 divides aⁿ-1 if and only if d divides n

Fix an integer a > 1. Prove that for all d,n \in \mathbb{N}, d divides n if and only if a^d-1 divides a^n-1. Conclude that \mathbb{F}_{p^d} \subseteq \mathbb{F}_{p^n} if and only if d|n.

If d|n, then by this previous exercise, x^d-1 divides x^n-1 in \mathbb{Z}[x], and so a^d-1 divides a^n-1 in \mathbb{Z}.

Conversely, suppose a^d-1 divides a^n-1. Using the Division Algorithm, say n = qd+r. Now a^n-1 = (a^d)^qa^r - a^r + a^r - 1 = a^r((a^d)^q-1) + (a^r-1). If q = 1, then we have a^r-1 = 0, so that r = 0 and d|n. If q > 1, then a^n-1 = a^r(a^d-1)(\sum_{i=0}^{q-1} (a^d)^i) + (a^r-1), and again we have r = 0, so that d|n as desired.

Recall that \mathbb{F}_{p^k} is precisely the roots (in some splitting field) of x^{p^k}-x. Now d|n if and only if p^d-1 divides p^n-1 by the above argument, if and only if x^{p^d-1}-1 divides x^{p^n-1}-1 by a previous exercise, if and only if x^{p^d}-x divides x^{p^n}-x, if and only if \mathbb{F}_{p^d} \subseteq \mathbb{F}_{p^n}.

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: