hard problem 9 | 解析数论基础练习题
luogu_gza
·
·
学习·文化课
求 y!+5^x=z^3 的所有正整数解。
::::info[solution]
首先我们给出结论,只有 (x,y,z)=(2,2,3),(1,5,5) 这两组解,下面我们给出其证明。
我们先处理 y \leq 5。
当 y=1 时,z^3=1+5^x\equiv2\pmod4,不可能。
当 y=2 时,模 9 得 x\equiv2,3\pmod6。若 3\mid x,则 z^3-(5^{x/3})^3=2,而两个不同的正整数立方之差至少为 2^3-1^3=7,矛盾。因此 x\equiv2\pmod6,我们由此不妨设 u=5^{x/2},有 u^2+2=z^3。
此方程在正整数中只有 (u,z)=(5,3),我们来证明这一点。
用一点代数数论的手法,考察环 \mathbb Z[\sqrt{-2}] 关于范数 N(a+b\sqrt{-2})=a^2+2b^2 是欧几里得环(两个坐标分别取最近整数,余数的相对范数至多为 1/4+2/4<1)。
它们两的乘积是一个东西的三次方,由于 u 为奇数,u+\sqrt{-2} 与 u-\sqrt{-2} 互素,所以它们各自也是一个东西的三次方,故唯一分解给出 u+\sqrt{-2}=(a+b\sqrt{-2})^3。比较虚部:b(3a^2-2b^2)=1。于是 b=1,a=\pm1。比较实部并用 u>0 可以排除 a=-1,得到 a=1,u=5,z=3。所以 (x,y,z)=(2,2,3)。
当 y=3,4 时,模 9,由 y !\equiv 6 \pmod 9 有 x\equiv4,5\pmod6。再模 7 得到 y=3 \Rightarrow x \equiv 4 \pmod 6 和 y=4 \Rightarrow x \equiv 5 \pmod 6。我们再将两侧模 31,两种情形分别给出了 z^3\equiv11\pmod{31},z^3\equiv18\pmod{31},但二者均不是模 31 的立方剩余,矛盾。
当 y=5 时,若 x\ge2,则 v_5(120+5^x)=1,不可能是立方。故 x=1,从而 z=5,得到 (1,5,5)。
我们接下来证明 y \geq 6 无解。
:::info[题外话]
由于是草稿所以我直接不加 latex 了。
我一开始尝试这个题的时候做的是这样的功夫:
y>=6 的时候我们 %9,有 z^3=5^x(mod 9),然后分析 %9 的三次剩余可以有 3|x,然后令 x=3k,y!=(z-5^k)(z^2+z5^k+25^k),令这两个为 A 和 B,有 AB=y!,B>A^2 所以 A^3<y!,对于 p=3k+2 型素数映射 u->u^3 在 %p^e 的单位群上是双射所以 z^3=5^{3k} mod(p^{v_p(y!)}) 可以直接改成 z=5^k(mod p^{v_p(y!}),所以有 p^{v_p(y!)}|z-5^k=A,接下来我们定义R_y:=\prod_{p<=y,p%3=2}p^{v_p(y!)} 需要求证 R_y^3>y!,如果有这个的话,就有 A^3>=R_y^3>y! 所以和这个矛盾炸了。然后我对这个的分析是:就你肯定知道 \sum_{p<=y,p%3=k)logp/p=1/2logy+O(1),这是定量的狄利克雷定理,你又有 v_p(y!)=y/p+O(1),log R_y^3/y!=\sum_{p<=y}v_p(y!)log p*([p%3=2]*2-1*[p%3=0,1])~y(2 \sum_{p%3=2}logp/p-\sum_{p%3=1}logp/p-log3/3),然后你可以嗯出来 log R_y^3/y!~1/2 ylogy+O(y)>0,然后我就不知道怎么去估这个 O(y) 了,我们只知道对充分大的 y 这是成立的,但是却不知道如何找到一个充分大的 y
| 这里有一个疏漏是那个双射的结论对 p=5 不成立,需要特殊处理一下 5,然后下面的 B(n) 本质是对这个 R(y) 取了几项然后做了定量分析,思路能和 g 老师稍微对上一点,可谓是荣幸之至了…… |
如果你看不懂为什么下面的 B(n) 要取叽里咕噜的几项的话,也许可以看看题外话来了解一下人类怎么想到这个
记 n=y。因为 9\mid n!,而模 9 的立方剩余只有 0,1,-1,所以 3\mid x。
令 x=3k,a=5^k,d=z-a>0,Q=z^2+az+a^2,有 n!=dQ,Q>d^2,则 d^3<n!。
若素数 p\equiv2\pmod3 且 p\ne5,则 p\nmid Q。否则,因 p\nmid a,t\equiv z/a\pmod p 满足 t^2+t+1=0,从而是非平凡的三次单位根,与 3\nmid p-1 矛盾。另外,模 3 有 z\equiv a\not\equiv0,写成 z=a+3t 得
Q=3(a^2+3at+3t^2),\qquad v_3(Q)=1
因此下面的整数一定整除 d:
B(n)=3^{v_3(n!)-1}
\prod_{p\in\{2,11,17,23,29\}}p^{v_p(n!)}
当 6\le n\le31 时,可以计算说明 B(n)^3>n! 与 d^3<n! 矛盾。
魔法的开端。
当 32\le n\le512 时,在勒让德公式
v_p(n!)=\sum_{j\ge1}\left\lfloor\frac{n}{p^j}\right\rfloor
中,对 p=2,3,11,17,23,29,分别保留前 K_p=9,5,2,2,1,1 项,并用 \lfloor t\rfloor\ge t-1。记
\alpha=\sum_p(\log p)\sum_{j=1}^{K_p}p^{-j}>1.905
\beta=\log3+\sum_p K_p\log p<29.80.
可得 \log B(n)\ge\alpha n-\beta>1.905n-29.80,另一方面,我们有 \log(n!)\le(n+1)\log n-n+1,所以 3\log B(n)-\log(n!)>
F(n):=6.715n-(n+1)\log n-90.4,这个函数在 [32,512] 上是凹的,可以计算证明在 [32,512] 上这个函数 >0。于是 B(n)^3>n!,再次与 d^3<n! 矛盾。
接下来我们解决 n \geq 512 的部分,这次我们要面对的是无穷的数。
令
S(n)=\prod_{\substack{p\text{ 为素数}\\p\equiv1\pmod6}}p^{v_p(n!)},A=12\sqrt3,c=\frac{\log A}{5}
我们证明
\log S(n)\le cn\bigl(\log(n/7)+1\bigr)\qquad(n\ge7) \tag{1}
对正整数 m,考虑
P(m)=\frac{2^{m-1}3^{\lfloor(m-1)/2\rfloor}}{m!}
\prod_{j=0}^{m-1}(6j+1)
这是整数:对素数 p\ge5,等差数列中每连续 p^r 项恰有一项是 p^r 的倍数,故乘积中的指数至少为 \lfloor m/p^r\rfloor;素数 2,3 则由前面的补偿因子处理。同时,(6j+1)/(j+1)<6 给出
P(m)\le A^{m-1} \tag{2}
设
\Psi(t)=\prod_{\substack{p\equiv1\pmod6\\p^r\le t,\ r\ge1}}p
对每一个 m<p^r\le6m、p\equiv1\pmod6,数 p^r\equiv1\pmod6 本身出现在上面的等差数列中,而分母的 m! 不含这一层 p^r 的贡献;其他各层的指数差非负。因此
\frac{\Psi(6m)}{\Psi(m)}\mid P(m),
\qquad \Psi(6m)\le A^{m-1}\Psi(m) \tag{3}
给定实数 t>0,取 m_0=\lceil t/6\rceil,并反复取 m_{j+1}=\lceil m_j/6\rceil,直至为 1。由 (3) 及
m_{j+1}-1\le\frac{m_j-1}{6},\qquad
\sum_j(m_j-1)\le\frac65(m_0-1)<\frac t5
得到 \log\Psi(t)\le ct。又因这一类的最小素数为 7,
\log S(n)=\sum_{j=1}^{\lfloor n/7\rfloor}\log\Psi(n/j)
\le cn\sum_{j=1}^{\lfloor n/7\rfloor}\frac1j
\le cn\bigl(\log(n/7)+1\bigr)
即证明了 (1)。
现在回到原方程。令 g=\gcd(z,a)=5^r。因为 g^3\mid n!,
3r\le v_5(n!)\le\sum_{j\ge1}\frac n{5^j}=\frac n4
\qquad 2r\le\frac n6
除去公因子后,z/g 与 a/g 互素。因此 Q/g^2 的素因子除了一次幂的 3 外,全为 1\pmod6 的素数。这些素因子的指数又不超过它们在 n! 中的指数,所以
Q\le3\cdot5^{2r}S(n)\le3\cdot5^{n/6}S(n). \tag{4}
利用 \log(n!)>n\log n-n 及 (1),有
\frac23\log(n!)-\log\bigl(3\cdot5^{n/6}S(n)\bigr)
>nH(n)
其中
H(n)=\left(\frac23-c\right)\log n
-\left[\frac23+\frac{\log5}{6}+c(1-\log7)\right]
-\frac{\log3}{n}
因为 c=0.6068425588\ldots<2/3,H 严格递增;直接代入得 H(512)>0.010。于是对所有 n\ge512,由 (4) 得
Q<(n!)^{2/3}
但 d^3>n! 给出 d<(n!)^{1/3},从而 Q=n!/d>(n!)^{2/3},矛盾。
| 最后一段 n \geq 512 仍然是由 g 老师生成的,我明天再研读一下写点人话。 |