初等數論--同餘--歐拉函數、歐拉定理、費馬小定理

• 概念
• • 同餘類，既約同餘類
  • 歐拉函數
  • 完全剩餘系，既約剩餘系
• 關于完全剩餘系、既約剩餘系一些比較簡單的定理
• 歐拉定理、費馬小定理

部落客是初學初等數論（整除+同餘+原根），本意是想整理一些較難了解的定理、算法，加深記憶也友善日後查找；如果有錯，歡迎指正。

我整理成一個系列：初等數論，友善檢索。

歐拉函數本身，其實就是一個簡單描述與元素互素個數的函數，但是它涉及、以及由它推出的定理（歐拉定理、費馬小定理）很重要。我會從一些小概念、小定理推到歐拉定理、費馬小定理等比較難的定理。

概念

同餘類，既約同餘類

同 餘 類 ： 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}

關于完全剩餘系、既約剩餘系一些比較簡單的定理

• 設 m ∈ N + , a 、 b ∈ Z , ( a , m ) = 1 , 若 x 遍 曆 m 的 一 個 完 全 剩 餘 系 ， 則 a x + b 遍 曆 m 的 一 個 完 全 剩 餘 系 。 設m\in N^+,a、b\in Z,(a,m)=1,若x周遊m的一個完全剩餘系，則ax+b周遊m的一個完全剩餘系。 設m∈N+,a、b∈Z,(a,m)=1,若x周遊m的一個完全剩餘系，則ax+b周遊m的一個完全剩餘系。

證 明 ： 若 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​的完全剩餘系，則m2​x1​+m1​x2​周遊模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​個元素，m2​x1​+m1​x2​中有m1​m2​個元素，現在隻需證這m1​m2​個元素彼此模m1​m2​不同餘。

反 證 法 ： 假 設 存 在 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​使得m2​xi​+m1​xj​與m2​yi​+m1​yj​模m1​m2​同餘,其中xi​,yi​屬于x1​,xj​,yj​屬于x2​,即m2​xi​+m1​xj​≡m2​yi​+m1​yj​(modm1​m2​)m2​(xi​−yi​)≡m1​(yj​−xj​)(modm1​m2​),即m1​m2​∣m2​(xi​−yi​)+m1​(xj​−yj​),又m1​∣m1​m2​,是以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 m2​x1​+m1​x2​完全剩餘系裡的元素，再證是更小範圍的既約剩餘系裡的元素

證 明 ： 若 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​的既約剩餘系，則m2​x1​+m1​x2​周遊模m1​m2​的既約剩餘系。

核心思想跟證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​個元素，m2​x1​+m1​x2​中有m1​m2​個元素，先證是屬于完全剩餘系的，那麼隻需證這m1​m2​個元素間彼此模m1​m2​不同餘。反證法：假設存在xi​,xj​,yi​,yj​使得m2​xi​+m1​xj​與m2​yi​+m1​yj​模m1​m2​同餘,其中xi​,yi​屬于x1​,xj​,yj​屬于x2​,即m2​xi​+m1​xj​≡m2​yi​+m1​yj​(modm1​m2​)m2​(xi​−yi​)≡m1​(yj​−xj​)(modm1​m2​),即m1​m2​∣m2​(xi​−yi​)+m1​(xj​−yj​),又m1​∣m1​m2​,是以m1​∣m2​(xi​−yi​)+m1​(xj​−yj​)=m2​(xi​−yi​)因為(m1​,m2​)=1,是以m1​∣(xi​−yi​),與xi​,yi​為m1​的完全剩餘系中元素産生沖突，同理m2​,即證得m2​x1​+m1​x2​是屬于m1​m2​完全剩餘系的。

現 在 證 明 ∀ 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​,(m2​xi​+m1​xj​,m1​m2​)=1,因為(m2​xi​+m1​xj​,m1​)=(m2​xi​,m1​)=(xi​,m1​)=1(m2​xi​+m1​xj​,m2​)=(m1​xj​,m2​)=(xj​,m2​)=1是以,(m2​xi​+m1​xj​,m1​m2​)=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) 證明：m1​m2​的既約剩餘系中有φ(mn)個元素，x1​,x2​分别周遊m1​,m2​的既約剩餘系，m2​x1​+m1​x2​中有φ(m1​)φ(m2​)個元素，是以φ(mn)=φ(m)φ(n)

歐拉定理、費馬小定理

• 歐 拉 定 理 ： 設 n ∈ N + , a ∈ Z , ( a , n ) = 1 , 則 a φ ( n ) ≡ 1 ( m o d n ) 歐拉定理：設n\in N^+,a\in Z,(a,n)=1,則a^{\varphi(n)}\equiv 1(mod n) 歐拉定理：設n∈N+,a∈Z,(a,n)=1,則aφ(n)≡1(modn)

證明：

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 si​bi​+tn=1，那麼同時模 n n n，有 s i b i ≡ 1 ( m o d n ) s_ib_i\equiv 1(mod n) si​bi​≡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)