一个数论相关的猜想

今天做题的时候看到一个人似乎认为这个结论是对的：

\(\operatorname{lcm}(a_1, a_2, \dots, a_n) \equiv \operatorname{lcm}(\operatorname{lcm}(\operatorname{lcm}(a_1, a_2)\bmod k, a_3), \dots) \pmod k\)

很显然这个东西假了，证伪的过程暂时不放，这里给出一个反例：

\(a_1 = 6, a_2 = 9, a_3 = 2, k = 5\)。

但是按照他的这种写法，仍然能够通过那道题目。

思考了一会之后，我注意到那道题目只关心最后的值对 \(k\) 取模的余数 是否 为 \(0\)。

所以我有个想法：

记上面 \(\equiv\) 号左边的为 \(\text{Lcm}\)，右边的为 \(\text{val}\)。

则对于任意 \(k\)，满足：

  1. 若 \(k | \text{Lcm}\)，则 \(k | \text{val}\)。

  2. 若 \(k \not| \text{Lcm}\)，则 \(k \not| \text{val}\)。

换句话说，\(\text{Lcm, val}\) 这两个数在模 \(k\) 意义下绝不可能只有一个为 \(0\)。

因为我目前不知道怎么证明 2，所以我写了一段代码，随机生成一些数据来判断这个结论是否“大概率”是对的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import math
import random as rnd

T = int(input())

def lcm(x, y):
    return x * y * math.gcd(x, y)

cnt_equal_0 = 0
cnt_equal_not_0 = 0
cnt_not_equal = 0
cnt_error = 0

for nw in range (0, T):
    n = 100
    v = []
    Lcm = 1
    for i in range (0, n):
        a = rnd.randint(1, 50)
        Lcm = lcm(Lcm, a)
        v.append(a)
    for i in range (0, 10):
        val = 1
        k = rnd.randint(2, Lcm - 1)
        for j in range (0, len(v)):
            val = lcm(val, v[j]) % k
        if val % k == Lcm % k:
            if val % k != 0:
                cnt_equal_not_0 += 1
            else: 
                cnt_equal_0 += 1
        else:
            if val % k != 0 and Lcm % k != 0:
                cnt_not_equal += 1
            else: 
                cnt_error += 1
                print(v)
print("=============================================")
print("Total", T * 10, "random cases:")
print("Equal but not equals to 0:", cnt_equal_not_0) # A
print("Equals to 0.", cnt_equal_0) # B
print("Not equal but no single 0 exists.", cnt_not_equal) # C
print("Error", cnt_error) # D

经过运行之后得到了一下的结果：

\(n =\) \(V = [1, ?]\) Total cases A B C D
1 100 10 10000 9673 0 327 0
2 100 10 10000 9696 0 304 0
3 100 10 10000 9682 0 318 0
4 100 10 10000 9660 0 340 0
5 100 10 10000 9679 0 324 0
6 100 10 10000 9696 0 304 0
7 100 10 10000 9664 0 336 0
8 100 10 10000 9658 0 342 0
9 100 10 10000 9661 0 339 0
10 100 10 10000 9672 0 328 0
11 100 10 200000 193343 0 6657 0
12 100 50 10000 9931 0 69 0
13 100 50 10000 9924 0 76 0
14 100 50 10000 9940 0 60 0
15 100 50 10000 9933 0 67 0
16 100 50 10000 9936 0 64 0
17 100 50 10000 9932 0 68 0
18 100 50 200000 198583 0 1417 0
19 1000 10 10000 9690 0 310 0
20 100 10 10000 9637 0 363 0
21 100 10 10000 9682 0 318 0
22 100 10 10000 9670 0 330 0
23 100 10 10000 9672 0 328 0
24 10 10 200000 193201 0 6798 0
25 10 50 200000 198283 0 1717 0

因为机子性能原因暂时没跑更大的数据。

可以注意这个结论在值域较小，数字个数较小的情况下是几乎完全正确的。

也可以注意到开头提到的第一个错误结论，它的正确概率随值域的增加而增加，和数字个数近似无关，这个是符合预期的，因为这是 \(\operatorname{lcm}\) 嘛（）

值域为 \([1, 10]\) 的时候大约有 \(96.7\%\) 的正确率，值域为 \([1, 50]\) 的时候大约有 \(99.3\%\) 的正确率。

我们可以推测，当值域越来越大的时候，最上面的错误结论几乎是对的，第二个结论有非常非常大的可能性就是对的。

现在还不会证明所以暂时用这个暴力验证替代，等会证明了就补。

感觉很有意思啊！

upd: 补了，这证明很简单。

Proof（其实是直接粘贴我的题解）

本篇题解是对题解区的一个疑似正确的做法的补充。

本题的做法是简单的。

可以注意到问题等价于给定一个类似 EXCRT 形式的线性同余方程组，问是否有解。

不难想到有解当且仅当 \(k \mid \operatorname{lcm}(a_1, a_2, \dots, a_n)\)。

这个分解一下质因数就好了。

但是在题解区看到了不一样的做法（这篇和这篇）。

大概做法是，判断这个东西是否能被 \(k\) 整除：

\(val = \operatorname{lcm}(\operatorname{lcm}(\operatorname{lcm}(a_1, a_2)\bmod k, a_3), \dots)\bmod k\)

也就是认为 \(val = \operatorname{lcm}(a_1, a_2, \dots, a_n)\)。

思考一下就能知道这个东西的值和 \(\operatorname{lcm}(a_1, a_2, \dots, a_n)\) 不一定相等。

这个“假结论”实际上认为 \(\operatorname{lcm}\) 在模意义下也是具有结合律的

可以构造出特例：\(\{a_i\} = \{6, 9, 2\}, k = 5\)。

因为 \(\operatorname{lcm}(6, 9, 2) \equiv 18 \equiv 3 \pmod 5\)，而 \(\operatorname{lcm}(6, 9) \equiv 3 \pmod 5\) 且 \(\operatorname{lcm}(3, 2) \equiv 6 \equiv 1\pmod 5\)。

但是这种做法仍然能通过本题，而题解区使用该做法的两篇题解均没有说明这个问题。

笔者思考了一下，认为存在以下结论：

记 \(Lcm = \operatorname{lcm}(a_1, a_2, \dots, a_n)\)，则有：

对于任意 \(k\)，满足：

  1. 若 \(k \mid Lcm\)，则 \(k \mid val\)。

  2. 若 \(k \nmid Lcm\)，则 \(k \nmid val\)。

换句话说，\(Lcm, val\) 这两个数在模 \(k\) 意义下绝不可能只有一个为 \(0\)。

如果这个结论是正确的，那么上述的所谓“假做法”应当是正确的。

笔者目前还不会验证这个结论，但是经过暴力枚举，并加以构造验证之后，发现这个猜想有极大可能是对的。

在大约 \(10^7\) 次验证里，仍然没有反例存在，验证过程可以看笔者的博客。

我们可以假设，笔者的猜想应该是几乎正确的。

鉴于这个做法能通过本题，并且在随机的多组数据下仍然正确，所以我们暂且认为它是正确的，如果后续能够严谨证明这个结论，将作补充。

upd：我是 shaber，这结论巨好证。

就是你考虑 \(\operatorname{lcm}\) 的本质是什么，对于 \(\operatorname{lcm}(x, y)\)，它的本质是对于 \(x, y\) 两个数质因子集合之并集当中的每个质因子 \(p_i\)，对 \(p_i\) 在 \(x, y\) 中分别的指数取 \(\max\)。

第一个部分是 Easy 的，考虑第二个部分。

然后如果 \(k \nmid Lcm\)，那么说明对于 \(k = \prod p_i^{c_i}\)，存在至少一个 \(a_j\) 使得 \(p_i\) 在 \(a_j\) 中对应的指数 \(d < c_i\)。

而对于 \(val\)，它的每一步过后都对 \(k\) 取了模，值域为 \([0, k)\)，指数的大小不可能增加，所以如果 \(k \nmid Lcm\)，那么 \(k \nmid val\)。

所以笔者的上述结论是正确的。

另外补充一个东西，虽然和这个想法没有太大关系：

“假结论”在值域越大的情况下正确率越高，在值域为 \([1, 10]\) 的时候大约为 \(96.7\%\)，在值域为 \([1,50]\) 的时候大约为 \(99.3\%\)。

最后更新: August 5, 2023