这里记录了一些学习过程中遇到的数学证明

d∣n⇔xd+1∣xn+1d | n \Lrarr x^d+1|x^n+1

充分性

即求证：

d∣n⇒xd+1∣xn+1d|n \Rarr x^d + 1 | x^n +1

设 n=kdn = kd，有

xd−1=(x−1)(xd−1+⋯+x+1)x^d-1 = (x-1)(x^{d-1} + \cdots + x + 1)

xn−1=(x−1)(xkd−1+⋯+x+1)=(x−1)(xd−1+⋯+x+1)(x(k−1)d+⋯+xd+1)=(xd−1)(x(k−1)d+⋯+xd+1)\begin{align*} x^n-1 &= (x-1)(x^{kd-1} + \cdots + x + 1) \\ &= (x-1)(x^{d-1} + \cdots + x + 1)(x^{(k-1)d} + \cdots + x^d + 1) \\ &= (x^d-1)(x^{(k-1)d}+ \cdots + x^d + 1) \end{align*}

证毕

必要性

即求证:

xd+1∣xn+1⇒d∣nx^d+1 | x^n + 1 \Rarr d|n

设 n=kd+rn = kd+r，其中 $ 0 \leq r < d$，只需证 r=0r = 0

假设 $r \neq 0 $，有：

xn−1=xkdxr−1=(xkd−1)xr+xr−1=(xd−1)(xkd−1+⋯+x+1)xr+xr−1\begin{align*} x^n-1 &= x^{kd} x^r - 1 \\ &= (x^{kd}-1) x^r + x^r-1 \\ &= (x^d-1)(x^{kd-1} + \cdots + x + 1)x^r + x^r-1 \end{align*}

也即 xn+1x^n+1 被 xd−1x^d-1 除的余式是 xr−1x^r -1

因为 r≠0r \neq 0，所以 xr−1≠0x^r -1 \neq 0
与条件矛盾，假设不成立

所以 xd+1∣xn+1⇒d∣nx^d+1 | x^n + 1 \Rarr d|n 证毕