数论篇

作者：

糖豆 , 2021-01-13 11:16:38 , 阅读 53

数论的整体学习思路

死磕大神的博客

https://www.cnblogs.com/ShuraK/p/7905790.html

一、李永乐老师的一些数论知识讲解

讲最大公约数+面积求法+辗转相除法（欧几里得定理）+裴蜀定理（贝祖数）+扩展欧几里得算法
https://www.ixigua.com/i6755369627741585924/

（1）什么是最大公约数，最常见的求法是分解质因数
（2）面积求法+辗转相除法的背后是欧几里得定理，用来求最大公约数。

（3）裴蜀定理（用途:可以判断一个不定方程是不是有整数解）
ax+by=c 当g | gcd(a,b)，方程有整数解
(4) 扩展欧几里得(用途：1、可以用来计算最大公约数，可以计算出方便ax+by=c的一组解，一般称为特解)
扩展欧几里得是非常有用的：
https://blog.csdn.net/weixin_43879181/article/details/95481349

裴蜀定理
例题： https://www.luogu.com.cn/problem/P4549#sub

[二、费马小定理]

(1)若p是素数且a是整数则a^p≡a(mod p)，
(2)特别的若a不能被p整除(a与p互质)，则a^(p-1)≡1(mod p)。

https://www.jianshu.com/p/e3df7e5d9c38
https://haokan.baidu.com/v?vid=3032136584887251853
https://www.zybang.com/question/5942c2eee9d7a66352ddf4015a4db429.html
https://haokan.baidu.com/v?vid=6635367936852436463

2730=2 * 3 * 5 * 7 * 13

这道例题的理解

(1) n^13-n = n(n-1)(n+1)(n^4 + n^2+1)(n^6 + 1) 而n(n-1)(n+1)可以被6整除，故原式可以被2*3整除。
n、(n-1)、(n-2)中三个相连的自然数,其中一定有一个数是2的倍数,还有一个数是3的倍数,所以n(n-1)(n-2) (n>=3) 能被6整除

(2) n^13-n = n(n^4 - 1)(n^8 + n^4 + 1) 由费马小定理知，(n^4 - 1)可以被5整除，故原式可以被5整除。
(3) n^13-n = n(n^6 - 1)(n^6 + 1) 由费马小定理知，(n^6 - 1)可以被7整除，故原式可以被7整除。
(4) n^13-n = n(n^12 - 1) 由费马小定理知，(n^12 - 1)可以被13整除，故原式可以被13整除。
所以，原式可以被2 * 3 * 5 * 7 * 13=2730整除。

用途：
https://article.itxueyuan.com/Ow5We6