1. \(\boldsymbol{\gcd(a,b)=a \iff a \mid b \iff \operatorname{lcm}(a,b)=b}\)
2. Any common divisor of a and b is a divisor of \(\gcd(a,b)\); any common multiple of a and b is a multiple of \(\operatorname{lcm}(a,b)\).If \(m\mid a,\;m\mid b\), then \(m\mid \gcd(a,b)\); if \(a\mid m,\;b\mid m\), then \(\operatorname{lcm}(a,b)\mid m\).
3. For any positive integer m:\(\boldsymbol{\gcd(am,bm)=m\cdot\gcd(a,b)},\quad \boldsymbol{\operatorname{lcm}(am,bm)=m\cdot\operatorname{lcm}(a,b)}\)
4. \(\boldsymbol{\gcd(a,b)\times \operatorname{lcm}(a,b)=|ab|}\)

5. Bezout’s Identity: If \(\boldsymbol{\gcd(a,b)=d}\), there exist integers \(m,n\) such that \(\boldsymbol{am+bn=d}\).
6. If \(\boldsymbol{\gcd(a,c)=1}\), then \(\boldsymbol{\gcd(a,bc)=\gcd(a,b)}\).
7. If \(\boldsymbol{\gcd(a,m)=1}\) and \(\boldsymbol{\gcd(b,m)=1}\), then \(\boldsymbol{\gcd(ab,m)=1}\).
8. If \(\boldsymbol{a\mid bc}\) and \(\boldsymbol{\gcd(a,c)=1}\), then \(\boldsymbol{a\mid b}\).
9. If \(\boldsymbol{a\mid m,\;b\mid m}\) and \(\boldsymbol{\gcd(a,b)=1}\), then \(\boldsymbol{ab\mid m}\).

最大公约数（GCD）与最小公倍数（LCM）性质

中文总结

1. 两数的最大公约数等于数a，等价于a能整除b，等价于两数的最小公倍数等于b。
2. \(a,b\)的任意公约数都是二者最大公约数的约数；\(a,b\)的任意公倍数都是二者最小公倍数的倍数。
3. 对任意正整数m，两数同乘m后的最大公约数、最小公倍数，分别等于原最大公约数、最小公倍数乘m。
4. 两个数的最大公约数与最小公倍数的乘积，等于这两个数乘积的绝对值。

5. 裴蜀定理（贝祖定理）：若\(a,b\)的最大公约数为d，则存在整数\(m,n\)，使得 \(am+bn=d\)。
6. 若a与c互质，则a和bc的最大公约数等于a和b的最大公约数。
7. 若a、b均与m互质，则ab与m互质。
8. 若a能整除bc，且a与c互质，则a能整除b。
9. 若a、b都能整除m，且a、b互质，则ab能整除m。

---

Euclidean Algorithm (Method of Successive Division)

Given two positive integers \(a,b\), the steps to find their greatest common divisor \(\gcd(a,b)\):

1. Repeat division with remainder: divide the larger number by the smaller one, and replace the original larger number with the obtained remainder.
2. This process terminates after finite steps when the remainder becomes 0.
3. The last non‑zero divisor is the greatest common divisor of a and b.This algorithm is also called the Method of Successive Division.

设 \(a,b\) 为正整数，求二者最大公约数 \((a,b)\) 的方法：

1. 反复进行带余除法：用两数中较大的数除以较小的数，用所得余数替换原来的较大数；
2. 该操作经过有限次后，余数必为 0，运算停止；
3. 最后一个不为 0 的除数，即为 \(a,b\) 的最大公约数；此算法也叫辗转相除法。

---

Given that n is a positive integer less than 50, and \(4n+5\) and \(7n+6\) are not coprime, find all values of n that satisfy the conditions.

已知n为小于50的正整数，且使得\(4n+5\)和\(7n+6\)的值不互质，求所有满足要求的n。

解答

核心原理：利用欧几里得算法（辗转相除法），最大公约数满足 \(\boldsymbol{\gcd(a,b)=\gcd(a,b-a)}\)，两数不互质即最大公约数大于1。

1. 化简最大公约数：

\(\begin{align*} \gcd(4n+5,\,7n+6)&=\gcd(4n+5,\,(7n+6)-(4n+5))=\gcd(4n+5,\,3n+1)\\ &=\gcd(3n+1,\,(4n+5)-(3n+1))=\gcd(3n+1,\,n+4)\\ &=\gcd(n+4,\,(3n+1)-3(n+4))=\gcd(n+4,\,-11)\\ &=\gcd(n+4,\,11) \end{align*}\)

2. 分析条件：11 是质数，两数不互质 \(\implies \gcd(n+4,11)=11\)，即 \(\boldsymbol{11\mid n+4}\)。
3. 求符合范围的n：设 \(n+4=11k\)（k为正整数），则 \(n=11k-4\)。由 \(0<n<50\)：

• \(k=1\)，\(n=7\)
• \(k=2\)，\(n=18\)
• \(k=3\)，\(n=29\)
• \(k=4\)，\(n=40\)
• \(k=5\)，\(n=51>50\)（舍去）

最终答案：\(\boldsymbol{n=7,\,18,\,29,\,40}\)

---

Let \(m,a,b\) be positive integers with \(m>1\). Prove that
\(\boldsymbol{\gcd\left(m^a-1,\ m^b-1\right)=m^{\gcd(a,b)}-1}\)

设 \(m,a,b\) 均为正整数，且 \(m>1\)，证明：

\(\boldsymbol{\left(m^a-1,\ m^b-1\right)=m^{(a,b)}-1}\)

其中 \((x,y)\) 表示 \(x,y\) 的最大公约数。

解答

步骤 1：证明核心引理

对整数 \(m>1,\ a\ge b>0\)，有

\(\boldsymbol{\gcd(m^a-1,\ m^b-1)=\gcd(m^{a-b}-1,\ m^b-1)}\)

推导：

利用代数变形 \(m^a-1=m^{a-b}(m^b-1)+(m^{a-b}-1)\)，

根据最大公约数性质 \(\gcd(x,y)=\gcd(y,x\bmod y)\)，

可得 \(\gcd(m^a-1,\,m^b-1)=\gcd(m^b-1,\,m^{a-b}-1)\)。

步骤 2：指数辗转相除证明原式

对指数 \(a,b\) 使用欧几里得辗转相除法：

不妨设 \(a\ge b\)，反复套用引理： \(\begin{align*} \gcd(m^a-1,\,m^b-1)&=\gcd(m^{a-b}-1,\,m^b-1)\\ &=\gcd(m^b-1,\,m^{a\bmod b}-1) \end{align*}\)

该过程与直接对指数 \(a,b\) 求最大公约数 \(\gcd(a,b)\) 的步骤完全一致。

设 \(d=\gcd(a,b)\)，指数辗转相除最终结果为 d，因此

\(\boldsymbol{\gcd(m^a-1,\,m^b-1)=m^d-1=m^{\gcd(a,b)}-1}\)

举例验证

取 \(m=2,\ a=4,\ b=6\)：

\(\gcd(2^4-1,\,2^6-1)=\gcd(15,63)=3\)，

\(2^{\gcd(4,6)}-1=2^2-1=3\)，等式成立。

Solution

Step 1: Prove the Key Lemma

For integers \(m>1\) and \(a\ge b>0\),

\(\boldsymbol{\gcd(m^a-1,\ m^b-1)=\gcd(m^{a-b}-1,\ m^b-1)}\)

Derivation:

From the identity \(m^a-1=m^{a-b}(m^b-1)+(m^{a-b}-1)\),

by the Euclidean algorithm property \(\gcd(x,y)=\gcd(y,x\bmod y)\),

we get \(\gcd(m^a-1,\,m^b-1)=\gcd(m^b-1,\,m^{a-b}-1)\).

Step 2: Prove the original formula via exponent division

Apply the Euclidean Algorithm to exponents \(a,b\):

Assume \(a\ge b\), repeatedly use the lemma: \(\begin{align*} \gcd(m^a-1,\,m^b-1)&=\gcd(m^{a-b}-1,\,m^b-1)\\ &=\gcd(m^b-1,\,m^{a\bmod b}-1) \end{align*}\)

This process is exactly the same as calculating \(\gcd(a,b)\).

Let \(d=\gcd(a,b)\). The exponent division terminates at d, so

\(\boldsymbol{\gcd(m^a-1,\,m^b-1)=m^d-1=m^{\gcd(a,b)}-1}\)

Verification Example

Take \(m=2,\ a=4,\ b=6\):

\(\gcd(2^4-1,\,2^6-1)=\gcd(15,63)=3\),

\(2^{\gcd(4,6)}-1=2^2-1=3\). The equality holds.

---

上面的这个题目其实有更一般的形式，就是把1换成变量

通用定理

设正整数 \(a,b\)，整数 \(x、y\) 满足 \(\boldsymbol{\gcd(x,y)=1}\)（\(x,y\) 互质），则

\(\boldsymbol{\gcd\left(x^a-y^a,\ x^b-y^b\right)=x^{\gcd(a,b)}-y^{\gcd(a,b)}}\)

特例（你之前学的 \(m^n-1\) 形式）

当 \(\boldsymbol{y=1}\) 时，直接退化为：

\(\boldsymbol{\gcd\left(x^a-1,\ x^b-1\right)=x^{\gcd(a,b)}-1}\)

核心原理

1. 因式分解：\(x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\dots+y^{n-1})\)
2. 指数辗转相除：\(\gcd(x^a-y^a,\,x^b-y^b)=\gcd(x^b-y^b,\,x^{a-b}-y^{a-b})\ (a\ge b)\)，对指数 \(a,b\) 用欧几里得算法，最终指数为 \(\gcd(a,b)\)
3. \(\gcd(x,y)=1\) 用来排除额外公因数干扰

---

General Theorem

Let \(a,b\) be positive integers, and integers \(x,y\) satisfy \(\boldsymbol{\gcd(x,y)=1}\) (x and y are coprime). Then

\(\boldsymbol{\gcd\left(x^a-y^a,\ x^b-y^b\right)=x^{\gcd(a,b)}-y^{\gcd(a,b)}}\)

Special Case (your previous \(m^n-1\) form)

When \(\boldsymbol{y=1}\), it simplifies directly to:

\(\boldsymbol{\gcd\left(x^a-1,\ x^b-1\right)=x^{\gcd(a,b)}-1}\)

Core Principle

1. Factorization: \(x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\dots+y^{n-1})\)
2. Exponent Euclidean Algorithm:\(\gcd(x^a-y^a,\,x^b-y^b)=\gcd(x^b-y^b,\,x^{a-b}-y^{a-b})\ (a\ge b)\).Apply the Euclidean algorithm to exponents \(a,b\), the final exponent is \(\gcd(a,b)\).
3. The condition \(\gcd(x,y)=1\) eliminates extra common divisors.

---