求 $n$ 的最小值，使得 $109^{20}$ 整除 $123^n-99^n$

hbghlyj

据ExponentLift所述 $n=6×109^{19}$ 是 $n$ 的最小值，使得 $109^{20}$ 整除 $123^n-99^n$：

hbghlyj

在比宇宙年龄（$138.2\times10^9$岁）短的时间内没有可能暴力找到解。
让我们尝试一些数学技巧。
$109$ 是素数，并且与 $123$、$99$ 互素。
不能直接使用 LTE 引理，因为 $123-99$ 不是 $109$ 的倍数，而 LTE 引理要求 $p$ 整除 $x-y$！
那么，首先，找到 $k$ 的最小值，使得 $123^k-99^k$ 是 $109^1$ 的倍数：
$123^1-99^1\mod109=24$
$123^2-99^2\mod109=96$
$123^3-99^3\mod109=38$
$123^4-99^4\mod109=76$
$123^5-99^5\mod109=65$
$123^6-99^6\mod109=\color{#f00}0$
这意味着 $109$ 整除 $123^6 - 99^6$，并且 LTE 引理 适用于这种新形式 $123^n-99^n=(123^6)^m-(99^6)^m$：
根据 LTE 引理，$$v_{109}((123^6)^m-(99^6)^m)=v_{109}(123^6-99^6)+v_{109}(m)$$计算得 $v_{109}(123^6-99^6)=1$，因此$$v_{109}((123^6)^m-(99^6)^m)=1+v_{109}(m)$$
为了使得 $109^{20}\mid(123^6)^m-(99^6)^m$，即$v_{109}((123^6)^m-(99^6)^m)\ge20$，需$v_{109}(m)\ge19$，
即 $\min\{m:109^{20}\mid(123^6)^m-(99^6)^m\}=109^{19}$.
即 $\min\{n:109^{20}\mid123^n-99^n\}=6\times109^{19}$

hbghlyj

维基百科上有一个类似的问题
求 $n$ 的最小值，使得 $3^{3}\cdot 5^{5}\cdot 7^{7}$ 整除 $149^n-2^n$.

3、7可以直接用 LTE；
对于5不能直接用LTE，类似上面，先从$5|149^n-2^n$推出$4|n$，设$n=4m$，对$5|(149^4)^m-(2^4)^m$使用LTE

hbghlyj

Table[Mod[PowerMod[123,i, 109]-PowerMod[99,i, 109],109],{i,108}]
$123^{109}-99^{109}\bmod109$的周期为108

1. {24, 96, 38, 76, 65, 0, 53, 103, 93, 77, 30, 0, 58, 14, 1, 2, 39, 0, 10, 40, 34, 68, 18, 0, 13, 52, 66, 23, 67, 0, 6, 24, 64, 19, 98, 0, 95, 53, 105, 101, 62, 0, 69, 58, 82, 55, 37, 0, 57, 10, 63, 17, 59, 0, 85, 13, 71, 33, 44, 0, 56, 6, 16, 32, 79, 0, 51, 95, 108, 107, 70, 0, 99, 69, 75, 41, 91, 0, 96, 57, 43, 86, 42, 0, 103, 85, 45, 90, 11, 0, 14, 56, 4, 8, 47, 0, 40, 51, 27, 54, 72, 0, 52, 99, 46, 92, 50, 0}

复制代码

Select[Range[108],PowerMod[123,#, 109]==PowerMod[99,#, 109]&]
$\{n:123^n-99^n\equiv0\pmod{109}\}$的周期为6

1. {6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96, 102, 108}

复制代码