数论笔记

2023/1/18

1. 对于任意自然数 \(n,m,a>1\)，证 \((a^m-1,a^n-1)=a^{(m,n)}-1\)

证：来自同学

$(a^m - a^n, a^n - 1) = (a^n (a^{m-n}-1), a^n -1 ) $

\((a^n, a^{(n,m)}-1)=1\)，故只需要考虑 \(((a^{m-n}-1), a^n -1 ) = a^{(m-n, n)} -1\)。

易归纳。个人认为很 perfect 的证明。

证：来自教材

令 \(d = (m,n), D = (a^m-1, a^n-1)\)

易知 \((a^d-1)|D\)

构造 \(mu - nv = d\)，由 $D | a^m -1 $ 得到 \(D | a^{mu}-1\)

同理 \(D | a^{nv} - 1\)

合并得到 $D | a^{mu} - a^{nv} $，即 \(D | a^{nv} (a^d -1)\)（注意，用到 \(u>0, v>0\)，其实一定可以构造得出）

由 \(D | a^{nv} -1\) 得到 \((D,a^{nv})=1\)，故 \(D | (a^d-1)\)

综上，\(D = a^d-1\) 成立。