首页 > 其他 > 详细

数论总结

时间:2019-02-17 20:01:54      阅读:240      评论:0      收藏:0      [点我收藏+]

持续更新\(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)}\]

\((1)\)、集合中任意两个数模\(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\)余数一定不同

\((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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!