monoid.free

Recent Notes

Exercise A0.V.2.13

3 min read

Lemma P2.1

In Z[x],\mathbb{Z}[x],

xn−1=(x−1)(∑k=0n−1xk).x^n - 1 = (x - 1)\left(\sum_{k=0}^{n-1}x^k \right).

Proof

(x−1)(∑k=0n−1xk)=x(∑k=0n−1xk)−(∑k=0n−1xk)=(∑k=0n−1xk+1)−(∑k=0n−1xk)=(x1+x2+…+xn−1+xn)−(x0+x1+…+xn−2+xn−1)=xn−x0\begin{align*} (x - 1)\left(\sum_{k=0}^{n-1}x^k \right) &= x\left(\sum_{k=0}^{n-1}x^k\right) - \left(\sum_{k=0}^{n-1}x^k\right)\\ &= \left(\sum_{k=0}^{n-1}x^{k+1}\right) - \left(\sum_{k=0}^{n-1}x^k\right)\\ &= \left(x^1 + x^2 + \ldots + x^{n -1} +x^n\right) - \left(x^0 + x^1 + \ldots + x^{n - 2} +x^{n -1}\right)\\ &= x^n - x^0\\ \end{align*}

■\blacksquare

Proposition A

Let a,b∈Z>0.a,b \in \mathbb{Z}_{>0}. In Z[x],\mathbb{Z}[x], xb−1x^b - 1 divides xa−1x^a - 1 if and only if bb divides a.a.

Proof

For convenience, I will use the notation [k1;k2)[k_1; k_2) to denote the polynomial xk1+xk1+1+…+xk2−1.x^{k_1} + x^{k_1 + 1} + \ldots + x^{k_2 - 1}. Note that xm[k1;k2)=[k1+m;k2+m)x^m [k_1;k_2) = [k_1 + m; k_2 + m) and [k1;k2)+[k2;k3)=[k1;k3).[k_1; k_2) + [k_2; k _3) = [k_1;k_3).

Suppose bb divides aa and let cc be such that a=cb.a = cb.

By P2.1 we have

xa−1=(x−1)[0;a)andxb−1=(x−1)[0;b).x^a - 1 = (x - 1)[0;a)\quad\text{and}\quad x^b - 1=(x - 1)[0;b).

To prove divisibility, it suffices to find a cofactor CC such that

[0;a)=C[0;b).[0;a) = C[0;b).

Set C=x0+xb+x2b+…+x(c−1)b.C = x^0 + x^b + x^{2b} + \ldots + x^{(c-1)b}. Then

C[0;b)=x0[0;b)+xb[0;b)+x2b[0;b)+…+x(c−1)b[0;b)=[0;b)+[b;2b)+[2b;3b)+…+[(c−1)b;cb)=[0;a).\begin{align*} C[0;b) &= x^0[0;b) + x^b[0;b) + x^{2b}[0;b) + \ldots + x^{(c-1)b}[0;b)\\ &= [0;b) + [b;2b) + [2b;3b) + \ldots + [(c-1)b;cb)\\ &= [0;a). \end{align*}

⚠️ Suppose, conversely, that there exists a cofactor CC such that xa−1=C(xb−1).x^a - 1 = C(x^b - 1).

By cancellation, we get [0;a)=C[0;b).[0;a) = C[0;b). Observe that both [0;a)[0;a) and [0;b)[0;b) have x0x^0 as their constant term, thus the minimum degree monomial of CC must be x0.x^0.

We will now prove that all monomials of CC are of the form xa−nbx^{a - nb} starting with the maximal degree monomial and descending.

Note that the leading coefficient of [0;a)[0;a) is the same as the leading coefficient of [0;b),[0;b), namely 1.1. Thus, the leading coefficient of CC must also be 1.1. For the equality [0;a)=C[0;b)[0;a) = C[0;b) to hold, it must be that deg⁡(C)+b=a,\deg(C) + b = a, so deg⁡(C)=a−b.\deg(C) = a - b. This proves that the leading monomial of CC is xa−b.x^{a - b}.

Let C′=C−xa−b.C' = C - x^{a - b}. Now, consider [0;a)=(C′+xa−b)[0;b),[0;a) = (C' + x^{a - b})[0;b), which implies [0;a−b)=C′[0;b).[0;a-b) = C'[0;b). The second highest degree monomial of CC is the leading monomial of C′.C'. We can apply this procedure inductively. At each step, we remove one monomial from C,C, and since CC has finitely many monomials, this must terminate.

This shows that all monomials of CC are of the form xa−nb.x^{a - nb}. Since x0x^0 is among them, there exists nn such that a−nb=0,a - nb = 0, hence a=nb.a = nb. So bb divides a.a.

■\blacksquare

Proposition B

Let a,b,c∈Z>0a,b,c \in \mathbb{Z}_{>0} with c>1.c > 1. Then, cb−1c^b - 1 divides ca−1c^a - 1 if and only if bb divides a.a.

Proof

Suppose bb divides a.a. Then, by Proposition A, xb−1x^b -1 divides xa−1,x^a - 1, and evaluating at x=cx = c completes this part of the proof.

Suppose that cb−1c^b -1 divides ca−1.c^a - 1. Then there exists CC such that ca−1=C(cb−1).c^a -1 = C(c^b - 1).

Write a=qb+r,a = qb + r, where 0≤r<b.0 \leq r < b. Then ca−1=cr(cqb−1)+(cr−1).c^a - 1 = c^r (c^{qb} - 1) + (c^r - 1). Since cqb−1c^{qb} - 1 is divisible by cb−1,c^b - 1, cr−1c^r - 1 must be also divisible by cb−1.c^b - 1. ⚠️

But cr−1<cb−1c^r - 1 < c^b - 1 so cr−1=0,c^r - 1 = 0, hence r=0.r = 0.

■\blacksquare

Recent Notes

Graph View

Backlinks