Showing that $a^n - 1 \mid a^m - 1 \iff n \mid m$

Solution 1:

Let $m=kn+r$. Then

$$(a^m-1)-(a^r-1)=a^m-a^r=a^{kn}-1=(a^n-1)(\rm junk)$$

Then

$$a^n-1 | a^m-1 \Leftrightarrow a^n-1 | a^r-1 \,.$$

Since $0 \leq r <n$ we have $0 \leq a^r-1<a^n-1 $ and hence

$$a^n-1 | a^r-1 \Leftrightarrow a^r-1= 0 \Leftrightarrow r= 0 \Leftrightarrow n|m \,.$$

Solution 2:

It might help if you think of writing positive integers not in base 10 as we usually do, nor in base 2 or 16 as computers usually do, but in base $a$. Then $a^n-1$ is an $n$-digit number in which every digit is $a-1$, and similarly for $a^m-1$. This makes it quite easy to see what happens when you apply long division to divide $a^m-1$ by $a^n-1$.

Solution 3:

Here is another approach using "universal identities." We first show that

$$x^n -1 \mid x^m -1 \text{ in }\mathbb{Z}[x] \Longleftrightarrow n\mid m \text{ in }\mathbb{Z}.$$

Note that for monic, separable polynomials $f(x),\, g(x)\in \mathbb{Z}[x]$ we have $f(x)\mid g(x)$ iff every root of $f(x)$ in $\mathbb{C}$ is also a root of $g(x)$. Note that $x^n-1$ is separable for all $n\in\mathbb{N}$, which follows from $\gcd(x^n-1,nx^{n-1})=1$ in $\mathbb{Z}[x]$.

First suppose $n\mid m$. Let $x_0$ be a root of $x^n-1$ in $\mathbb{C}$. Then $m =nk$ for some $k\in \mathbb{Z}$, and we have $x_0^m = x_0^{nk} = 1^k = 1$. So, $x_0^m-1 = 0$. Thus, $x^n-1 \mid x^m-1$.

Next, suppose $x^n-1 \mid x^m-1$. Let $x_0$ be a primitive $n$th root of unity (not a $k$th root of unity for any $k<n$) which always exists (exercise.) By the division algorithm, we may write $m = nq + r$ where $q,\,r\in \mathbb{Z}$ and $0\leq r < n$. By our assumption, $1 = x_0^m = x_0^{nq + r} = x_0^r$. Since we assumed $x_0$ to be primitive, $r=0$. Thus, $m = nq$ and $n\mid m$.

Now that we have established the equivalence in $\mathbb{Z}[x]$, we may apply an evaluation homomorphism at any integer $a$ to get $n\mid m \Longrightarrow a^n-1 \mid a^m-1$. I do not quickly see if we can get the reverse implication from this argument. In any case, the idea was to demonstrate a neat technique.