定义
如果正整数 (n) 和 整数 (a) 互质，那么就有
[a^{varphi left( n ight)}equiv 1 left( mod n ight) ]其中欧拉函数(varphi left( n ight)) 为 ”小于 (n) 的正整数中并且与 (n) 互质的数的个数“。
互质：即自然数 (X) 和 (Y) 的最大公因/约数为1 栗子：7 和 3 公约数只有1。
( equiv ): 同余关系。例如：(X) ( equiv ) (Y) (mod (n)), 即 (X) mod (n) 和 (Y) mod (n) 的余数相同。
基础知识
1.唯一质数分解定理（Unique factorisation theorem）
任何一个正整数 (n) > 1 都可以唯一地分解为一组质数的乘积
其中 (
e_1,e_2,cdots in N
) ，我们称这个分解为 (n)的标准分解
解释：因为一个数肯定是由合数和质数构成的，合数又可以分解成质数和合数，最后递归下去就会变成质数的乘积，最后化成了质数相乘的形式。如 (100
ightarrow 4 imes 25
ightarrow 2^2 imes 5^2)
2.最大公因/约数（GCD）、最小公倍数 （LCM）、互质（Coprime）
因数：指整数 a 除以 b (b!=0) 的商正好是整数而没有余数，我们就可以说 b 是 a 的因数。
公因数：两个或多个数共同都有的因数叫做公因数.
最大公因数：两个或多个数都有的因数里最大的叫做最大公因数。
倍数：一个整数能够被另一个整数整除，这个整数就是另一整数的倍数。如同上面的因数概念，a 即为 b的倍数。
公倍数：两个或多个都有的倍数叫做公倍数。
最小公倍数：两个或多个数都有的倍数里最小的叫做最小公倍数。
互质：对于整数 (a,b) 我们记 ( gcdleft( a,b ight) ) 和 ( lcmleft( a,b ight) ) 为 (a,b) 的最大公因数和最小公倍数，有时候我们会直接把他们简写为 ( left( a,b ight) ) 和 ( left[ a,b ight] ) 。如果 ( gcdleft( a,b ight) =1 ) ，我们称 (a,b) 互质，也就是说他们没有任何共同的质因数。Attention: 1不为质数/素数。
基本性质
- ( gcdleft( a,b ight) =gcdleft( apm b,b ight) )
- ( gcdleft( na,nb ight) =ngcdleft( a,b ight) )
- ( gcdleft( a,b ight) =frac{acdot b}{lcmleft( a,b ight)} )
- 裴蜀定理：存在整数 (x,y) 使得 ( gcdleft( a,b ight) =ax+by )
3.同余关系（Congruence relations）
整数 a 和 b 除以 n 的余数相同，则称 a, b 模 n 同于，记作
如果对于整数 ( a_1,a_2,b_1,b_2 )
那么可以它们进行相加或相减
同时也能进行相乘
综上两条性质，即如果 (aequiv b left( mod n ight))，那么
Attention: P(x) 为任意整数多项式。
这里需要注意的一点是，如果整数 ( a,b,c ) 满足
那么只有当 (n,c) 互质时才可以把两边的 (c) 直接约掉，得到 (aequiv b left( mod n ight)) ，更一般的
4.同余类(Residue class)、完全剩余系(Complete residue system)、缩剩余系(Reduced residue system)
通过一个整数模 (n) 的余数，我们可以把所有整数分成 (n) 类，记
为模 (n) 余 (r) 的同余类（也叫剩余类）。
举个例子
是模 10 余 4 的同余类
从 ( 0_n,1_n,2_n,cdots ,overline{left( n-1 ight) }_n ) 中各挑出一个数就组成了一个模 (n) 的完全剩余系（完系） ( R_n )
其中 ( r_0epsilon 0_n,r_1epsilon 1_n,r_2epsilon 2_n,cdots ,r_{n-1}epsilon overline{left( n-1 ight) _n} )
换言之， (n) 个模 (n) 互相不同余的整数组成一个模 (n) 的完全剩余系。
我们称 ( R_n=left{ 0,1,cdots ,n-1 ight} ) 为模 (n)的最小非负完全剩余系（最小非负完系）。
取一个模 (n) 的完全剩余系 ( R_n ) ，取出里面所有和 (n) 互质的数，这些数组成一个模 (n) 的缩剩余系（缩系），记为 ( varPhi _n )
其中 ( varphi left( n ight) ) 是序言里提到的欧拉函数，代表「小于 (n) 的正整数中和 (n) 互质的数」的个数。
栗子： 假设( R_6=left{ 36_0,7_1,14_2,15_3,22_4,23_5 ight} ) 为模6的完全剩余系，下标为余数，从里面找出所有和 6 互质的数，组成一个 模 6 的缩剩余系 ( varPhi _6=left{ 7_1,23_5 ight} )。我们可以发现1 和 5 也刚好是 ( varphi left( 6 ight) =2 ) 结果中的两个与其互质的数。
注意，因为 ( gcdleft( c_i,n ight) =gcdleft( c_i+n,n ight) =1 ) ，每一个模 (n) 的缩剩余系有相同数量的元素（缩剩余系中的每一个数所属的同余类是确定的，所以总共有确定的 $varphi left( n ight) $ 个同余类）
如果缩剩余系 (varPhi _n=left{ c_1,c_2,cdots c_{varphi left( n ight)} ight}) 满足 ( 1le c_1,c_2,cdots c_{varphi left( n ight)}le n-1 ) ，那么称其为模 (n) 的最小正缩剩余系（最小正缩系）。
5.欧拉函数(Euler's totient function)
对于正整数 (n) ， $varphi left( n ight) $代表「小于 (n) 的正整数中和 (n) 互质的数」的个数，这个函数被称为欧拉函数；欧拉还告诉我们
其中 (p) 取到 (n) 的所有质因数
所以我们可以很方便的计算一个正整数欧拉函数的值（根据唯一质数分解定理），比如
欧拉定理的证明
考虑模 (n) 的最小正缩系
已知 ( gcdleft( a,n ight) =1 ) 我们在 ( varPhi _n ) 的每一个元素前面都乘一个 (a)
利用反证法可以证明 ( avarPhi _n ) 也是一个模 (n) 的缩系（其元素的同余类的顺序有可能会改变，但是这并没有任何影响），假设
其中 ( i e j ) ，因为 (a,n) 互质可以将两边消去 (a)，那么就得到
这是不可能的，因为 ( varPhi _n ) 中的元素互相模 (n) 不同余，矛盾啦！
接下来的思路就比较清晰了，因为 ( varPhi _n ) 和 ( avarPhi _n ) 都是模 (n) 的缩系
显然 ( gcdleft( n, prod_{i=1}^{varphi left( n ight)}{c_i} ight) =1 ) 所以可以两边消去它
补充说明： 因为 (
varPhi _n
)为最小正缩系【{1，2，3，...，n-1}最小完全剩余系中挑选的与n互质的数组成】， 即 (
aPhi _nequiv Phi _nleft( mod n
ight) =Phi _n
) 。那为什么两个缩系各自的乘积取n得模依旧相等？ 例如(
Phi _3=left{ 1,2
ight}
) 和 (
2Phi _3=left{ 2,4
ight}
) 我们发现 ，(
1 imes 2 mod 3=2 imes 4 mod 3 = 2
) 且2，8都3互质。
证毕！
计算
求正整数 ( 3^{83} ) 的最后两位数
按照定义：如果正整数 (n) 和 整数 (a) 互质，那么就有
其中欧拉函数(varphi left( n ight)) 为 ”小于 (n) 的正整数中并且与 (n) 互质的数的个数“。
a = 3, n = 100(因为取后面两位数，即mod 100), 且 3 和 100 互质，因此
参考
对这位的大神仔仔的数学小屋的文章进行了一丢丢修改，只是为了方便自己理解。