LTE引理

· · 学习·文化课

LTE引理

1、奇素数 p 满足 p\mid a-b,p\nmid a,p\nmid b ，则有 v_p(a^n-b^n)=v_p(a-b)+n

证明：我们归纳证明。只需证下面两个引理：

1) v_p(a^p-b^p)=v_p(a-b)+1,p\mid a-b,p\nmid a,p\nmid b

设 a=kp^t+b ，由二项式定理知

a^p-b^p\equiv C_p^1kp^tb^{p-1}\equiv kb^{p-1}p^{t+1}\:(mod~p^{t+2})

其中 C_p^mk^mp^{tm}b^{p-m}=\frac{p}{m}C_{p-1}^{m-1}k^mp^{tm}b^{p-m} 为 p^{tm+1} 的倍数， tm+1\ge t+2(m\ge 2)

2) v_p(a^k-b^k)=v_p(a-b),p\mid a-b,p\nmid a,p\nmid b,p\nmid k

设 a=kp^t+b ，由二项式定理知

a^k-b^k\equiv C_k^1kp^tb^{k-1}\equiv k^2b^{k-1}p^t\:(mod~p^{t+1})

综上，结合归纳法可证原命题

2、奇素数 p 满足 p\mid a+b,p\nmid a,p\nmid b ，则对奇数 n 有 v_p(a^n+b^n)=v_p(a+b)+v_p(n)

3、2\mid x-y,2\nmid x,2\nmid y ，则 v_2(x^{2n}-y^{2n})=v_2(x^2-y^2)+v_2(n)

例1

设 p 为素数，且存在 n\in N^* ，使得 p\:||\:2^n-1 ，求证： p\:||\:2^{p-1}-1

记 \delta_p(2)=t,n=st,p-1=rt

由 LTE 引理， v_p(2^{n}-1)=v_p(2^t-1)+v_p(s) ，这说明 v_p(2^t-1)\le v_p(2^n-1)=1

又 v_p(2^{p-1}-1)=v_p(2^t-1)+v_p(r) ，而 r<p ，可知 v_p(2^{p-1}-1)=1

例2

求证： \large3^{\frac{5^{2^n}-1}{2^{n+2}}}\equiv(-5)^{\frac{3^{2^n}-1}{2^{n+2}}}\:(mod~2^{n+4})

记 M=2^n

由 LTE 引理，显然 2^{n+2}\:||\:5^{M}-1,2^{n+2}\:||\:3^{M}-1

记 k 为满足 -5\equiv 3^k\:(mod~2^{2n+4}) 的最小正整数

由 LTE 引理可知 \delta_{2^{n+4}}(3)=2^{n+2}

则只需证 3^{\frac{5^M-1}{2^{n+2}}}\equiv 3^{k\frac{3^M-1}{2^{n+2}}}\:(mod~2^{n+4})

\iff \frac{5^M-1}{2^{n+2}}\equiv k\frac{3^M-1}{2^{n+2}}\:(mod~2^{n+2}) \iff 5^M-1\equiv (3^M-1)k\:(mod~2^{2n+4}) $\begin{aligned}\iff 2^{2n+4}&\:\mid 3^{kM}-k\cdot 3^M+k-1\\ &=(3^M-1)(3^{M(k-1)}+3^{M(k-2)}+...+1-k)\\ \end{aligned}

结合 3^M\equiv 1\:(mod~2^{n+2}) 知

3^{M(k-1)}+3^{M(k-2)}+...+1-k\equiv 1+1+...+1-k\equiv 0\:(mod~2^{n+2})

接下来我们只需证明 k 的存在性

归纳证明。设 3^k\equiv -5\:(mod~2^n)

3^{k+2^{n-2}}\equiv 3^k\cdot 3^{2^{n-2}}\equiv (2^n-5)(2^n+1)\equiv -5\:(mod~2^{n+1})

例3

求方程 (a+b)^x=a^y+b^y 的所有正整数解 (a,b,x,y)

令 y=1 ，有平凡解 (a,b,1,1)

令 x=1 ，有平凡解 (1,1,1,y) （ y=2 仅有此解）

下考虑 y\ge 3,x\ge 2 ，记 (a,b)=d,a=da_1,b=db_1

原条件等价于 (a_1+b_1)^x=d^{y-x}(a_1^y+b_1^y)

我们先证明对任意素数 p 满足 p\mid s+t,(s,t)=1 有 v_p(s^k+t^k)\le v_p(s+t)+v_p(k)

  1. 当 p>2 ， k 为奇数则为 LTE 引理， y 为偶数，由于 p\mid a^k-b^k,(a^k-b^k,a^k+b^k)\le 2 ，有 v_p(s^k+t^k)=0

  2. 当 p=2 ， k 为偶数由 v_2(a^2+b^2)=1,\forall a,b\in \N 显然， k 为奇数则设 t=c\cdot 2^n-s,2\nmid c ，我们有

s^k+t^k=C_k^1\cdot c\cdot 2^n\cdot s^{k-1}+C_k^2\cdot c\cdot 2^{2n}\cdot s^{k-2}+...\equiv C_k^1\cdot c\cdot s^{k-1} \cdot 2^n\:(mod~2^{n+1})

显然 v_2(s^k+t^k)=v_2(s+t) ，即证

回到原题，对每一个 a_1+b_1 的素因子 p ，我们有

xv_p(a_1+b_1)=(y-x)v_p(d)+v_p(a_1^y+b_1^y)\le (y-x)v_p(d)+v_p(a_1+b_1)+v_p(y)

由于 p 也覆盖了 d^{y-x}(a_1^y+b_1^y) 的所有素因子（因为它们是相等的），结合所有不等式可知

(a_1+b_1)^x\le (a_1+b_1)yd^{y-x}

又 (a_1+b_1)^x=d^{y-x}(a_1^y+b_1^y) 可知 a_1^y+b_1^y\le a_1y+b_1y ，其中 y\ge 3

1) a_1=b_1=1 ，代回原方程 2^{x-1}=d^{y-x} ，即 a=b=d=2^m ，解得 (2^m,2^m,km+1,km+k+1),k\in\N^*

2) a_1=1,b_1>1 ，有 1+b_1^y\le(1+b_1)y ，唯一解为 b_1=2,y=3 ，不难得到 d=1 ，其余情况可归纳证明

3) a_1,b_1>1 ，有 a_1^y+b_1^y\le a_1y+b_1y ，显然不成立

综上可知所有解为 (a,b,1,1)(1,1,1,y)(1,2,2,3)(2^m,2^m,km+1,km+k+1) ，对称解略

例4

设 a,b,c,d 是不同的正整数，p 是不整除 abcd 的奇素数，已知存在正整数 M 使得 1\le \max\limits_{n\in Z_+}v_p(ca^n-db^n)\le M ，证明：存在正整数 T ，使得对任意正整数 n ，若 v_p(ca^n-db^n)>0 ，则 v_p(ca^n-db^n)=T

首先设 x^{-1} 表示 x 模 p^{M+1} 意义下的逆元

记 ab^{-1}=x,dc^{-1}=y ，我们有 v_p(x^n-y)=v_p(ca^n-db^n) （模 p^{M+1} 即可验证）

如果命题不成立，我们可以得知 0<v_p(x^s-y)=e<v_p(x^t-y)=f ，那么 v_p(x^s-x^t)=d ， \delta_p(x) 存在 ，记为 k

接下来取 N=\max v_p(x_n-y) ，希望有 \delta 使得 v_p(x^{n+\delta}-y)>v_p(x^n-y)

v_p(x^{n+\delta}-y)=v_p(x^n-y+x^n(x^\delta-1))$ ，只需 $\frac{x^\delta-1}{p^N}\equiv (x^n)^{-1}\frac{x^n-y}{p^N}\:(mod~p)

由 v_p(x^d-1)\le d<N ，可取 \delta=p^rq 使得 v_p(x^\delta-1)=N ， q=1,2,...,p-1 时 \frac{x^\delta-1}{p^N} 遍历模 p 缩系，证毕

例5

求所有整数 b>2 满足存在无限多正整数 n 使得 n^2\mid b^n+1

取 n 的某个素因子 p ，有 b^n\equiv -1\:(mod~p),b^{2n}\equiv 1\:(mod~p) 那么 \delta_p(b)\mid (p,2n) 且 2 的次数与 2n 一致

此时取 p 为 n 的最小素因子，有 \delta_p(b)\mid 2 且 \delta_p(b)\ne 1 ，从而 p\mid b+1

声称其余 $b$ 均满足题设，从 $p_1^{\alpha_1} ~||~b+1$ 开始 归纳证明：存在 $p_{k+1}\mid b^{p_1p_2...p_k}+1

实际上 b^{p_1p_2...p_k}+1 在 p_1,p_2,...,p_k 只有 p_k 的次数相比 b^{p_1p_2...p_{k-1}}+1 提升了一次，而 \frac {b^{p_1p_2...p_k}+1}{b^{p_1p_2...p_{k-1}}+1}>p_k ，这就意味着一定有一个在 p_1,p_2,...,p_k 之外的素因子