风灵无畏OI

【质数】

1.3.1 素数定理

1.3.2 费马小定理

【定义】

【证明】（来自百度百科，部分为自己编写）

引理1

          若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(modm)时,有a≡b(modm)

          证明：a*c≡b*c(mod m)可得a*c–b*c≡0(mod m)可得(a-b)*c≡0(mod m)

                    因为(m,c)=1即m,c互质,c可以约去,a– b≡0(mod m)可得a≡b(mod m)

                   //另一种证明过程，见下面这片博客的重要定理第10,11点

                  //https://tzdyy.lofter.com/post/1e3cd119_e213ffd

引理2

　　    设m是一个整数,且m>1,b是一个整数且(m,b)=1.如果a1,a2,a3,a4,…am是模m的一              个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系.

           //剩余系：https://baike.baidu.com/item/剩余系?sefr=cr

　　 证明：若存在2个整数b*a和b*a[j]同余即ba≡ba[j](mod m),

                   根据引理1则有a≡a[j](mod m).根据完全剩余系的定义可知这是不可能的,

                    因此不存在2个整数b*a和b*a[j]同余.

                   所以b*a[1],b*a[2],b*a[3],b*a[4],…ba[m]构成模m的一个完全剩余系.

                

                    这样就证明了费马小定理。

【例题】

题目描述：

例题讲解：

另外一种方法：

（此处用到了欧拉定理，后面会提到）

题目链接：https://pyoj.ml/problem/67（这题部分分是用费马小定理做的，要AC得用到欧拉定理）

源代码：

             pascal：https://code.csdn.net/snippets/2277186

             c++：https://pyoj.ml/submission/2498（本组的一位大佬的题解）

1.3.3 欧拉定理

https://baike.baidu.com/item/欧拉函数?sefr=enterbtn

//这里有另外一篇博客：https://blog.csdn.net/qq_24451605/article/details/47045279

1.3.4 筛法