# [数论学习笔记01]完系/同余最短路/费马小定理/扩欧/中国剩余定理
### 每日蒟蒻小故事(1/1)
蒟蒻带了一本崭新的笔记本到S组.
他发现这一节课居然在学习数论.
"听不懂,求讲解!" 蒟蒻说.
大佬邪魅一笑,并未理会.
蒟蒻只能一边听着老师的讲解,一边努力地记着笔记.
"什么是完全剩余系啊!"
### 什么是完全剩余系？
从模n的每个剩余类中各取一个数，得到一个由n个数组成的集合，叫做模n的一个完全剩余系。
由完全剩余系的定义,我们可以给出以下两条引理:
- 引理1 若a,b,c为任意3个整数,m为正整数,且gcd(,.c)=1,则当a·c≡b·c(mod m)时，有a≡b(mod m).
- 引理2 设m是一个整数且m>1,b是一个整数且gcd(m,b)=1.若a[1],a[2],...,a[m]是模m的完系,则b·a[1],b·a[2],...,b·a[m]也为模m的完系.
"可是还是过不了第一题……"
没关系,把下一个知识点学会了就行了!
"那快讲啊!"
### 费马小定理
(贴一个百度百科的介绍)
构造p的完系p={1,2,3,...,p-1}.
由引理2得A={a,2a,3a,..,(p-1)a}也为p的完系.
由完系性质,1*2*3*...*(p-1)≡a*2a*3a*...*(p-1)a(mod p)
即(p-1)!≡(p-1)*a^(p-1)(mod p)
易知gcd((p-1)!,p)=1,可约去(p-1)!
得a^(p-1)≡1(mod p)
"啊……"
标签：剩余,...,01,定理,引理,完系,mod From： https://www.cnblogs.com/firepaw/p/18002476