数论还是太难了QWQ

这篇blog是我写的最认真的了，我把我的干货全放这了

还是一样的，先讲讲数论，以前你肯定学过

就是数学知识而已，再细讲的话……我不废了

模块1:整除

这是一个大整数▶30

这是一个小整数▶3

知众所众，3*10=30，30/3=10;

就可以说3就能整除30，换做其他整数也是适用的，记作3|30 挺像“或”的

其实我觉得倒不如这么说：

30除以3没有余数，那么3就能整除30

整除还有一些性质：

1.传递性

如果a|b,b|c,那么a|c (没座，就是你想的那种传递性) 我的理解:

证明：

∵a|b,b|c

设b = a * m,c = b * o

∴c = a * m * o

∴a|c

实数样例👇

3|30 是因为 30 = 3 * 10 = 3 * 2 * 5

30|60 是因为 60 = 30 * 2 = 3 * 2 * 5 * 2

所以3也能整除60

---

性质2

如果a|b && a|c (dongdedoudong),那么a|(b * m + c * o),but m && o 必须 是 整数

我的理解:

3|30且3|60

因为30是3的倍数，所以30乘以整数m还是3的倍数

同理，60是3的倍数，所以60乘以整数o还是3的倍数

而两个3的倍数相加，仍然是3的倍数

所以30 * m + 60 * o仍是3的倍数

意思就是说3|30 * m + 60 * o

---

性质3

只要mod是一个≠0的数，那么a|b就==(a * m)|(b * m)

我的理解:

我们先设mod为5

3|30 是因为 30 = 3 * 10

15|150是因为 150 = 15 * 10 = 3 * 5 * 10

150又= 30 * 5，证明了这个结论

你懂了吗？

---

性质4

我们先写证明过程

a|n且b|n(已知)

∵a|n且b|n

∴(a * b)|(b * n)且(a * b)|(a * n)(由性质3得)

∴（a * b)|(a * n * m + b * n * o)(由性质2得)

a * n * m + b * n * o变式为(a * m + b * o) * n(由乘法分配律得)

如果a * m + b * o = 1 时

(a * m + b * o) * n = 1 * n = n

∴ (a * b)|n

结论:设整数m、o,a|n且b|n,如果(a * m + b * o) = 1,那么(a * b)|n数论肯定得用数学啦

---

性质5

若a = m * b + c,想要b|a,首先要满足b|c

我的理解

m * b肯定是b的倍数

其次，a = m * b + c

所以如果c不是b的倍数的话，那么m * b + c 也就不是b的倍数，相反亦是如此

very useful 的整除小技巧(其实就是小学都学过的)

判断2的倍数，就看最后1位，只要最后一位是2的倍数，整个数就是2的倍数，原因:

整十的数都是2的倍数，因为10就是2 * 5，所以最后一位决定了整个数是否是2的倍数;

---

判断4的倍数，就看最后2位，只要最后二位是4的倍数，整个数就是4的倍数，原因:

整百的数都是4的倍数，因为100就是4 * 25，所以最后二位决定了整个数是否是4的倍数;

---

判断8的倍数，就看最后3位，只要最后三位是8的倍数，整个数就是8的倍数，原因:

整千的数都是8的倍数，因为1000就是8 * 125，所以最后三位决定了整个数是否是8的倍数;

---

怕你看上面的太累，总结一个规律，想判断一个数是否为2的N次方的倍数，那么就看这个数最后N位，只要最后N位是2的N次方的倍数那么整个数就是2的N次方的倍数！！经本人认证，2的10次方也能够奏效，不是我吃(你猜吃啥)

---

判断3的倍数，就把这个数的所有数位上的数相加，如果这个总和是3的倍数，那么这个数就是3的倍数，原因有点长，不想看可以跳过:

这是一个三位数的abc

可变式为a * 100 + b * 10 + c

原式 = a * (99 + 1) + b * (9 + 1) + c

= a * 99 + a + b * 9 + b + c(由乘法分配律得)

= (a * 99 + b * 9) + (a + b + c)

由于a * 99 + b * 9 是3的倍数，所以只要后面的a + b + c是3的倍数，那么三位数abc就是三的倍数

同理，判断9的倍数也是看所有数位的总和，原因可以看上面3的倍数的原因就能理解了

---

判断能被7，11，13整除的数，就把这数的后三位组成的数与后三位以前的数的差拿出来算，只要这个差是7，11，13的倍数，那么整个数就是7，11，13的倍数(7，11，13指的是7，11或13，而不是7，11和13)，原因:

度哥太权威了，没搜到……

---

7，11，13单拎出来还各有一种方法

如果本数没有高达3位那么变态的数据，那么就可以除掉个位，剩下的位组成的数减去个位的数的2倍，如果这个差是7的倍数，那么整个数就是7的倍数

---

想看看一个数是否为11的倍数？把这个数的奇数位数字之和与偶数位数字之和的差算出来吧，如果该差是11的倍数，那么整个数就是11的倍数 这段怎么和前面的不一样？

---

13的倍数也很好找，先把个位去了，剩下的数位组成的数加上个位的4倍，这个和是13的倍数，那么这个数就是13的倍数

---

如果用了上面所有这些方法算出来的数太大了，无法直接看出是否为某数的倍数，你可以重复使用这些方法，直到你能算出为止

---

老师还讲了整数的性质和整除的性质，

整数的性质

1.就是任何一个正整数mod都可以写成2^n+l的形式，其中n为非负整数，l为任意奇数(这很正常，这写法质数合数还是1都适用，我已经试过了)

2.如果a>1，那么a除了1以外的最小因数q一定是个质数，如果q≠a，那么q<=√a

我们在C++中判断质数的时候，一直在for循环中增加这个条件i<=√a，以前不知道这是为啥，现在窝瓜懂了

3.任何整数一定能够写成不同质因数的次方相乘的式子，并且具有唯一性//不考虑顺序//(证明吗？你在质因数分解时难道还能每次分出不同结果？除非你算错了)for example,20=2²+5¹

---

整除的性质

1.如果a|b且a|c，那么b与c的和或差都能被a整除

证明：

设b = a * m,c = a * o

∴b - c = a * m - a * o

∴b - c = a * (m - o)(由乘法分配律得)

∴b - c 是a的倍数

2.如果b|a,c|b,那么c|a性质1来了

3.如果(b * c)|a,那么b|a且c|a

证明：

∵(b * c)|a

∴b,c均为a的因数

∴b|a且c|a

4.如果b|a且c|a,且b与c互质，那么(b * c)|a

证明：

∵b|a且c|a

∴b与c是a的因数

∵b与c互质

∴b * c也是a的因数

5.如果b|a,那么bm|am👆性质1来了

*6

---

说完了没余数的，再看看有余数的

模块2:同余

讲同余前，先讲讲带余除法，学名欧几里得除法(想不到小学学的玩意儿还有这么带派的名字，只能说太带派了)

÷÷ 带派不

(/) 老铁

÷/…………………/

a/b没法整除，就分为了两个数，m和od，能满足

a = b * m + od

其中，m是a/b的商的整数部分，od就是a/b的余数

而带派余除法的写法长这样

a ÷ b = m……od

讲完带余除法，咱们再讲讲余数

---

余数三大定理(你不会让我给一个定理写证明过程的吧)

1.余数的加法定理

a与b的和除以c的余数，等于a除以c的余数与b除以c的余数之和(或这个和除以c的余数)

2.余数的减法定理

a与b的差除以c的余数，等于a除以c的余数与b除以c的余数之差

3.余数的乘法定理

a与b的乘积除以c的余数，等于a除以c的余数与b除以c的余数之积(或这个积除以c的余数)

---

现在才开始讲同余，实在是莫得办法ㄟ( ▔, ▔ )ㄏ

先讲定义：

如果a与b除以c的余数相同，那么就说a,b对于模c同余，式子表示为a == b(mod c)👈这个式子叫做同余式(读作a 同余于 b 模 c)

再讲一个推论：

如果a == b(mod c),那么c|(a - b)

推论过程如下

∵a == b(mod c)

设a = m * c +r,b = o * c + r

a - b = m * c + r - o * c - r

= m * c - o * c

=(m - o) * c

∴c|(a - b)

3.余数判别法

众所众知，被除数太“慈善”(!CiShan)，特地送我们好多个位数时，我们用长除法(就是短除法的反义词，简称正常除法)也很难求余，所以我们可以找到一个数R，让R同余于被除数 模 除数，从而通过R来找到余数

这篇主要就是讲一下我的见解，所以这篇blog没有题解，但是这篇blog绝对是我的匠心巨作，都看到这了，给个免费的收藏不过分吧