最小公约数 \((a,b)\) 即满足 \(d\mid a,d\mid b\) 的最大 \(d\)

最大公倍数 \([a,b]\) 即满足 \(a\mid d,b\mid d\) 的最小 \(d\)

若 \((a,b)=1\) 称 \(a,b\) 两数互素

重要结论：

1. \((a,b)[a,b]=ab\)

2. 裴蜀定理： \(ax+by=c\) 有整数解 \((x,y)\) 当且仅当 \((a,b)\mid c\)

证明：考虑辗转相除法中 \(u_1=a,u_2=b,u_3=a~mod~b,u_4=u_2~mod~u_3\) ...

设 \(d=u_k=u_{k-2}-u_{k-1}q_{k-1}=u_{k-2}-(u_{k-3}-u_{k-2}q_{k-2})q_{k-1}=...\)

即 \(d\) 可以表示为 \(a,b\) 的线性组合

必要性是显然的

拓展： \(a_1x_1+a_2x_2+...a_nx_n=b\) 有整数解当且仅当 \((a_1,a_2,...,a_n)\mid b\)

\(a_1 x_1+a_2x_2=(a_1,a_2)t_1\) ， \((a_1,a_2)t_1+a_3x_3=(a_1,a_2,a_3)t_2\) ，...

3. 高斯引理：若 \(a\mid bc,(a,b)=1\) ，则 \(a\mid c\) （同余语言：若 \(ac\equiv bc \:(mod ~m )\) ， 则 \(a\equiv b \:(mod ~~\frac{m}{(m,c)})\) ）

证明：存在 \(x\) 使得 \(bx\equiv 1\:(mod~a)\) ，由于 \(bcx\equiv 0\:(mod~a)\) 可知 \(c\equiv 0\:(mod~a)\)

一个引理是：\(a\mid m,b\mid m=>ab\mid m(a,b)\)

4. \((a^n,b^n)=(a,b)^n\)

5. \((a,b)=(a+pb,b),p\in Z\)

6. \((a^m-b^m,a^n-b^n)=a^{(m,n)}-b^{(m,n)}\)

CP1

一些基础内容

例1

正整数 \(m,n,k\) 满足 \(5^n-2\) 和 \(2^k-5\) 均为 \(5^m-2^m\) 的倍数，求证： \((m,n)=1\)

由条件知 \(5^{kn}-2^{kn}\equiv 2^k-5^n\equiv 5-2\equiv 3\:(mod~5^m-2^m)\)

从而 \(5^d-2^d\mid 3\) ， \(d=1\)

例2

给定正整数 \(n\ge 2\) ，设有 \(d_1,d_2,...,d_n\in Z_+\) ，且 \((d_1,d_2,...,d_n)=1\) ， \(d_i\mid d_1+d_2+...+d_n,i=1,2,...,n\) ，求证： \(d_1d_2...d_n\mid(d_1+d_2+...+d_n)^{n-2}\) ，并举例说明 \(n-2\) 的最优性

我们先说明 \(\gcd\limits_{1\le i\le n,i\neq k} (d_i)=1\) ，即去掉一个数后剩余数的最小公约数依旧为 \(1\)

假设 \(\gcd\limits_{1\le i\le n,i\neq k} (d_i)=d\) ，取 \(j\neq k\) ，则 \(d_j\mid d_1+d_2+...+d_n\) ，则 \(d\mid d_1+d_2+...+d_n\) ，这意味着 \(d\mid d_k\) ，与 \((d_1,d_2,...,d_n)=1\) 矛盾

记 \(S=d_1+d_2+...+d_n\)

取出一对互素的数 \(d_1,d_2\) ，由于去掉 \(d_1\) 剩余数最小公约数依旧是 \(1\) ，肯定存在与 \(d_2\) 互素的数，不妨设为 \(d_3\)

我们就取出了 \((d_1,d_2)=1,(d_2,d_3)=1\)

\(d_1d_2d_3\mid S(d_1,d_3)\) ，又 \((d_1,d_3,d_4,...,d_n)=1\) ，存在与 \((d_1,d_3)\) 互素的数，不妨记为 \(d_4\) ， 则 \(d_4\mid \frac{S}{(d_1,d_3)}\)

综上可知 \(d_1d_2d_3d_4\mid S^2\) ，可推知 \(d_1d_2...d_n\mid S^{n-2}\)

举例： \(1,2,3,6,12,24,...,3\cdot 2^{n-3}\)

例3

设 \(S\) 是一个由正整数组成的有限集，且 \(S\) 不含 \(1\) ，对任意 \(n\in Z_+\) ， \(\exists s\in S,~s.t.(n,s)=1\) 或 \(s\) ，求证：\(\exists s,t\in S,(s,t)\) 为素数（ \(s,t\) 可以相同）

取 \(n\) 为最小的满足 \(\forall s\in S,(n,s)>1\) 的正整数，则 \(\exists s\in S ,(n,s)=s\) ，取某个 \(s\) 的素因子 \(p\) ，由 \(n\) 的最小性知 \(\exists t\in S,(\frac{n}{p},t)=1\) ，结合 \((n,t)>1\) ，知 \((n,t)=p\) ，又 \(s\mid n\) ， \((s,t)=p\) 为素数

例4

设 \({a_n}\) 是严格单增的正整数列，满足 \((a_m,a_n)=a_{(m,n)}\) 对任意正整数 \(m,n\) 成立。已知存在一个最小正整数 \(k\) 使得 \(\exists0<r<k,s>k\) 使得 \(a_k^2=a_r\cdot a_s\) ，求证 \(r\mid k,k\mid s\)

基本思路是，假设其不成立，找到一个更小的 \(k\) 满足条件

\(a_{(r,k)}^2=(a_r,a_k)^2=(a_r^2,a_k^2)=(a_r^2,a_ra_s)=a_ra_{(r,s)}\)

若 \((r,k)<r\) ，由 \(a_{(r,k)}<a_r\) 知 \(a_r\neq a_{(r,s)}\) ，就与 \(k\) 的最小性矛盾

从而 \(r\mid k\)

又 \(\frac{a_k}{a_r}\cdot a_k=a_s\) ，有 \(a_k\mid a_s\) ，\((a_k,a_s)=a_k\)

结合 \((a_k,a_s)=a_{(k,s)}\) 及数列的单增性，知 \((k,s)=k\) ，即 \(k\mid s\)

注记：对这类数列存在数列 \(b_d\) 使得 \(a_n=\prod_{d\mid n}b_d\) ，可由莫比乌斯反演得到

例5

有 \(100\) 个整数 \(1,2,...,100\) ，现选择 \(a,b\) 并用 \((a^2b^2+3,a^2+b^2+2)\) 替换 \(a,b\) ，重复操作，求证最后剩下的数不是完全平方数

我们知道 \(x^2\equiv 0,1\:(mod~3)\)

1、 \(a,b\) 均为 \(3\) 的倍数 ，则 \((a^2b^2+3,a^2+b^2+2)\) 不为 \(3\) 的倍数

2、 \(a,b\) 一个为 \(3\) 的倍数，则 \((a^2b^2+3,a^2+b^2+2)\) 是 \(3\) 的倍数，但不是 \(9\) 的倍数

3、 \(a,b\) 均不为 \(3\) 的倍数，则 \((a^2b^2+3,a^2+b^2+2)\) 不是 \(3\) 的倍数

我们可以发现， \(3\) 的倍数个数奇偶性不变，那么开始有 \(33\) 个，最后就剩 \(1\) 个

又根据第二条，可知其不为 \(9\) 的倍数，即不为完全平方数

CP2

一些相关的构造题

例6

证明：对任意正整数 \(n\) ，存在正整数 \(a_1,a_2,...,a_n\) 使得 \(\forall i,j\in \overline{1,n}\:,|a_i-a_j|=(a_i,a_j)\)

归纳构造，设 \(a_1,a_2,...,a_{n-1}\) 是满足题设的 \(n-1\) 个整数，令 \(M=[a_1,a_2,...,a_{n-1}]\) ，则 \(M,M+a_1,M+a_2,...,M+a_{n-1}\) 满足题设

例7

证明：对最大公约数为 \(1\) 的集合 \(D\) ，存在一一映射 \(f:Z\rightarrow Z\) 使得 \(|f(n)-f(n+1)|\in D,\forall n\in Z\)

首先若 \(D\) 是无限集，递增排列元素 \(a_1<a_2<...\) ，记 \(x_n=(a_1,a_2,...,a_n)\) ，由于 \(x_n\ge x_{n+1}\) 且为整数，最终 \(x_n\) 是常数，整除于 \(D\) 的每一个元素，从而只能是 \(1\) ，取第一个 \(x_n=1\) 对应子集 \(a_1,a_2,...,a_n\) 即可

下面对 \(|D|\) 归纳证明：存在一一对应 \(f:Z\rightarrow gcd(D)Z\) 使得 \(|f(n)-f(n+1)|\in D,\forall n\in Z\) 当 \(n=1,D=\{d\}\) 时取 \(f(x)=dx\) 即可

下设结论对 \(|D|=m-1\) 成立，考虑 \(|D|=m\) ，设 \(b\in D,D'=D-\{b\}\) ，并记 \(d=gcd(D),d'=gcd(D')\) ，则对 \(D'\) 存在 \(g:Z\rightarrow d'Z\) 使得 \(|g(n)-g(n+1)|\in D'\)

记 \(n=kd+r,0\le r<d\) ，当 \(2\mid k\) ，令 \(f(n)=g(k)+rb\) ，否则令 \(f(n)=g(k)+(d-1-r)b\)

\(\forall x\in Z,\exist y,0\le z<d,dx=d'y+bz\) ，由于 \(g\) 是满射，从而 \(f\) 也是满射

下面检验 \(|f(n)-f(n-1)|\in D\) ，当 \(d\nmid n\) ，有 \(f(n)-f(n-1)=b\in D\) ；

当 \(d\mid n,2\mid \frac nd=k\) ，有 \(f(n)-f(n-1)=g(k)-g(k-1)\) ，当 \(2\mid n,2\nmid \frac nd=k\) ，有 \(f(n)-f(n-1)=g(k)-g(k-1)\)

综上命题成立