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