CP3

一些大小估计类问题

经典的估计是 \((a,b)\le a-b,[a,b]\ge \frac {ab}{a-b}\) ，从而 \(\sum_{k=0}^{n-1}\frac 1{[a_k,a_{k+1}]}\le 1-\frac 1{2^n}\) （归纳，分类 \(a_n<2^n,a_n\ge 2^n\) 即可）

此外， \(gcd\) 可以用欧拉函数表达，参见欧拉函数

例1

求证： \([m,n]+[m+1,n+1]\ge \frac{2mn}{\sqrt{m-n}}\)

\([m,n]=\frac{mn}{(m,n)}\) ，记 \(k=m-n\)

\(LHS=\frac{mn}{(m,n)}+\frac{(m+1)(n+1)}{(m+1,n+1)}>\frac{mn}{(k,n)}+\frac{mn}{(k,n+1)}\) （这里 \(m,n\) 趋于无穷时 \((m+1)(n+1)\) 肯定要放到 \(mn\)

下证 \(\frac{1}{(k,n)}+\frac{1}{(k,n+1)}\ge \frac1{\sqrt{k}}\)

实际上由于 \((n,n+1)=1\) ，故 \((k,n)(k,n+1) \mid k\) 可知成立

例2

证明： \(aC_{a+b}^b\mid [b+1,b+2,...,b+a]\)

一个有趣的方法是利用 \(\frac {x_1}{y_1}+\frac {x_2}{y_2}+..=\frac {k}{[y_1,y_2,...]}\) 来证明整除（这种方法可以配合拉格朗日插值多项式）

由分式分部公式 \(\large\frac {n!}{(x+1)(x+2)..(x+n)}=\sum\limits_{i=1}^n\frac{(-1)^{i-1}iC_n^i}{x+i}\) 可以得到：

\(\large \frac 1{C_{a+b}^b}=\sum\limits_{i=1}^a\frac{(-1)^{i-1}iC_a^i}{b+i}=a\sum\limits_{i=1}^a\frac{(-1)^{i-1}C_{a-1}^{i-1}}{b+i}=\frac{ak}{[b+1,b+2,...,b+a]},k\in Z\)

例3

1. 求证：对正整数等差数列 \(a_1<a_2<..<a_n,(a_1,a_2-a_1)=1\) 有 \(a_1a_2...a_n\mid (n-1)![a_1,a_2,...,a_n]\)

2. 求证：对正整数等差数列 \(a_1<a_2<...<a_n\) 有 \([a_1,a_2,...,a_n]\ge \frac{2^{n-1}}{n}\)

1. 设 \(d\) 是公差，将 \(x=\frac {a_1}d\) 代入分式分部公式可以得到： \(\large\frac{d^{n-1}(n-1)!}{a_1a_2...a_n}=\sum\limits_{k=1}^n\frac{(-1)^{k-1}C_{n-1}^{k-1}}{a_1+(k-1)d}\) （当然，已经将组合数的 \(n\) 提取出来）

2. 取 \(k=[\frac{n}2]+1\) ，由于 \(a_ka_{k+1}...a_n\mid (n-k)![a_k,a_{k+1},...,a_n]\) ，可知 \([a_1,a_2,...,a_n]\ge [a_k,a_{k+1},...,a_n]\ge \frac{(a_1+(k-1)d)(a_1+kd)...(a_1+(n-1)d)}{(n-k)!}\ge C_{n-1}^{k-1}\ge \frac {2^{n-1}}{n}\)

最后一个不等号来自于 \(C_{n-1}^0+C_{n-1}^1+...=2^{n-1}\) ，而 \(C_{n-1}^{k-1}\) 是其中最大的一项

注：例2与例3(1)都可以通过直接分析素因子幂次证明

有趣的是， \([1,2,...,n]\ge 2^{n-1}\) ，这可由 \([1,2,...,n+1]=(n+1)(C_n^0,C_n^1,...,C_n^n)\ge \frac 1{n+1}\cdot(n+1)\sum C_n^i=2^n\) 得到，第一步的恒等式留给读者（借助例2）

例4

1. 区间 \([2m-\sqrt m+1,2m]\) 存在素数 \(p\) ，求证：对任意正整数 \(a_1,a_2,...,a_m\) ，存在 \(i,j\in\overline{1,m}\) ，有 \(\frac{a_i}{(a_i,a_j)}\ge m\)

2. 求证：\(2n-1\) 为素数当且仅当对任意正整数 \(a_1,a_2,...a_n\) ，存在 \(i,j\in \overline{1,n}\) 使得 \(\frac{a_i+a_j}{(a_i,a_j)}\ge 2n-1\)

3. 已知 \(p\) 为素数，求证： 对任意正整数 \(a_1,a_2,...,a_{p+1}\) ，存在 \(i,j\in \overline{1,p+1}\) 使得 \(\frac{a_i}{(a_i,a_j)}\ge p+1\)

不妨设 \((a_1,a_2,...,a_m)=1\) 。采用反证法，假设命题不成立。

首先，不存在 \(p\mid a_i\) ，否则取出 \(p\nmid a_j\) ，\(\frac{a_i}{(a_i,a_j)}\ge p>m\)

其次，不存在 \(a_i\equiv a_j\:(mod ~p)\) ，否则 \(p\mid \frac{a_i-a_j}{(a_i,a_j)}\) ，有 \(\frac {a_i}{(a_i,a_j)}>\frac{a_i-a_j}{(a_i,a_j)}>m\)

下面设 \(p=2m-(2l-1),l\le \frac{\sqrt m}2\) ，并构造 \(m-l\) 个抽屉 \((1,2m-2l),(2,2m-2l-1),...,(m-l,m-l+1)\) ，放入 \(a_i(mod~p)\) ，其中 \(l\) 个为满抽屉

所以有 \(l\) 对 \((i,j)\) 满足 \(p\mid \frac{a_i+a_j}{(a_i,a_j)}\) ，但由于 \(\frac{a_i}{(a_i,a_j)}<m<p\) ，知 $ \frac{a_i+a_j}{(a_i,a_j)}<2p$ ，只能是 \(p\)

对于每个 \(\frac{a_i+a_j}{(a_i,a_j)}=2m-2l+1\) ，因为 \(\frac{a_i}{(a_i,a_j)}<m\) ，从而 \(\frac{a_j}{(a_i,a_j)}>2m-2l+1-m=m-2l+1\)

对于满抽屉 \((a_1,a_2)(a_3,a_4)...(a_{2l-1},a_{2l})\) ，设 \(a_1,a_3,...\) 是更大的，从而 \(\frac{a_{2i-1}}{(a_{2i-1},a_{2i})}\in[m-l+1,m-1]\) ，根据抽屉原理有相同，不妨 \(\frac {a_1}{(a_1,a_2)}=\frac{a_3}{(a_3,a_4)}\)

我们来分析 \(a_1>a_2,a_3>a_4\) 这 \(4\) 个数，具体地，设 \(a_1=da,a_2=db,a_3=ea,a_4=eb,(a,b)=1,a<b\) 并不妨设 \((d,e)=1\)

记 \((a,d)=q,(a,e)=n,(b,d)=s,(b,e)=t,a=qnx,b=sty,d=qsz,e=ntw\)

下面我们记 \(K=\frac{a_1}{(a_1,a_4)},M=\frac{a_4}{(a_1,a_4)},L=\frac{a_2}{(a_2,a_3)},N=\frac{a_3}{(a_2,a_3)}\) ，得到 \(K=qnx\cdot qsz/ns=q^2xz,M=t^2yw,L=s^2yz,N=n^2xw\)

已经知道的是 \(qnx+sty=2m-2l+1\) ，而 \(K+L=z(q^2x+s^2y),M+N=w(t^2y+n^2x)\) ，若 \(z>1\) 或 \(w>1\) ，有 \(K+L+M+N\ge 2\sqrt 2qnx+2\sqrt 2sty=2\sqrt 2(2m-2l+1)\ge 4m\) ，与反证假设矛盾

当 \(z=w=1\) ，不妨 \(q>n\) ，有 \(\frac KN=(\frac qn)^2\ge (\frac {n+1}n)^2\) ，\(KN=(qnx)^2=a^2,a\ge m-l+1\) （此式可得 \(n<\sqrt a\) 因为 \(q>n\) ）， \(K^2\cdot \frac NK\ge a^2\) 得到 \(K\ge a+\frac an>a+\sqrt a>m\) ，矛盾

那么 \(q=n=1\) ，此外，我们还有 \(s=t=1\) 来自于 \(L=s^2y,M=t^2y\) ，因为 \(b\ge m-2l+2\) 类似上述论证得到，这很显然矛盾了

2. 一个 \(2n-1=ab(a\ge b)\) 的构造是 \(m=\frac {b-1}2\cdot a\) 当 \(m\) 为偶数时令 \(m'=m-a\) ，则 \(1,2,...,m+1,m+3,m+5,...\) 满足条件，例如 \(25:1,2,3,4,5,6,8,10,...,20\)

3. 注意 \(k=\frac {[a_1,a_2,...,a_m]}{a_1}\ge m\) ， \(a_1<a_2<...<a_m\) ，因为 \(ka_1\) 不小于 \(a_1\) 的因子至多有 \(k\) 个 \(\frac {ka_1}1,\frac{ka_1}2,...,\frac{ka_1}k\) ，而 \(a_1,a_2,..,a_m\) 是它的不同因子，不小于 \(a_1\)

例5

设 \(n>4\) ，正整数序列 \(a_1<a_2<...<a_n\le 2n\) ，证明： \(\min\limits_{1\le i\ne j\le n} [a_i,a_j]\le 6([\frac n2]+1)\)

首先，若存在 \(a_i\mid a_j\) ，命题显然

设不存在 \(a_i\mid a_j\) ，分成 \(n\) 个抽屉 \((1,2,4,...,2^{x_1})(3,6,12,...,2^{x_2})...(2n-1)\)

直接取 \([2^{x_1},3\cdot 2^{x_2}]\le 3\cdot 2^{x_1}\le 3n\) ，完成证明

注：一个需要该抽屉构造解决的题目是：正整数 \(a_1<a_2<...<a_n\le 2n\) 满足 \([a_i,a_j]> 2n\) ，求证： \(\frac 1 {a_1}+...+\frac 1{a_n}\le \frac 76\)

这个结果并不漂亮，需要一定的分段缩放以及积分估计，而 Erdos 给出了：对任意 \(a_1<a_2<...<a_k\le n,[a_i,a_j]>n\) ， \(n\ge\sum [\frac n{a_i}]\ge \sum[\frac n {a_i}]-k\) 从而 \(\frac 1{a_1}+...\frac 1{a_n}\le\frac 32\) ，第一个等号是因为在 \(n\) 以内没有 \(a_i,a_j\) 的公共倍数

例6

证明： \((n,[n\sqrt 2])<\sqrt[4]{8n^2}\)

设 \(d=(n,[n\sqrt 2]),n=kd,[n\sqrt 2]=md\) ，其中 \(md<kd\sqrt 2<md+1\) ，从而 \(m^2<2k^2\) 即 \(m^2\le 2k^2-1\) 且 \((k\sqrt 2-m)d<1\iff (2k^2-m^2)d<k\sqrt 2+m\)

结合两式，得 \(d<k\sqrt 2+m<2\sqrt 2k<\sqrt[4]{8n^2}\)

例7

对 \(S\) 定义 \(|S|\) 表示 \((\sum\limits_{x,y\in S}\frac 1{[x,y]})^{\frac 12}\) ，求证：若 \(A,B\) 是不交正整数有限集，则 \(|A\cup B|\le |A|+|B|\)

在欧拉函数中已经给出了一种做法，这里再给出一种，关键是对 \(x\mid y\) 有 \(\frac yx=\sum\limits_{x\mid k,k\le y}1\) 以及 \([x,y]\mid k\iff x\mid k,y\mid k\)

设 \(D=lcm(S)\) ，有 \(\frac {D}{[x,y]}=\sum\limits_{k\le D,[x,y]\mid k}1\) ，则

\( \begin{aligned} D|S|^2&=\sum\limits_{x,y\in S}\sum\limits_{k\le D,[x,y]\mid k} 1\\ &=\sum\limits_{k=1}^D\sum\limits_{x,y\in S,x\mid k,y\mid k}1\\ &=\sum\limits_{k=1}^D(\sum\limits_{x\in S,x\mid k}1)^2 \end{aligned} \)

下设 \(N=lcm(A\cup B)\)

\(|A\cup B|\le |A|+|B|\)

\(\iff (\sum\limits_{k=1}^N(\sum\limits_{x\in A,x\mid k}1+\sum\limits_{x\in B,x\mid k}1)^2)^{\frac 12}\le (\sum\limits_{k=1}^N(\sum\limits_{x\in A,x\mid k}1))^{\frac 12}+(\sum\limits_{k=1}^N(\sum\limits_{x\in B,x\mid k}1)^2)^{\frac 12}\)

即三角不等式

例8

给定 \(n\ge 2\) ，已知 \(a_1,a_2,..,a_n\in \N^*,\gcd(a_1,a_2,...,a_n)=1\) ，记 \(D_i=\gcd\limits_{1\le j\le n,j\ne i}(a_j),d_i=\gcd(a_i,S)\) ，其中 \(S=a_1+a_2+...+a_n\) ，求 \(\prod\limits_{i=1}^n\frac{S-a_i}{d_iD_i}\) 的最小值

这里可以先估计 \(\prod d_iD_i\) ，关键想法是它可以写成 \(\prod d_iD_{i+1}\) ，而 \(d_i\mid a_i,D_{i+1}|a_i\) ，并且它们互质，因为设 \(d=(d_i,D_{i+1}),d\mid d_i=>d\mid S;d\mid D_{i+1}=>d\mid a_1+a_2+...,a_i+a_{i+2}+...+a_n=S-a_{i+1}\) ，从而 \(d\mid a_1,a_2,...,a_n\) ，得出结论

从而 \(\prod d_iD_i\le a_1a_2...a_n\) ，而 \(\prod(S-a_i)\ge (n-1)^n\prod a_i\) （由均值不等式直接得到），最小值就是 \((n-1)^n\) ，当 \(a_1=a_2=...=a_n\) 取到

CP4

最小公约数和最大公倍数更多还是以分析工具的身份出现在数论中，这里记录一些使用例与方法

例1

已知正整数 \(a>b>1\) 满足方程 \(\frac{a^x-1}{a-1}=\frac{b^y-1}{b-1}(x>1,y>1)\) 有至少两组不同的正整数解，求证： \((a,b)=1\)

设解为 \((x_1,y_1)(x_2,y_2)\) ，我们看到

\(a^{x_2-1}+...+a^{x_1}=b^{y_2-1}+...+b^{y_1}\)

我们设素数 \(p^k~||~(a,b)\) ，可以看到 \(p^{k(x_1+1)}\mid p^{ky_1}\mid RHS\) ，所以 \(p^{k(x_1+1)}\mid LHS\equiv a^{x_1}\:(mod~p^{k(x_1+1)}\) ，进一步 \(p^{k+1}\mid a\) ，但是看

\(a^{x_2}+...+a^2=b^{y_2}+...+b^2+b-a\)

如果 \(v_p(a)>v_p(b)\) ，那么 \(v_p(RHS)=v_p(b)\) ，但 \(v_p(LHS)=2v_p(a)>v_p(b)\) ，矛盾！

于是 \((a,b)=1\)

CP5

杂题

例1

设 \(n\ge 2\) ，证明：至多有限个 \(n\) 数组 \((a_1,a_2,...,a_n)\) 满足：

1. \(a_1>a_2>...>a_n\)

2. \((a_1,a_2,...,a_n)=1\)

3. \((a_1,a_2)+(a_2,a_3)+...+(a_{n-1},a_n)+(a_n,a_1)=a_1\)

由于 \(RHS\le a_2-a_1+a_3-a_2+...+a_{n-1}-a_n+a_1\) ，取等仅当 \(a_n\mid a_1,a_{i+1}=\frac{k_{i+1}-1}{k_{i+1}}a_i\)

问题转换为 \((1-\frac 1{k_2})(1-\frac1{k_3})...(1-\frac1{k_n})=\frac {a_n}{a_1}\) ，记 \(x_i=k_i-1\) ，即 \(\prod(1+\frac 1{x_i})=\frac{a_1}{a_n}\)

\(x_i\in Z^*\) 意味着 \(\frac {a_1}{a_n}\) 有上界，从而只有有限个取值，我们证明：

\(\prod\limits_{i=1}^n(1+\frac 1{x_i})=t\) 只有有限组正整数解

假设命题对 \(n-1\) 成立，取 \(x_n=min\{x_i\}\) ，则 \(1+\frac 1{x_n}\ge \sqrt[n]t\) 至多有有限个值，而前 \(n-1\) 个数根据归纳假设也只有有限组

证毕

例2

给定 \(k\ge 2\) ，若 \([n+1,n+2,...,n+k]\) 是关于 \(n\) 的多项式 \(P(n)\) ，求证： \(k=2\)

法一：假设命题对 \(k\ge 2\) 成立，当 \(n\) 充分大时，有 \([n,n+1,...,n+k-1]<[n+1,...,n+k]\)

希望： \([n,n+1,...,n+k-1]\ge [n+1,...,n+k]\) ，一个自然的想法是令 \(n\) 为素数， \(n+k\) 为合数，并且 \(n+k\) 有一个素因子小于 \(k\) （这样，它在 \(n+1,n+2,...,n+k-1\) 就能找到一个倍数）

任取素数 \(q\nmid k,q\le k-1\) ，由 \(Dirichlet\) 定理，存在无穷个素数 \(p\equiv -k\:(mod~q)\)

那么 $[p,p+1,...,p+k-1]=p[p+1,...,p+k-1]>\frac{p+k}{q}[p+1,...,p+k-1]\ge [p+1,...,p+k] $ 当 \(p\) 充分大成立

法二：记 \([n+1,...,n+k]=\frac{(n+1)(n+2)...(n+k)}{A_n}\)

第三部分的例三给出： \(A_n\mid (n-1)!\) （当然，可以不用精细估计，直接估计素因子幂次有上界也行），从而 \(A_n\) 的取值有限

由抽屉原理，存在一个 \(A\) 使得无穷个 \(A_n=A\) ，即 \(P(n)=\frac{(n+1)(n+2)...(n+k)}{A}\) 有无穷个根，只能是 \(P(n)\) 等于右侧的多项式

下考虑 \(A=(k+1)!/[2,...,k+1]=(k+2)!/2[3,...,k+2]\)

由于 \(k\ge 3\) ，\([2,3,4,...,k+1]=[3,4,...,k+1]\)

1. \(k+2\) 为素数，则 \([3,...,k+2]=[3,...,k+1](k+2)\) ，那么 \(A=(k+1)!/[3,...,k+1]=(k+1)!/2[3,...,k+1]\) ，矛盾

2. \(k+2\) 为合数，并且 \(k+2>4\) ，从而 \(k+2\mid [2,3,...,k+1]=[3,...,k+1]\) ，即 \(A=(k+1)!/[3,...,k+1]=(k+2)!/2[3,...,k+1]\iff 1=\frac{k+2}2\) ，矛盾