博主是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。 我整理成一个系列：初等数论，方便检索。
欧拉函数本身，其实就是一个简单描述与元素互素个数的函数，但是它涉及、以及由它推出的定理（欧拉定理、费马小定理）很重要。我会从一些小概念、小定理推到欧拉定理、费马小定理等比较难的定理。
同 余 类 ： m ∈ N + , ∀ i ∈ Z , 记 : [ i ] = 同余类：m\in N^{+},{\forall}i \in Z,记: [i]= 同余类：m∈N+,∀i∈Z,记:[i]= { x : x ∈ Z , x ≡ i ( m o d m ) x:x\in Z,x\equiv i(mod m) x:x∈Z,x≡i(modm) } 既 约 同 余 类 ： ( i , m ) = 1 + 同 余 类 定 义 既约同余类：(i,m)=1+同余类定义 既约同余类：(i,m)=1+同余类定义 如 ： 整 数 6 的 完 全 剩 余 系 ： [ 0 ] , [ 1 ] , [ 2 ] , [ 3 ] , [ 4 ] , [ 5 ] ; 既 约 剩 余 系 ： [ 1 ] , [ 5 ] 如：整数6的完全剩余系：[0],[1],[2],[3],[4],[5];既约剩余系：[1],[5] 如：整数6的完全剩余系：[0],[1],[2],[3],[4],[5];既约剩余系：[1],[5]
小 于 m ， 且 与 m 互 素 的 整 数 个 数 ， 写 作 φ ( m ) 小于m，且与m互素的整数个数，写作\varphi(m) 小于m，且与m互素的整数个数，写作φ(m)
完 全 剩 余 系 ： m 个 整 数 a 1 , a 2 , a 3 … a m , 整 数 模 m 不 同 余 完全剩余系：m个整数a_1,a_2,a_3…a_m,整数模m不同余 完全剩余系：m个整数a1,a2,a3…am,整数模m不同余 既 约 剩 余 系 ： φ ( m ) 个 整 数 b 1 , b 2 , … b φ ( m ) 既约剩余系：\varphi(m)个整数b_1,b_2,…b_\varphi(m) 既约剩余系：φ(m)个整数b1,b2,…bφ(m) 如 ： 整 数 6 的 完 全 剩 余 系 ： { 0 , 1 , 2 , 3 , 4 , 5 } ; 既 约 剩 余 系 { 1 , 5 } 如：整数6的完全剩余系：\{0,1,2,3,4,5\};既约剩余系\{1,5\} 如：整数6的完全剩余系：{0,1,2,3,4,5};既约剩余系{1,5}
证 明 ： 若 x 遍 历 m 的 一 个 完 全 剩 余 系 ， 则 x = { a 0 , a 1 , a 2 , … a m − 1 } 且 ∀ a i , a j 有 a i 和 a j 模 m 不 同 余 , 有 a x + b = { a a 0 + b , a a 1 + b , … a a m − 1 + b } , 我 们 只 需 要 证 明 集 合 a x + b 中 每 个 整 数 模 m 不 同 余 。 反 证 法 ： 假 设 存 在 两 个 整 数 a i , a j 使 得 a a i + b ≡ a a j + b ( m o d m ) , 那 么 a ( a i − a j ) ≡ 0 ( m o d m ) → m ∣ a ( a i − a j ) 又 因 为 ( a , m ) = 1 , 所 以 m ∣ a i − a j , 即 a i 与 a j 模 m 同 余 ， 产 生 矛 盾 ， 证 毕 。 证明：若x遍历m的一个完全剩余系，则x=\{a_0,a_1,a_2,…a_{m-1}\}且{\forall}a_i,a_j有a_i和a_j模m不同余,\\ 有ax+b=\{aa_0+b,aa_1+b,…aa_{m-1}+b\},我们只需要证明集合ax+b中每个整数模m不同余。\\ 反证法：假设存在两个整数a_i,a_j使得aa_i+b\equiv aa_j+b(mod m),\\ 那么a(a_i-a_j)\equiv 0(mod m)\rightarrow m\mid a(a_i-a_j)\\ 又因为(a,m)=1,所以m\mid a_i-a_j,即a_i与a_j模m同余，产生矛盾，证毕。 证明：若x遍历m的一个完全剩余系，则x={a0,a1,a2,…am−1}且∀ai,aj有ai和aj模m不同余,有ax+b={aa0+b,aa1+b,…aam−1+b},我们只需要证明集合ax+b中每个整数模m不同余。反证法：假设存在两个整数ai,aj使得aai+b≡aaj+b(modm),那么a(ai−aj)≡0(modm)→m∣a(ai−aj)又因为(a,m)=1,所以m∣ai−aj,即ai与aj模m同余，产生矛盾，证毕。
设 m 1 , m 2 是 两 个 互 素 正 整 数 ， x 1 , x 2 分 别 遍 历 m 1 , m 2 的 完 全 剩 余 系 ， 则 m 2 x 1 + m 1 x 2 遍 历 模 m 1 , m 2 的 完 全 剩 余 系 。 设m_1,m_2是两个互素正整数，x_1,x_2分别遍历m_1,m_2的完全剩余系，则m_2x_1+m_1x_2遍历模m_1,m_2的完全剩余系。 设m1,m2是两个互素正整数，x1,x2分别遍历m1,m2的完全剩余系，则m2x1+m1x2遍历模m1,m2的完全剩余系。证 明 ： x 1 , x 2 分 别 遍 历 m 1 , m 2 的 完 全 剩 余 系 ， 则 x 1 = { a 0 , a 1 , … a m 1 − 1 } , x 2 = { b 0 , b 1 , … … , b m 2 − 1 } , x 1 中 有 m 1 个 元 素 ， x 2 中 有 m 2 个 元 素 ， m 2 x 1 + m 1 x 2 中 有 m 1 m 2 个 元 素 ， 现 在 只 需 证 这 m 1 m 2 个 元 素 彼 此 模 m 1 m 2 不 同 余 。 证明：x_1,x_2分别遍历m_1,m_2的完全剩余系，则x_1=\{a_0,a_1,…a_{m_1-1}\},x_2=\{b_0,b_1,……,b_{m_2-1}\},x_1中有m_1个元素，x_2中有m_2个元素，m_2x_1+m_1x_2中有m_1m_2个元素，现在只需证这m_1m_2个元素彼此模m_1m_2不同余。 证明：x1,x2分别遍历m1,m2的完全剩余系，则x1={a0,a1,…am1−1},x2={b0,b1,……,bm2−1},x1中有m1个元素，x2中有m2个元素，m2x1+m1x2中有m1m2个元素，现在只需证这m1m2个元素彼此模m1m2不同余。 反 证 法 ： 假 设 存 在 x i , x j , y i , y j 使 得 m 2 x i + m 1 x j 与 m 2 y i + m 1 y j 模 m 1 m 2 同 余 , 其 中 x i , y i 属 于 x 1 , x j , y j 属 于 x 2 , 即 m 2 x i + m 1 x j ≡ m 2 y i + m 1 y j ( m o d m 1 m 2 ) m 2 ( x i − y i ) ≡ m 1 ( y j − x j ) ( m o d m 1 m 2 ) , 即 m 1 m 2 ∣ m 2 ( x i − y i ) + m 1 ( x j − y j ) , 又 m 1 ∣ m 1 m 2 , 所 以 m 1 ∣ m 2 ( x i − y i ) + m 1 ( x j − y j ) = m 2 ( x i − y i ) 因 为 ( m 1 , m 2 ) = 1 , 所 以 m 1 ∣ ( x i − y i ) , 与 x i , y i 为 m 1 的 完 全 剩 余 系 中 元 素 产 生 矛 盾 ， 同 理 m 2 , 证 毕 。 反证法：假设存在x_i,x_j,y_i,y_j使得m_2x_i+m_1x_j与m_2y_i+m_1y_j模m_1m_2同余,其中x_i,y_i属于x_1,x_j,y_j属于x_2,即\\ m_2x_i+m_1x_j\equiv m_2y_i+m_1y_j(mod m_1m_2)\\ m_2(x_i-y_i)\equiv m_1(y_j-x_j)(mod m_1m_2),\\ 即m_1m_2\mid m_2(x_i-y_i)+m_1(x_j-y_j),又m_1\mid m_1m_2,所以m_1\mid m_2(x_i-y_i)+m_1(x_j-y_j)=m_2(x_i-y_i) \\ 因为(m_1,m_2)=1,所以m_1\mid (x_i-y_i),与x_i,y_i为m_1的完全剩余系中元素产生矛盾，同理m_2,证毕。 反证法：假设存在xi,xj,yi,yj使得m2xi+m1xj与m2yi+m1yj模m1m2同余,其中xi,yi属于x1,xj,yj属于x2,即m2xi+m1xj≡m2yi+m1yj(modm1m2)m2(xi−yi)≡m1(yj−xj)(modm1m2),即m1m2∣m2(xi−yi)+m1(xj−yj),又m1∣m1m2,所以m1∣m2(xi−yi)+m1(xj−yj)=m2(xi−yi)因为(m1,m2)=1,所以m1∣(xi−yi),与xi,yi为m1的完全剩余系中元素产生矛盾，同理m2,证毕。
设 m ∈ N + , a ∈ Z , ( a , m ) = 1 , 若 x 遍 历 m 的 一 个 既 约 剩 余 系 ， 则 a x 遍 历 m 的 一 个 既 约 剩 余 系 。 设m\in N^+,a\in Z,(a,m)=1,若x遍历m的一个既约剩余系，则ax遍历m的一个既约剩余系。 设m∈N+,a∈Z,(a,m)=1,若x遍历m的一个既约剩余系，则ax遍历m的一个既约剩余系。先证是遍历的是 m 2 x 1 + m 1 x 2 m_2x_1+m_1x_2 m2x1+m1x2完全剩余系里的元素，再证是更小范围的既约剩余系里的元素 证 明 ： 若 x 遍 历 m 的 一 个 既 约 剩 余 系 ， 则 x = { a 0 , a 1 , a 2 , … a φ ( m ) − 1 } 且 ∀ a i , a j 有 a i 和 a j 模 m 不 同 余 , ( a i , m ) = 1 , 有 a x = { a a 0 , a a 1 , … a a m − 1 } , 我 们 只 需 要 证 明 集 合 a x 中 每 个 整 数 模 m 不 同 余 ， 且 ∀ a i , ( a a i , m ) = 1 反 证 法 ： 假 设 存 在 两 个 整 数 a i , a j 使 得 a a i ≡ a a j ( m o d m ) , 那 么 a ( a i − a j ) ≡ 0 ( m o d m ) → m ∣ a ( a i − a j ) 又 因 为 ( a , m ) = 1 , 所 以 m ∣ a i − a j , 即 a i 与 a j 模 m 同 余 ， 产 生 矛 盾 ， 即 可 证 得 a x 遍 历 的 元 素 属 于 m 的 完 全 剩 余 系 。 现 在 要 证 明 a x 是 m 的 既 约 剩 余 系 ， 还 需 要 证 明 ∀ a i , ( a a i , m ) = 1 , 因 为 ( a i , m ) = 1 , ( a , m ) = 1 ， 所 以 ( a a i , m ) = 1 证明：若x遍历m的一个既约剩余系，则x=\{a_0,a_1,a_2,…a_{\varphi(m)-1}\}且{\forall}a_i,a_j有a_i和a_j模m不同余,(a_i,m)=1,\\ 有ax=\{aa_0,aa_1,…aa_{m-1}\},我们只需要证明集合ax中每个整数模m不同余，且{\forall}a_i,(aa_i,m)=1\\ 反证法：假设存在两个整数a_i,a_j使得aa_i\equiv aa_j(mod m),\\ 那么a(a_i-a_j)\equiv 0(mod m)\rightarrow m\mid a(a_i-a_j)\\ 又因为(a,m)=1,所以m\mid a_i-a_j,即a_i与a_j模m同余，产生矛盾，即可证得ax遍历的元素属于m的完全剩余系。\\ 现在要证明ax是m的既约剩余系，还需要证明{\forall}a_i,(aa_i,m)=1,\\因为(a_i,m)=1,(a,m)=1，所以(aa_i,m)=1 证明：若x遍历m的一个既约剩余系，则x={a0,a1,a2,…aφ(m)−1}且∀ai,aj有ai和aj模m不同余,(ai,m)=1,有ax={aa0,aa1,…aam−1},我们只需要证明集合ax中每个整数模m不同余，且∀ai,(aai,m)=1反证法：假设存在两个整数ai,aj使得aai≡aaj(modm),那么a(ai−aj)≡0(modm)→m∣a(ai−aj)又因为(a,m)=1,所以m∣ai−aj,即ai与aj模m同余，产生矛盾，即可证得ax遍历的元素属于m的完全剩余系。现在要证明ax是m的既约剩余系，还需要证明∀ai,(aai,m)=1,因为(ai,m)=1,(a,m)=1，所以(aai,m)=1
设 m 1 , m 2 是 两 个 互 素 正 整 数 ， x 1 , x 2 分 别 遍 历 m 1 , m 2 的 既 约 剩 余 系 ， 则 m 2 x 1 + m 1 x 2 遍 历 模 m 1 m 2 的 既 约 剩 余 系 。 设m_1,m_2是两个互素正整数，x_1,x_2分别遍历m_1,m_2的既约剩余系，则m_2x_1+m_1x_2遍历模m_1m_2的既约剩余系。 设m1,m2是两个互素正整数，x1,x2分别遍历m1,m2的既约剩余系，则m2x1+m1x2遍历模m1m2的既约剩余系。核心思想跟证ax遍历m的既约剩余系一样，都是从完全剩余系开始证，再缩小范围。 证 明 ： x 1 中 有 m 1 个 元 素 ， x 2 中 有 m 2 个 元 素 ， m 2 x 1 + m 1 x 2 中 有 m 1 m 2 个 元 素 ， 先 证 是 属 于 完 全 剩 余 系 的 ， 那 么 只 需 证 这 m 1 m 2 个 元 素 间 彼 此 模 m 1 m 2 不 同 余 。 反 证 法 ： 假 设 存 在 x i , x j , y i , y j 使 得 m 2 x i + m 1 x j 与 m 2 y i + m 1 y j 模 m 1 m 2 同 余 , 其 中 x i , y i 属 于 x 1 , x j , y j 属 于 x 2 , 即 m 2 x i + m 1 x j ≡ m 2 y i + m 1 y j ( m o d m 1 m 2 ) m 2 ( x i − y i ) ≡ m 1 ( y j − x j ) ( m o d m 1 m 2 ) , 即 m 1 m 2 ∣ m 2 ( x i − y i ) + m 1 ( x j − y j ) , 又 m 1 ∣ m 1 m 2 , 所 以 m 1 ∣ m 2 ( x i − y i ) + m 1 ( x j − y j ) = m 2 ( x i − y i ) 因 为 ( m 1 , m 2 ) = 1 , 所 以 m 1 ∣ ( x i − y i ) , 与 x i , y i 为 m 1 的 完 全 剩 余 系 中 元 素 产 生 矛 盾 ， 同 理 m 2 , 即 证 得 m 2 x 1 + m 1 x 2 是 属 于 m 1 m 2 完 全 剩 余 系 的 。 证明：x_1中有m_1个元素，x_2中有m_2个元素，m_2x_1+m_1x_2中有m_1m_2个元素，先证是属于完全剩余系的，那么只需证这m_1m_2个元素间彼此模m_1m_2不同余。\\ 反证法：假设存在x_i,x_j,y_i,y_j使得m_2x_i+m_1x_j与m_2y_i+m_1y_j模m_1m_2同余,其中x_i,y_i属于x_1,x_j,y_j属于x_2,即\\ m_2x_i+m_1x_j\equiv m_2y_i+m_1y_j(mod m_1m_2)\\ m_2(x_i-y_i)\equiv m_1(y_j-x_j)(mod m_1m_2),\\ 即m_1m_2\mid m_2(x_i-y_i)+m_1(x_j-y_j),又m_1\mid m_1m_2,所以m_1\mid m_2(x_i-y_i)+m_1(x_j-y_j)=m_2(x_i-y_i) \\ 因为(m_1,m_2)=1,所以m_1\mid (x_i-y_i),与x_i,y_i为m_1的完全剩余系中元素产生矛盾，同理m_2,即证得m_2x_1+m_1x_2是属于m_1m_2完全剩余系的。 证明：x1中有m1个元素，x2中有m2个元素，m2x1+m1x2中有m1m2个元素，先证是属于完全剩余系的，那么只需证这m1m2个元素间彼此模m1m2不同余。反证法：假设存在xi,xj,yi,yj使得m2xi+m1xj与m2yi+m1yj模m1m2同余,其中xi,yi属于x1,xj,yj属于x2,即m2xi+m1xj≡m2yi+m1yj(modm1m2)m2(xi−yi)≡m1(yj−xj)(modm1m2),即m1m2∣m2(xi−yi)+m1(xj−yj),又m1∣m1m2,所以m1∣m2(xi−yi)+m1(xj−yj)=m2(xi−yi)因为(m1,m2)=1,所以m1∣(xi−yi),与xi,yi为m1的完全剩余系中元素产生矛盾，同理m2,即证得m2x1+m1x2是属于m1m2完全剩余系的。 现 在 证 明 ∀ x i ∈ x 1 , ∀ x j ∈ x 2 , ( m 2 x i + m 1 x j , m 1 m 2 ) = 1 , 因 为 ( m 2 x i + m 1 x j , m 1 ) = ( m 2 x i , m 1 ) = ( x i , m 1 ) = 1 ( m 2 x i + m 1 x j , m 2 ) = ( m 1 x j , m 2 ) = ( x j , m 2 ) = 1 所 以 , ( m 2 x i + m 1 x j , m 1 m 2 ) = 1 现在证明{\forall}x_i\in x_1,{\forall}x_j\in x_2,(m_2x_i+m_1x_j,m_1m_2)=1,\\ 因为(m_2x_i+m_1x_j,m_1)=(m_2x_i,m_1)=(x_i,m_1)=1\\ (m_2x_i+m_1x_j,m_2)=(m_1x_j,m_2)=(x_j,m_2)=1\\ 所以,(m_2x_i+m_1x_j,m_1m_2)=1 现在证明∀xi∈x1,∀xj∈x2,(m2xi+m1xj,m1m2)=1,因为(m2xi+m1xj,m1)=(m2xi,m1)=(xi,m1)=1(m2xi+m1xj,m2)=(m1xj,m2)=(xj,m2)=1所以,(m2xi+m1xj,m1m2)=1
设 m , n 是 两 个 正 整 数 , ( m , n ) = 1 , 则 φ ( m n ) = φ ( m ) φ ( n ) 设m,n是两个正整数,(m,n)=1,则\varphi(mn)=\varphi(m)\varphi(n) 设m,n是两个正整数,(m,n)=1,则φ(mn)=φ(m)φ(n)证 明 ： m 1 m 2 的 既 约 剩 余 系 中 有 φ ( m n ) 个 元 素 ， x 1 , x 2 分 别 遍 历 m 1 , m 2 的 既 约 剩 余 系 ， m 2 x 1 + m 1 x 2 中 有 φ ( m 1 ) φ ( m 2 ) 个 元 素 ， 所 以 φ ( m n ) = φ ( m ) φ ( n ) 证明：\\ m_1m_2的既约剩余系中有\varphi(mn)个元素，\\ x_1,x_2分别遍历m_1,m_2的既约剩余系，m_2x_1+m_1x_2中有\varphi(m_1)\varphi(m_2)个元素，\\ 所以\varphi(mn)=\varphi(m)\varphi(n) 证明：m1m2的既约剩余系中有φ(mn)个元素，x1,x2分别遍历m1,m2的既约剩余系，m2x1+m1x2中有φ(m1)φ(m2)个元素，所以φ(mn)=φ(m)φ(n)
证明： n的既约剩余系: { b 0 , b 1 , … … , b φ ( n ) − 1 } ， \{b_0,b_1,……,b_{\varphi(n)-1}\}， {b0,b1,……,bφ(n)−1}， 则由上述几个小定理中的第3个小定理：“设 m ∈ N + , a 、 b ∈ Z , ( a , m ) = 1 , m\in N^+,a、b\in Z,(a,m)=1, m∈N+,a、b∈Z,(a,m)=1,若 x x x遍历 m m m的一个既约剩余系，则 a x ax ax遍历 m m m的一个既约剩余系。”，我们可得 { a b 0 , a b 1 , … … , a b φ ( n ) − 1 } \{ab_0,ab_1,……,ab_{\varphi(n)-1}\} {ab0,ab1,……,abφ(n)−1}也是n的既约剩余系，所以有 b 0 ⋅ b 1 ⋅ … … ⋅ b φ ( n ) − 1 ≡ a b 0 ⋅ a b 1 ⋅ … … ⋅ a b φ ( n ) − 1 ≡ a φ ( n ) ⋅ b 0 ⋅ b 1 ⋅ … … ⋅ b φ ( n ) − 1 ( m o d n ) b_0·b_1·……·b_{\varphi(n)-1}\equiv ab_0·ab_1·……·ab_{\varphi(n)-1}\equiv a^{\varphi(n)}·b_0·b_1·……·b_{\varphi(n)-1}(mod n) b0⋅b1⋅……⋅bφ(n)−1≡ab0⋅ab1⋅……⋅abφ(n)−1≡aφ(n)⋅b0⋅b1⋅……⋅bφ(n)−1(modn)
注意： 这里不是因为除法，而是因为乘法，我们已知 ( b i , n ) = 1 (b_i,n)=1 (bi,n)=1，根据信息安全数学基础–整除–欧几里得算法/辗转相除法中推的 ( a , b ) = s a + t b ， (a,b)=sa+tb， (a,b)=sa+tb，那么我们可以写 s i b i + t n = 1 s_ib_i+tn=1 sibi+tn=1，那么同时模 n n n，有 s i b i ≡ 1 ( m o d n ) s_ib_i\equiv 1(mod n) sibi≡1(modn)，即 s i s_i si是 b i b_i bi在模 n n n的意义下的逆元。现在我们对左右同时乘逆元： ( s 0 ⋅ b 0 ) ⋅ ( s 1 ⋅ b 1 ) ⋅ … … ⋅ ( s φ ( n ) − 1 ⋅ b φ ( n ) − 1 ) ≡ a φ ( n ) ⋅ ( s 0 ⋅ b 0 ) ⋅ ( s 1 ⋅ b 1 ) ⋅ … … ⋅ ( s φ ( n ) − 1 ⋅ b φ ( n ) − 1 ) ( m o d n ) (s_0·b_0)·(s_1·b_1)·……·(s_{\varphi(n)-1}·b_{\varphi(n)-1})\equiv a^{\varphi(n)}·(s_0·b_0)·(s_1·b_1)·……·(s_{\varphi(n)-1}·b_{\varphi(n)-1})(mod n) (s0⋅b0)⋅(s1⋅b1)⋅……⋅(sφ(n)−1⋅bφ(n)−1)≡aφ(n)⋅(s0⋅b0)⋅(s1⋅b1)⋅……⋅(sφ(n)−1⋅bφ(n)−1)(modn)，即 a φ ( n ) ≡ 1 ( m o d n ) a^{\varphi(n)}\equiv 1(mod n) aφ(n)≡1(modn)
费 马 小 定 理 ： 设 n 为 素 数 , a ∈ Z , 则 a n ≡ a ( m o d n ) 费马小定理：设n为素数,a\in Z,则a^n\equiv a(mod n) 费马小定理：设n为素数,a∈Z,则an≡a(modn)证 明 ： 从 n ∣ a 和 n ∤ a 两 个 角 度 来 考 虑 证明：从n\mid a 和n\nmid a两个角度来考虑 证明：从n∣a和n∤a两个角度来考虑 若 n ∣ a , 则 a n ≡ 0 ( m o d n ) , a ≡ 0 ( m o d n ) , 即 a n ≡ a ≡ 0 ( m o d n ) 若n\mid a,则a^n\equiv 0(mod n),a\equiv 0(mod n),即a^n\equiv a\equiv 0(mod n) 若n∣a,则an≡0(modn),a≡0(modn),即an≡a≡0(modn) 若 n ∤ a , 则 由 欧 拉 定 理 得 ， a n − 1 ≡ 1 ( m o d n ) , 即 a n ≡ a ( m o d n ) 若n\nmid a,则由欧拉定理得，a^{n-1}\equiv 1(mod n),即a^n\equiv a(mod n) 若n∤a,则由欧拉定理得，an−1≡1(modn),即an≡a(modn)
