几个最大公约数相关数论常见定理

标签：right frac gcd 数论 定理 ge 最大公约数 binom left

今天才知道这几个定理，网上没搜到证明方式，别人不会证那我就证明一下。

定理1：

\[\gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1 \]

证明：

根据 \(\gcd\) 具有 \(\gcd(a, b) = \gcd(a - b, b)\) 的性质，不妨设 \(m \ge n\)，作差有：

\[\begin{aligned} \gcd(a^m - 1, a^n - 1) &= \gcd(a^m - a^n, a^n - 1) \\ &= \gcd(a^n(a^{m - n} - 1), a^n - 1) \end{aligned} \]

由于 \(\gcd(a^n, a^n - 1) = 1\)，

\[\begin{aligned} \gcd(a^n(a^{m - n} - 1), a^n - 1) &= \gcd(a^n, a^n - 1)\gcd(a^{m - n} - 1, a^n - 1) \\ &= \gcd(a^{m - n} - 1, a^n - 1) \end{aligned} \]

由递归定义，则原式等价于：

\[\gcd(a^{m \bmod n} - 1, a^n - 1) \]

根据辗转相除法的形式，我们不难得出：

\[\gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1 \]

---

定理2

\[\gcd(a^m - b^m, a^n - b^n) = a^{\gcd(m, n)} - b^{\gcd(m, n)} \]

其中 \(\gcd(a, b) = 1\) 且 \(a > b\)

证明：

根据定理1的类似证明方式，作差后有：

\[\begin{aligned} \gcd(a^m - b^m - (a^n - b^n), a^n - b^n) &= \gcd(a^na^{m-n} - b^nb^{m-n} - (a^n - b^n), a^n - b^n) \\ &= \gcd(a^n(a^{m-n} - b^{m-n}) + b^{m-n}(a^n - b^n), a^n - b^n) \\ &= \gcd(a^n(a^{m-n} - b^{m-n}), a^n - b^n) \\ &= \gcd(a^{m-n} - b^{m-n}, a^n - b^n) \\ &= \gcd(a^{m \bmod n} - b^{m \bmod n}, a^n - b^n) \end{aligned} \]

由递归定义可得 \(\gcd(a^m - b^m, a^n - b^n) = a^{\gcd(m, n)} - b^{\gcd(m, n)}\)。

---

定理3

\[G = \gcd\left(\binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n - 1}\right) \]

• 设 \(p \in \mathbb{P}\)，若 \(n = p^k(k > 0)\)，\(G = p\)。
• \(\texttt{otherwise}\)，\(G = 1\)。

证明：

• \(n = p^k\) 时，因为 \(\binom{n}{i} = \frac{n!}{i!(n-i)!}(1 \le i < n)\)。
  由勒让德定理有，对因子 \(p\)，\(p\) 的出现次数为 \(L_p(n!) = \sum\limits_{i \ge 1}\left\lfloor\frac{n}{p^i}\right\rfloor\)。

\[L_p((n-i)!) + L_p(i!) = \sum\limits_{j \ge 1}\left\lfloor\frac{i}{p^j}\right\rfloor + \sum\limits_{j \ge 1}\left\lfloor\frac{n-i}{p^j}\right\rfloor \le \sum\limits_{j \ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor = L_p(n!) \]

而等号成立的条件当且仅当 \(i \mid p^j, (n - i) \mid p^j\)，而 \(n = p^k\) 贡献了 \(1\)，不存在 \(i \mid p^k\) 的情况，因此前者严格小于后者。

因此 \(p \mid \binom{n}{i}(1 \le i < n)\)，而 \(\binom{n}{1} = p\)，可得 \(\gcd\left(\binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n - 1}\right) = p\)。

• \(\texttt{otherwise}\)，同样根据勒让德定理，可以推出：

\[L_p((n-i)!) + L_p(i!) = \sum\limits_{j \ge 1}\left\lfloor\frac{i}{p^j}\right\rfloor + \sum\limits_{j \ge 1}\left\lfloor\frac{n-i}{p^j}\right\rfloor \le \sum\limits_{j \ge 1}\left\lfloor\frac{n}{p^j}\right\rfloor = L_p(n!) \]

设 \(n = p_1^{k_1}p_2^{k_2}\ldots p_t^{k_t}(t>1, p_1<p_2<\ldots<p_t)\)，当且仅当 \(i \mid p^j, (n - i) \mid p^j\) 时等号成立。

若对 \(n\) 的某个质因子 \(p_0\)，将 \(n\) 改写为 \(p_0\) 进制有 \(n = c_0 + p_0c_1 + p_0^2c_2 + \ldots p_0^rc_r\)。

由于 \(n\) 不能被写作 \(p_0\) 的幂形式，因此必然存在 \(c_\lambda \neq 0(0 \le \lambda < r)\)，设 \(i = p_0^\lambda c_\lambda\)，根据整除性质，可以发现等号成立。

对于每一个因子 \(p_0\)，都存在一个 \(i\) 使得 \(L_{p_0}(n!) = L_{p_0}(i!) + L_{p_0}((n-i)!)\)。

因此，对于任意一个质因子 \(p\) 都存在一个 \(i\) 使得 \(p \nmid \binom{n}{i}\)，即 \(G = 1\)。

综上，上述结论成立。

定理4
若 \(F(n)\) 表示斐波那契数列第 \(n\) 项，则

\[\gcd(F(n), F(m)) = F(\gcd(n, m)) \]

标签：right,frac,gcd,数论,定理,ge,最大公约数,binom,left
From： https://www.cnblogs.com/YipChipqwq/p/18554908