catalog

同余取模快速幂质数互质约数质因子@Delimiter(旧解释)经验谈两数之差也整除加一的特殊性取模累加的周期性取模的唯一集合取模下的四则运算除法的不可约性取模集合 * 互质数互质集合 * 互质数取模集合与互质集合的累积和元素范围取模还原同余转换取模公式计算机取模模板代码取模与整除的对应质数质数与合数质数个数质数特殊表示互质取模下的乘积互质0和1的互质互质数的和与差取模数公约数性质(公约数集合) 等于 (GCD的约数集合)约数性质约数与最小公倍数约数集合的最小公倍数质因子公倍数性质公倍数集合证明

同余

取模

快速幂

210=2∗2∗...2^{10} = 2*2*...210=2∗2∗...

Cuz 10=10102=10002+102=8+210 = 1010_2 = 1000_2 + 10_2 = 8 + 210=10102​=10002​+102​=8+2, 210=(28)∗(22)2^{10} = (2^8) * (2^2)210=(28)∗(22)

----

The property under modulo:

+Under the modulo mmm, the exponentiation aba^bab is equivalent to (a%m)b(a\% m)^b(a%m)b, but absolutely differs from ab%ma^{b \% m}ab%m (e.g., 23(%3)=22^3 (\% 3) = 223(%3)=2, while 23%3=12^{3 \% 3} = 123%3=1

质数

[1,n][1,n][1,n]内的质数个数

The Primes-Count in [1,n][1,n][1,n] is approximately nln⁡n\displaystyle{ \frac{n}{\ln{n} }}lnnn​;

互质

@Delimiter

000与任何正数互质

(0,x)(0, x)(0,x) is Co-Prime ⟺\iff⟺ x∈N+x \in N^+x∈N+

.Notice, (0,0)(0,0)(0,0) is not Coprime;

--

111与任何自然数互质

(1,x)(1, x)(1,x) is Co-Prime ⟺\iff⟺ x∈Nx \in Nx∈N

.As a lemma, the Euler-Function of 111 equals to 111;

@Delimiter

(a,b)(a,b)(a,b)互质的等价代换

(a,b)(a,b)(a,b) is Co-Prime →\to→ GCD(a,b)=1GCD(a,b)=1GCD(a,b)=1

.As discussed above, (1,1)(1,0)(1,1) (1,0)(1,1)(1,0) is Coprime while (0,0)(0,0)(0,0) is not, the a,ba,ba,b in GCD(a,b)GCD(a,b)GCD(a,b) must be NNN and not both 000;

约数

xxx的约数个数

A=p1a1∗p2a2∗...A = p_1^{a_1} * p_2^{a_2} * ...A=p1a1​​∗p2a2​​∗..., then the number of divisors of AAA equals (1+a1)∗(1+a2)∗...(1 + a_1) * (1 + a_2) * ...(1+a1​)∗(1+a2​)∗...;

Proof:

.For any divisor aaa of AAA, every Prime-Factor of aaa must be also a Prime-Factor of AAA;

.Therefore, for every item piaip_i^{a_i}piai​​, there are a1+1a_1 + 1a1​+1 choices: pi0,pi1,pi2,...p_i^0, p_i^1, p_i^2, ...pi0​,pi1​,pi2​,...;

@Delimiter

a∈inta \in inta∈int的最大约数个数

The Maximal-Divisor-Count in the rangeint[1,2147483647][1, 2147483647][1,2147483647] is 153615361536;

.Two numbers a=1745944200/2113511400a = 1745944200/2113511400a=1745944200/2113511400 attains this peak: 23∗33∗52∗7∗11∗13∗17∗(19/23)2^3 * 3^3 * 5^2 * 7 * 11 * 13 * 17 * (19/23)23∗33∗52∗7∗11∗13∗17∗(19/23);

质因子

两数乘积的质因子不变

Let S1S1S1 be the Prime-Factors set of the number aaa, S2S2S2 be the set of bbb; then the Prime-Factors set of a∗ba * ba∗b must be S1∨S2S1 \lor S2S1∨S2;

.In other words, any Prime-Factor of a∗ba * ba∗b must be also a Prime-Factor of at least one of a,ba, ba,b;

.As a corollary, every Prime-Factor of n!n!n! must ≤n\leq n≤n, although the number n!n!n! maybe very large;

@Delimiter

合数的最小质因子

If xxx is not a Prime-Number, then min(pi)≤xmin(p_i) \leq \sqrt{ x}min(pi​)≤x​ (in other words, there must exist a Prime-Factors ppp of xxx such that p∣x∧p∈[1,x]p | x \ \ \land \ \ p \in [1, \sqrt{x}]p∣x∧p∈[1,x​])

.Example: AcWing-198. 反素数

@Delimiter

一个数的质因子个数

+Let SSS be themultisetof all Prime-Factors of an arbitrary-integer aaa, then the maximal S.size()S.size()S.size() is log⁡2(a)\log_2(a)log2​(a) (i.e., S={2,2,...,2}S=\{2,2,...,2\}S={2,2,...,2})

+Let SSS be thesetof all Prime-Factors of an arbitrary-integer aaa, then

.If the type of aaa isint, the maximal S.size()S.size()S.size() is 999 (i.e., S={2,3,5,7,11,13,17,19,23}S=\{2, 3,5,7,11,13,17,19,23 \}S={2,3,5,7,11,13,17,19,23} whose product is223092870; if you proceed multiple the next-prime29then it would be6469693230which is Out-Of-UINT32_MAX)

.If the type of aaa islong long, the maximal S.size()S.size()S.size() is 151515 (i.e., S={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}S=\{2, 3,5,7,11,13,17,19,23,29,31,37,41,43,47\}S={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47} whose product is614889782588491410; ; if you proceed multiple the next-prime53then it would be Out-Of-UINT64_MAX)

@Delimiter(旧解释)

经验谈

两数之差也整除

∀AB,g∣A,g∣B(g∣abs(A−B))\forall{AB}, g | A, g | B(g | abs(A - B))∀AB,g∣A,g∣B(g∣abs(A−B))

加一的特殊性

Fact(x)={y∣y∣x,y>1}Fact(x) = \{ y | \quad y | x, y \gt 1\}Fact(x)={y∣y∣x,y>1}

∀Fact(x)(¬(Fact(x)∣(x+1)))\forall{ Fact( x)}(\neg( \ Fact(x) |(x + 1)))∀Fact(x)(¬(Fact(x)∣(x+1)))

(Fact(x)无法整除: 1)

取模

累加的周期性

对于任意的(A, M), 序列: A, 2 * A, 3 * A, … (即k * A) 在%M下, 是周期性的

注意, 是k * A, 不是AkA^kAk

因为: k * A = (k + M) * A (% M), 所以, M肯定是周期;

如果(A, M)互质, 则 根据: 取模集合性质, 周期是M

M = 8, A = 3 {3, 6, 1, 4, 7, 2, 5, 0 | 3, 6, …}

否则, (A, M)不互质, 则: 周期 < M, 且周期 | M

M = 8, A = 2 {2, 4, 6, 0 | 2, 4, …}

取模的唯一集合

对于取模M, 虽然不同的(取模方式: 正负取模, 非负, 非正), 最终得到的数值范围不同;

比如, 一个数A % M后, 在不同取模方式下, 可能得到: 一个负数N, 可能得到一个整数P

但是, N与P, 他俩在%M意义下, 仍然是相等的!

因此, 在数学证明角度, 你可以假设所有数, 都是[0, M)范围内的;

即所有的Z整数域, 都是在[0, M)范围, 这会使得问题分析更简单;

这一点与选择哪种取模方式无关, 因为都可以对应到[0, M)范围的;

取模下的四则运算

在取模M下, 其唯一集合为[0, M);

给定一个A, 如果A不在唯一集合, 则令A1为A在唯一集合里的对应元素;

给定一个B, 此时要进行(A R B)二元操作, R为四则运算;

则令B1为B在唯一集合里的对应元素;

则原操作 (A R B) % M, 可以等价为: (A1 R B1) % M

R是任意的四则元素; 这样, 可以防止数据溢出; 因为A, B都很大; 但是%M的唯一集合很小;

换句话说, 在取模意义下,

( 加 A) 等价于: ( 加 A%M)

( 减 A) 等价于: ( 减 A%M)

( 乘 A) 等价于: ( 乘 A%M)

( 除 A) 等价于: ( 乘 A的逆元) 等价于: ( 乘 A%M的逆元) … 因为A与(A + k * M)的逆元相同

即在取模意义下的任何数任何操作, 你都可以先对他进行%M操作;

即, 你面临的所有数, 都是唯一集合[0, M)里面的数

除法的不可约性

在%M取模意义下, (以下的=等号, 都代表同余), 令R为二元运算, (A,B,C)为唯一集合[0, M)里面数

若R为(加, 减), 则:

1, 若A = B, 则A R C = B R C; … 证明: A = B意味着: (A,B)同时对应着[0, M)里的同一个元素

2, 若A != B, 则 A R C != B R C … 证明: [0, M)集合, 每个元素 R C后, 依然是[0, M)集合;(相当于钟表, 旋转后依然是相同的)

… 根据抽屉原理, A != B, 则旋转后 依然不同;

3, 若A R C = B R C, 则: A = B … 证明: 根据2定理(p -> q), 则(非q -> 非p)

4, 若A R C != B R C, 则: A != B … 证明: 根据1定理(p -> q), 则(非q -> 非p)

但是, 如果R是(乘, 除), 因为除法为(乘逆元), 所以只考虑乘法:

1, 若A = B, 则A R C = B R C, … 证明: A = B意味着: (A,B)同时对应着[0, M)里的同一个元素

2, 若A != B, 则A R C != B R C这是假的, 证明: (1 != 3)%4, 但(12 = 32 = 2)% 4

… A * C (% M) = A * C + k1 * M, B * C(% M) = B * C + k2 * M

… 如果两者相同, 则: k1 * M + (-k2 * M) = (B - A) * C; 根据裴蜀定理, 只要令: M | (B-A)*C 即可;

… 从这里也有个推理: 2_1: 若A != B 且 (C,M)互质, 则 A R C != B R C;

… … 因为(B-A)<M, (C,M)互质, 所以, (B-A)*C 不会是M的倍数, 即: M | (B-A)*C 恒不成立

3, 若A R C = B R C, 则A = B这是假的, 根据定理2

… 但是, 根据推理2_1: (若p -> q, 则非q -> 非p), 得到推理3_1: 若A R C = B R C, 则A = B 或 (C,M)互质

… 根据推理3_2, 可以得出: 若A R C = B R C 且 (C,M)互质, 则: A = B

4, 若A R C != B R C, 则A != B … 证明: 根据定理1

所以但遇到: C = C*A (% M), 不可以认为: (1 = A); 因为: (C,M)可能不互质;

根据推理3_2: 如果此时有(C, M)互质, 则可以得到(1 = A)

取模集合 * 互质数

在取模M下, [0, M);

给定一个P, 且(P, M)互质, 则[0, M) * P后的集合, 依然等于[0, M)

根据除法不可约去性, 对于(A, B) in [0, M): 若A != B, 且(C, M)互质, 则有: A * C != B * C

比如: M = 10: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3后: [0, 3, 6, 9, 2, 5, 8, 1, 4, 7]7后: [0, 7, 4, 1, 8, 5, 2, 9, 6, 3]

但如果(P,M)不互质, 则不成立;

2 后: [0, 2, 4, 6, 8, 0, 2, 4, 6, 8]

互质集合 * 互质数

上面介绍了: (取模集合) * P 后的集合, 等于(取模集合), (P, M)互质

对于(互质集合), N为M的欧拉函数值, 即{m1, m2, …, mN} 与 M互质;

对于(P, M)互质, 则: (欧拉集合) * P 后的集合, 在%M下, 依然等于(欧拉集合)

证明:

(P, M)互质, N = phi(M), 欧拉集合S1 = {m1, m2, …, mN}

(欧拉集合 * P)的集合S2: {m1 * P, m2 * P, …, mn * P}

证明这两个集合同余;

1, 因为(mi, M)互质, (P, M)互质, 所以(mi * P, M)互质; 即S2的元素,

取模集合与互质集合的累积和

对于取模M集合[0, M), 这些元素, 我们把0去掉, 即[1, M)这些元素,

他们的乘积, 与M, 不一定是互质的;

比如: M=4 : [1 * 2 = 2], 与4不互质;

即(1 * 2 * 3 * … (M-1)) 与 M, 不一定互质;

但是对于M的互质集合(即欧拉函数), 令N为phi(M), [a1, a2, a3, …, aN] 这些元素 与 M互质, 这是欧拉函数的定义;

他们的乘积: a1 * a2 * … * aN 与 M 是互质的

证明: ai里, 都不含有任何M的质因子; 所以ai的乘积里, 也不含任何M的质因子;

元素范围

在%M意义下(如果是正负取模), 所有的数, 都是(-M, …, M)范围内的!

比如, 在M = 5意义下, 给定一个数A = 10, B = 5; 求(A/B)的值

… (A / B = 2), 所以, 其答案为2

这是错误的!

在%M意义下, 不会有一个数是(A = 10), 这已经不在(%M)范围内了

因此所有数, 都要进行取模操作!

即(A % M = 0, B % M = 0), 即(A = 0, B = 0), 进行(A / B)

取模还原

令C = A % B, 我们此时得到了C; (不管%取模: 是正负取模 还是非负取模 还是非正取模)

因为, C = A + k * B, 那么, k是可以求出来的

k = (C - A) / B, 是可以整除的

即A, 向(左/右)跳了 k步(步长B), 到达了C

同余转换

对于取模下的方程: A = B ( % M)

可以转换为: 非取模方程(即严格意义下相等): A + k * M = B

其中k可以求出, 等于: (B - A) / M

也就是, 从A点 往(左/右) 跳了k步(步长M), 到达了B

取模公式

a%b=a−⌊ab⌋∗ba \% b= a - {\lfloor \frac{a}{b} \rfloor}*ba%b=a−⌊ba​⌋∗b

这个式子, 并不简单是一种等价关系; 而是说: %这个取模符号, 就是这样定义的!

即a%b, 本身没有意义; 他的定义, 是依据后面公式得到的

把gcd单独提出来, 会得到:

a%b=(k1%k2)∗g=(k1−⌊k1k2⌋∗k2)∗g其中,g=GCD(a,b),k1与k2互质a \% b = (k1 \% k2) * g = ( k1 - {\lfloor \frac{k1}{k2} \rfloor} * k2) * g \quad 其中, g = GCD(a, b), k1与k2互质a%b=(k1%k2)∗g=(k1−⌊k2k1​⌋∗k2)∗g其中,g=GCD(a,b),k1与k2互质

从此可知, A % B的结果, 一定是(A,B的GCD)的倍数;

计算机取模

计算机对于a%b的操作, 可以认为是调用了下面的函数:

Ll_ Mod( Ll_ _a, Ll_ _b){return _a - Divide( _a, _b) * _b;}

因此, 关键是研究: a/ba/ba/b除法是如何进行的

首先, 介绍: 向上, 向下, 向0取整; 这里的(向), 是基于整数数轴的, (即负数 -> 0 -> 正数)

向上, 就是向右侧, 即偏向大的数

(5.5: 向下和向0取整, 会得到5; 而向上取整会得到6)

(-5.5: 向下取整得到-6; 而向上和向0取整会得到-5)

… 向0取整, 是C++除法采用的; 他有个性质, 对于A和-A, 他们的取整结果的(绝对值), 是相同的; 满足对称性

由于除法有3种, 因此取模也对应的有3种;

对于a%b, 假设b是4, 则3种取模的结果 都会落在区间: [-3, -2, -1, 0, 1, 2, 3]里面;

根据上面的(取模公式), 配合不同的取整, 会得到下面性质:

… 1, 正负取模(即向0取整)时: 如果a是负数, 则落在[-3, -2, -1, 0]区间; 否则, 则落在[0, 1, 2, 3]区间

… 2, 非负取模(即向下取整)时: 不管a是正数负数, 都会落在[0, 1, 2, 3]区间

… 3, 非正取模(即向上取整)时: 不管a是正数负数, 都会落在[-3, -2, -1, 0]区间

模板代码

//> 向0整除Ll_ Divide( Ll_ _a, Ll_ _b){return _a / _b; }//> 向下取整Ll_ Divide( Ll_ _a, Ll_ _b){if( ( _a >= 0 && _b >= 0)|| ( _a <= 0 && _b <= 0)){return _a / _b;}if( _a % _b == 0){return _a / _b;}return _a / _b - 1;}//> 向上取整Ll_ Divide( Ll_ _a, Ll_ _b){if( ( _a >= 0 && _b >= 0)|| ( _a <= 0 && _b <= 0)){if( _a % _b == 0){return _a / _b;}return _a / _b + 1;}return _a / _b;}

我们过去, 向上取整代码会写成: (a + b - 1) / b, 其实他是错误的!

对于正数是正确的;

… 但是比如: 5 / -2, 向上取整后应该是-2; 但是, 上面代码会得到-1, 是完全错误的; (而且-5/-2会得到4…)

对于下取整, 如果除数是2, 则使用>>右移也可以

取模与整除的对应

我们知道取模有3种 (向0取模有正有负, 非负取模, 非正取模), 对应3种整除规则

在进行数学公式递推时, 经常会用到: A % B = A - (A/B) * B

如果全局都是使用的(非负取模), 那么这个公式中, (整除) 就必须是 (向下整除)!

不能是: 使用(非负取模), 而到了整除操作, 却使用C++默认的(向0整除), 这是错的, 因为两者是对不上的;

质数

质数与合数

对于自然数, 除了0 1外, 不是质数 就是合数.

0 1, 既不是质数, 也不是合数

质数个数

1到x之间, 有多少个质数呢? 大约有: x/ln(x)个

换句话说, 每ln(x)个, 就有一个质数;

即, 在[1, x]范围内, 任选一个数, 是质数的概率是: 1/ln(x)

质数特殊表示

质数: 2, 3, 5, 7, 11, 13, 17, 19, …

除了2 3外, 所有质数, 都可以表示为; 6n + 1 或 6n - 1的形式.

比如, 11 = 26 - 1, 19 = 36 + 1;

但反之不然, 4*6 + 1 = 25不是质数.

证明: (因为6n - 1也可以写成: 6n + 5, 即证明: 质数一定可以表示为: 6n + 1, 6n + 5的形式)

6n + 0, 6n + 2, 6n + 4, 都是偶数, 不是质数.

6n + 3 = 3( 2n + 1) 是3的倍数, 不是质数.

互质

AB互质, 当且仅当: AB的公约数只有1

因此可以得到, 1与任何正数, 都互质

取模下的乘积互质

若(A, M)互质, (B, M)互质, 则(A * B, M)也互质 … 注意, 不是说(A, B)互质

反证: 若(A * B, M)存在公约数(质因子)g, 则A * B = k * g; 得到: A或B里, 一定存在g质因子; 矛盾;

所以可以推出: 若干个ai (且(ai, M)互质), 的乘积, 与M互质; (注意, 不是说(ai, aj)互质)

比如, 欧拉集合的累积和, 与M互质;

比如M = 10, 欧拉集合为{1, 3, 7, 9}; 其乘积: 1 * 3 * 7 * 9 = 9 (% M), 其结果9 与 M 互质;

0和1的互质

对于1, 他与(任何 >= 1)的数x, 都互质

… 因为显然不存在一个质因子p, 使得: k1 * p = 1

对于0, 如果严格按照定义出发, (0, 1)互质, 但(0, 任何!=0的数)都不互质;

所以, phi( 1)一般定义为1; (即欧拉函数)

互质数的和与差

A和B互质, 令C = | A - B |, (A,B,C)三个数互质

令A > B, 反证:

如果(A,C)不互质, 令G为(A,C)的GCD, 则B = A - C = G的倍数, 得到(A,B)不互质; 矛盾

如果(B,C)不互质, 令G为(B,C)的GCD, 则A = B + C = G的倍数, 得到(A,B)不互质; 矛盾

若令C = A + B, 则(A,B,C)三者也互质;

证明也可以用反证法;

取模数

(A,B)互质, 令C = A + k * B, 则: C与B一定互质, 但C与A 不一定互质

我们从上面定理知道, 如果(A,B)互质, 则(A,B,|A-B|)三者互质;

这里是+k, 上面定理是k = -1的情况; 可以说, 这个定理是上面的一般化;

证明: (C与B互质)

反证法, 若(B,C)不互质, 则存在公约数G, 可以反推出, A一定也含有G, 与(A,B)互质矛盾;

证明: (C与A不一定互质)

因为C = A + k * B, 对于任意A的>1的约数f, 只要令k等于f的倍数, 此时: C = f的倍数, 而A也是f的倍数;

比如, (A=15, B=2互质), 但是(令k=A=15, 则: C = A + k * B = 15 + 15 * 2 = 45), 得到(A,C)不互质;

但不是绝对的, 取决于k, 可能(A,C)互质, 可能不互质

引理: 可以发现, C的性质, 就是A%B的公式; 因此, (A%B)与B互质, 而与A不一定互质;

比如: (A = 15, B = 4互质), 但是(C = A % B = 15 - 3 * 4 = 3)与A不互质, 但与B互质;

这也是为什么在求GCD时, 是从(A, B)转换为(A%B, B), 而不是(A%B, A)

公约数

任意两数AB, 满足x | A 且 x | B, 则x为AB的公约数;

满足这样的x很多, 所以AB的公约数 是一个集合; 其最大的元素, 为最大公约数GCD

性质

(公约数集合) 等于 (GCD的约数集合)

令G为A与B的GCD, 则AB的任意一个公约数g, 一定是G的约数;

比如: (24 与 36)的公约数集合是: {12, 6, 4, 3, 2, 1}, 其GCD(12)的约数集合也是: {12, 6, 4, 3, 2, 1}

等价于证明: g与G的GCD, 一定等于g反证 (即存在g不是G的约数, 即g与G的GCD 不等于g):令h为(g与G的GCD), 则g = kg * h, G = kG * h; (且h != g 即kg > 1, kg与kG互质)因为g | A, g | B, G | A, G | B; 根据公倍数的概念: A是g与G的公倍数; B是g与G的公倍数; (简称为: A和B 是 g和G 的公倍数)比如, a 是 b和c 的公倍数, 则会有: b和c的LCM 是 a 的约数; [证明参见: 公倍数集合](#0)则此时, (g和G的LCM) 是 A的约数; (g和G的LCM) 是 B的约数;则: (g和G的LCM) 是 A和B的 公约数;而g和G的LCM = kg * kG * h = kg * G, 因为kg > 1, 所以, g和G的LCM > G因为, G是最大的公约数, 而现在这个(g和G的LCM) 也是公约数, 还比G大; 矛盾

因此, 任意两数(A,B)的公约数集合, 只与其GCD有关, 与AB无关;

比如, A = k1 * G, B = k2 * G, 只要(k1,k2)互质, 则(A,B)的GCD等于G, 则其公约数集合都相同; 不管(k1,k2)等于多少

约数

满足x | A, 则x为A的约数

性质

约数与最小公倍数

如果a | A, 则(a,A)的LCM 等于 A

约数集合的最小公倍数

A的约数集合中的 任意两个元素ab, 其LCM一定属于该集合里

比如12的约数集合{12, 6, 4, 3, 2, 1}, 4 6的LCM为12; 2 3的LCM为6

证明: 因为a | A, b | A; 即A是ab的公倍数;

因为LCM一定是公倍数的约数

因此, 任意两数的LCM 一定是 A的约数;

质因子

满足x | A 且 x是质数, 则x为A质因子

公倍数

任意AB, 满足A | C 且 B | C, 则C为AB的公倍数;

正式的, 满足: C = x * A = y * B, 且(x,y)均为整数, 则C就是(A,B)的一个公倍数

最简单的例子, A * B这个数, 就是(A,B)的一个公倍数

比如, (4, 6)其公倍数有: (C = 0: 则(x,y) = (0,0)) (C = 12: 则(x,y) = (3, 2)) (C = -12: 则(x,y) = (-3, -2)) …

实际上, 其公倍数集合是: k * LCM, 这里的最小公倍数LCM等于12

满足这样C很多, 因此AB的公倍数 是一个集合(无限集合); 其中, 最小的(正数) 为最小公倍数LCM(least common multiple)

比如(5, 10), 其LCM为10; (4, 6), 其LCM为12

LCM算法

令A = ka * G, B = kb * G (G为AB的GCD, ka与kb互质)

则, LCM = ka * kb * G

其等价于: ka * kb * G * G / G = a * b / G

性质

公倍数集合

a | A 且 b | A, 则有: ab的LCM | A

即A是ab的公倍数, 证明: 公倍数 一定是 LCM的倍数;

证明: 令a = ka * g, b = kb * g (g为ab的GCD, ka与kb互质)

则, A = k1 * a = k1 * ka * g;

A = k2 * b = k2 * kb * g;

合并后, A = k * ka * kb * g = k * LCM

即: 公倍数 一定是 LCM的倍数; LCM一定是公倍数的约数;

即: AB的公倍数集合 是形如: { k * LCM | k为任意整数}, 比如{ …, -LCM, 0, LCM, …}

证明

REDIRECT_ID = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

如果觉得《`Computer-Algorithm` 数论基础知识 (同余 取模 快速幂 质数 互质 约数 质因子)》对你有帮助，请点赞、收藏，并留下你的观点哦！