相邻正整数的最大素因子

hbghlyj

对任意整数 $n \geq 2$, 记 $F(n)$ 为 $n$ 最大的素因子. 一个好对是指一对相异素数 $p q$ 满足不存在整数 $n \geq 2$ 使得 $F(n) F(n+1)=p q$。证明：存在无穷多个好对。
来源: 罗马尼亚大师杯 2020 题目六

hbghlyj

mathoverflow.net/questions/332901
So running a simple sieve algorithm allows for recording pairs which are not nice, and there are many of them below 9 million. I get that the complement includes (2,q) for q=23,29,37,47, and more, (3,q) for q=89,103,113,131,137 and more, (5,q) for q=307,503,509,613,619 and some more, (7,q) for q=967,971,1031,1039,1049 and some more, (11,q) for q=2381,2543,2551,2591,2801 and a few more, and (13,q) for q=2531,2689,2797. For larger values of 13 <p<q<

3000, there are no nice pairs.

I am willing to believe there is a q less than 2^2^101 for which (101,q) is nice. Based on preliminary data, I doubt q would be less than 2^101.

---

aops 21# 如下

Claim: If for two odd primes $p < q$ we have $\operatorname{ord}_q(2) = \operatorname{ord}_p(2)$ then $(p,2)$ is strange.

Proof: If $F(n)F(n+1)=2p,$ then either $(n,n+1)$ is either $(2^k, 2^k+1)$ or $(2^k-1, 2^k)$ for some positive integer $k.$ In the latter case, note $p \mid 2^{k}-1 \implies \operatorname{ord}_p(2) \mid k \implies \operatorname{ord}_q(2) \mid k \implies q \mid 2^k-1.$ In the former case, $p \mid 2^{k}+1 \implies \operatorname{ord}_p(2) =\operatorname{ord}_q(2) = 2k \implies q \mid 2^{2k}-1,$ and since $q \nmid 2^k-1$ because $\operatorname{ord}_q(2) \ne k,$ we have $q \mid 2^k+1.$ $\square$

It suffices to show there are infinitely many distinct pairs of odd primes $p,q$ where $\operatorname{ord}_q(2) = \operatorname{ord}_p(2).$ Take any prime $P = 2k+1 > 5$ (obviously infinitely many) and note
\begin{align*} 2^{2P} + 1 &=4\cdot 2^{4k} + 1\\ &=(2^{2k+1}+2^{k+1}+1)(2^{2k+1}-2^{k+1}+1). \end{align*}Note $\gcd(2^{2k+1}+2^{k+1}+1, 2^{2k+1}-2^{k+1}+1)=\gcd(2^{k+2}, 2^{2k+1}-2^{k+1}+1)=1,$ $3 \nmid 2^{2P}+1,$ and $25 \nmid 2^{2P}+1$ since $10 \nmid 2P.$ So we can take two distinct primes $p,q > 5$ dividing $2^{2P}+1,$ so $\operatorname{ord}_q(2), \operatorname{ord}_p(2) \mid 4P.$ Obviously now $\operatorname{ord}_q(2), \operatorname{ord}_p(2) > 4,$ so $\operatorname{ord}_q(2) = \operatorname{ord}_p(2) = 4P$ as desired. $\blacksquare$

hbghlyj

(引理部分的翻译)
引理: 奇素数 $p < q$ 满足 $\operatorname{ord}_q(2) = \operatorname{ord}_p(2)$ 则 $(p,2)$ 是好对.

证明: 若存在$n$使$F(n)F(n+1)=2p$, 则$F(n)=2$或$F(n+1)=2$, 即$n$或$n+1$是2的幂.
1° $n=2^k$, 则$F(n+1)=p\implies p \mid 2^{k}+1 \implies \operatorname{ord}_p(2) =\operatorname{ord}_q(2) = 2k \implies q \mid 2^{2k}-1=(2^k-1)(2^k+1)$
因为 $q \nmid 2^k-1$ (因为 $\operatorname{ord}_q(2) \ne k$), 我们有 $q \mid 2^k+1$, 与$p$为$n+1$的最大素因数矛盾.
2° $n+1=2^k$, 则$F(n)=p\implies p \mid 2^{k}-1 \implies \operatorname{ord}_q(2)= \operatorname{ord}_p(2) \mid k\implies q \mid 2^k-1$, 与$p$为$n+1$的最大素因数矛盾.
因此不存在$n$使$F(n)F(n+1)=2p$, 则$(p,2)$ 是好对.
引理证毕.