持续更新\(ing\)
本篇博客包含了本蒟蒻学的数论知识点\(qwq\)
需要有一定基础
定理:若正整数\(a,n\)互质,则\[a^{φ(n)}≡1\ (mod\ n)\]
设集合\(X_1,X_2,……,X_{φ(n)}\)为\(1\)到\(n-1\)中与\(n\)互质的数
那么我们思考下列数的性质:
\[aX_1,aX_2,……,aX_{φ(n)}\]
假设有 \[aX_1≡aX_2\ (mod\ n)\]
那么必须存在
\[aX_1-aX_2≡0\ (mod\ n)\]
\[a(X_1-X_2)≡0\ (mod\ n)\]
但是我们发现\(a,n\)互质,而\(X_1-X_2\)比\(n\)小,根据唯一分解定理可以得出上式不成立
于是我们得出结论:集合中任意两个数模\(n\)余数一定不同
首先,\(a,n\)互质,\(X_1,n\)互质,那么容易得出\(aX_1,n\)互质,那么得到:
\[gcd(aX_1,n)=1\]
运用欧几里得算法得到:
\[gcd(n,aX_1\%n)=1\]
也就是\(aX_1\%n,n\)互质
于是就得到了集合中任意数模\(n\)与\(n\)互质
\[aX_1\%n,aX_2\%n,……,aX_{φ(n)}\%n\]
我们发现这个集合其实排序后就是:
\[X_1,X_2,……,X_{φ(n)}\]
因为那个集合数字满足取值范围在\(1\)到\(n-1\)之间(模了\(n\)),并且每个数与\(n\)互质,且两两不同,并且有\(φ(n)\)个数(性质\(1\),性质\(2\)),这不正是上面这个集合的性质吗?
那么:
\[aX_1 \times aX_2 \times ……\times aX_{φ(n)}≡X_1 \times X_2 \times …… \times X_{φ(n)}\ (mod\ n)\]
变形:
\[(a^{φ(n)}-1)X_1 \times X_2 \times …… \times X_{φ(n)}≡0\ (mod\ n)\]
而\(X_1 \times X_2 \times …… \times X_{φ(n)}\)与\(n\)互质,那么说明
\[a^{φ(n)}-1≡0\ (mod\ n)\]
\[a^{φ(n)}≡1\ (mod\ n)\]
定理:对于质数\(p\),任意整数\(a\),均满足:\(a^p≡a\ (mod\ p)\)
我们把式子稍微变形一下:
\[a^{p-1} \times a≡a\ (mod\ p)\]
\[a^{p-1}≡1\ (mod\ p)\]
根据欧拉定理得到:
\[a^{φ(p)}≡1\ (mod\ p)\]
由于\(p\)是质数,所以\(φ(p)=p-1\),那么上式变为:
\[a^{p-1}≡1\ (mod\ p)\]
于是变回:
\[a^p≡a\ (mod\ p)\]
原文:https://www.cnblogs.com/yexinqwq/p/10392167.html