Euler's Theorem and Its Applications in Problem Solving | 欧拉定理及其在题型中的应用

📚 Euler’s Theorem and Its Applications in Problem Solving | 欧拉定理及其在题型中的应用

Euler’s Theorem is a cornerstone of number theory, offering a powerful tool for simplifying modular arithmetic. Named after the Swiss mathematician Leonhard Euler, this theorem generalizes Fermat’s Little Theorem and appears frequently in olympiad-style problems, A-Level further mathematics papers, and competitive examinations. Mastering Euler’s Theorem not only deepens your understanding of modular arithmetic but also unlocks elegant solutions to otherwise tedious calculations.

欧拉定理是数论的基石之一，为简化模运算提供了强大工具。该定理以瑞士数学家莱昂哈德·欧拉的名字命名，是费马小定理的推广，在奥林匹克风格题目、A-Level进阶数学试卷及各类竞赛中频繁出现。掌握欧拉定理不仅能加深你对模运算的理解，更能为原本繁冗的计算提供优雅的解答。

1. Statement of Euler’s Theorem | 欧拉定理的陈述

Euler’s Theorem states that if \( n \) is a positive integer and \( a \) is an integer coprime to \( n \) (i.e., gcd(a, n) = 1), then:

欧拉定理指出：若 \( n \) 为正整数，且 \( a \) 与 \( n \) 互质（即 gcd(a, n) = 1），则：

a^φ(n) ≡ 1 (mod n)

Here, φ(n) is Euler’s totient function, which counts the number of positive integers up to n that are coprime to n.

其中 φ(n) 为欧拉函数，表示不超过 n 且与 n 互质的正整数的个数。

Example: Let n = 10. The numbers coprime to 10 are 1, 3, 7, 9, so φ(10) = 4. For a = 3, we have 3⁴ = 81 ≡ 1 (mod 10). Indeed, 81 ≡ 1 (mod 10).

示例：取 n = 10，与 10 互质的数为 1、3、7、9，故 φ(10) = 4。取 a = 3，则 3⁴ = 81 ≡ 1 (mod 10)，验证成立。

2. Computing Euler’s Totient Function φ(n) | 欧拉函数 φ(n) 的计算

To apply Euler’s Theorem, you must first compute φ(n). The formula depends on the prime factorization of n.

要应用欧拉定理，首先需要计算 φ(n)。其计算公式依赖于 n 的质因数分解。

Formula: If n = p₁ᵏ¹ × p₂ᵏ² × … × pᵣᵏʳ, then

公式：若 n = p₁ᵏ¹ × p₂ᵏ² × … × pᵣᵏʳ，则

φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … × (1 − 1/pᵣ)

Example 1: Compute φ(12). Since 12 = 2² × 3,

例 1：计算 φ(12)。由于 12 = 2² × 3，

φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4

Indeed, the numbers coprime to 12 are 1, 5, 7, 11.

确实，与 12 互质的数为 1、5、7、11。

Example 2: Compute φ(100). Since 100 = 2² × 5²,

例 2：计算 φ(100)。由于 100 = 2² × 5²，

φ(100) = 100 × (1 − 1/2) × (1 − 1/5) = 100 × 1/2 × 4/5 = 40

For a prime p, φ(p) = p − 1. This special case recovers Fermat’s Little Theorem.

对于素数 p，φ(p) = p − 1。这种特殊情况正是费马小定理。

3. Proof Strategy of Euler’s Theorem | 欧拉定理的证明思路

The classic proof uses the concept of reduced residue systems. Let r₁, r₂, …, r_φ(n) be the positive integers less than n and coprime to n. Multiply each by a (where gcd(a, n) = 1). The resulting set ar₁, ar₂, …, ar_φ(n) is again a reduced residue system modulo n.

经典证明利用既约剩余系的概念。设 r₁, r₂, …, r_φ(n) 是小于 n 且与 n 互质的全部正整数。将每个数乘以 a（其中 gcd(a, n) = 1），得到的集合 ar₁, ar₂, …, ar_φ(n) 仍然是模 n 的既约剩余系。

Thus, the product of the original set is congruent to the product of the multiplied set:

因此，原集合的乘积与乘以 a 后的集合的乘积同余：

r₁ × r₂ × … × r_φ(n) ≡ a^φ(n) × r₁ × r₂ × … × r_φ(n) (mod n)

Since each rᵢ is invertible modulo n, we cancel the common product to obtain a^φ(n) ≡ 1 (mod n). This proof is elegant and illustrates why the coprimality condition is essential.

由于每个 rᵢ 在模 n 下均可逆，约去公共乘积后即得 a^φ(n) ≡ 1 (mod n)。此证明简洁优美，也说明了互质条件为何必要。

Key insight: The theorem only applies when gcd(a, n) = 1. If they share a common factor, a^φ(n) ≡ 1 will not hold.

关键要点：该定理仅在 gcd(a, n) = 1 时成立。若 a 与 n 有公因子，则 a^φ(n) ≡ 1 不成立。

4. Euler’s Theorem vs. Fermat’s Little Theorem | 欧拉定理与费马小定理的对比

Fermat’s Little Theorem states that for a prime p and any integer a not divisible by p, a^p−1 ≡ 1 (mod p). This is a direct corollary of Euler’s Theorem because φ(p) = p − 1.

费马小定理指出：对于素数 p 及不被 p 整除的整数 a，有 a^p−1 ≡ 1 (mod p)。这是欧拉定理的直接推论，因为 φ(p) = p − 1。

Theorem	Condition	Result
Fermat’s Little Theorem	n = p (prime), p ∤ a	a^p−1 ≡ 1 (mod p)
Euler’s Theorem	gcd(a, n) = 1	a^φ(n) ≡ 1 (mod n)

In practice, when the modulus is composite, Euler’s Theorem is the appropriate tool; when the modulus is prime, both theorems work, but Fermat’s is often quicker.

在实际问题中，当模数为合数时，应使用欧拉定理；当模数为素数时，两个定理均适用，但费马小定理通常更快捷。

5. Application 1: Simplifying Large Exponents | 应用一：化简大指数幂

One of the most common exam problems asks you to compute a^b mod n for very large b. Euler’s Theorem reduces the exponent modulo φ(n).

最常见的考题之一是计算 a^b mod n，其中 b 非常大。欧拉定理可将指数缩小为模 φ(n) 的余数。

Example: Compute 7²²² mod 10.

例题：计算 7²²² mod 10。

Step 1: φ(10) = 4.

第一步：φ(10) = 4。

Step 2: Since gcd(7, 10) = 1, we have 7⁴ ≡ 1 (mod 10). Write 222 = 4 × 55 + 2.

第二步：因为 gcd(7, 10) = 1，所以 7⁴ ≡ 1 (mod 10)。将 222 写成 222 = 4 × 55 + 2。

Step 3: 7²²² = (7⁴)⁵⁵ × 7² ≡ 1⁵⁵ × 49 ≡ 9 (mod 10).

第三步：7²²² = (7⁴)⁵⁵ × 7² ≡ 1⁵⁵ × 49 ≡ 9 (mod 10)。

Thus 7²²² ends in 9.

因此 7²²² 的个位数字是 9。

Another example: Compute 3¹⁰⁰⁰ mod 7. Since 7 is prime, φ(7) = 6. Then 3⁶ ≡ 1 (mod 7). Since 1000 = 6 × 166 + 4, we have 3¹⁰⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).

另一例：计算 3¹⁰⁰⁰ mod 7。由于 7 是素数，φ(7) = 6。于是 3⁶ ≡ 1 (mod 7)。由于 1000 = 6 × 166 + 4，故 3¹⁰⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7)。

6. Application 2: Finding Units Digits and Last Digits | 应用二：求个位数字与末位数字

Euler’s Theorem is particularly useful for determining the last digit (or last few digits) of large numbers without performing full multiplication.

欧拉定理在确定大数的末位数字（或末几位数字）时尤为实用，无需进行完整的大数乘法。

Problem: Find the last two digits of 19²⁰²⁵.

问题：求 19^{2025 的末两位数字。}

Solution: We need 19²⁰²⁵ mod 100. First, φ(100) = 40. Since gcd(19, 100) = 1, we have 19⁴⁰ ≡ 1 (mod 100). Write 2025 = 40 × 50 + 25. Thus 19²⁰²⁵ ≡ 19²⁵ (mod 100).

解：需要求 19²⁰²⁵ mod 100。首先 φ(100) = 40。由于 gcd(19, 100) = 1，所以 19⁴⁰ ≡ 1 (mod 100)。将 2025 = 40 × 50 + 25，所以 19²⁰²⁵ ≡ 19²⁵ (mod 100)。

Now compute 19² = 361 ≡ 61 (mod 100), 19⁴ ≡ 61² = 3721 ≡ 21 (mod 100), 19⁸ ≡ 21² = 441 ≡ 41 (mod 100), 19¹⁶ ≡ 41² = 1681 ≡ 81 (mod 100).

接着计算 19² = 361 ≡ 61 (mod 100)，19⁴ ≡ 61² = 3721 ≡ 21 (mod 100)，19⁸ ≡ 21² = 441 ≡ 41 (mod 100)，19¹⁶ ≡ 41² = 1681 ≡ 81 (mod 100)。

Then 19²⁵ = 19¹⁶ × 19⁸ × 19¹ ≡ 81 × 41 × 19 (mod 100). Since 81 × 41 = 3321 ≡ 21 (mod 100), and 21 × 19 = 399 ≡ 99 (mod 100). The last two digits are 99.

于是 19²⁵ = 19¹⁶ × 19⁸ × 19¹ ≡ 81 × 41 × 19 (mod 100)。由于 81 × 41 = 3321 ≡ 21 (mod 100)，而 21 × 19 = 399 ≡ 99 (mod 100)。末两位数字为 99。

7. Application 3: Solving Linear Congruences | 应用三：求解线性同余方程

Euler’s Theorem provides an explicit way to find modular inverses, which is essential for solving linear congruences of the form ax ≡ b (mod n).

欧拉定理为求模逆元提供了显式方法，而模逆元是求解形如 ax ≡ b (mod n) 的线性同余方程的关键。

If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), so a × a^φ(n)−1 ≡ 1 (mod n). Hence the modular inverse of a is:

若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)，即 a × a^φ(n)−1 ≡ 1 (mod n)。因此 a 的模逆元为：

a⁻¹ ≡ a^φ(n)−1 (mod n)

Example: Solve 5x ≡ 3 (mod 18).

例题：求解 5x ≡ 3 (mod 18)。

Step 1: Compute φ(18). Since 18 = 2 × 3², φ(18) = 18 × (1 − 1/2) × (1 − 1/3) = 6.

第一步：计算 φ(18)。因为 18 = 2 × 3²，φ(18) = 18 × (1 − 1/2) × (1 − 1/3) = 6。

Step 2: The inverse of 5 modulo 18 is 5⁶⁻¹ = 5⁵ = 3125. Since 3125 ≡ 11 (mod 18), the inverse is 11 (check: 5 × 11 = 55 ≡ 1 (mod 18)).

第二步：5 模 18 的逆元为 5⁶⁻¹ = 5⁵ = 3125。由于 3125 ≡ 11 (mod 18)，故逆元为 11（验证：5 × 11 = 55 ≡ 1 (mod 18)）。

Step 3: Multiply both sides by 11: x ≡ 3 × 11 = 33 ≡ 15 (mod 18).

第三步：两边乘以 11：x ≡ 3 × 11 = 33 ≡ 15 (mod 18)。

Thus x ≡ 15 (mod 18) is the solution.

因此 x ≡ 15 (mod 18) 即为方程的解。

8. Application 4: Euler’s Theorem in Cryptography (RSA) | 应用四：欧拉定理在密码学中的应用（RSA）

Euler’s Theorem underpins the RSA public-key cryptosystem. In RSA, two large primes p and q are chosen, and n = p × q. The encryption exponent e is chosen such that gcd(e, φ(n)) = 1, where φ(n) = (p − 1)(q − 1).

欧拉定理由 RSA 公钥密码体制奠定了理论基础。在 RSA 中，选择两个大素数 p 和 q，令 n = p × q。选择加密指数 e，满足 gcd(e, φ(n)) = 1，其中 φ(n) = (p − 1)(q − 1)。

To decrypt, one finds d such that e × d ≡ 1 (mod φ(n)). By Euler’s Theorem, for any message m coprime to n:

解密时，需要找到 d 使得 e × d ≡ 1 (mod φ(n))。根据欧拉定理，对于任何与 n 互质的消息 m：

m^e×d ≡ m^k×φ(n)+1 ≡ (m^φ(n))^k × m ≡ m (mod n)

This ensures that encrypting with e and decrypting with d restores the original message. The security of RSA relies on the difficulty of factoring n to compute φ(n).

这保证了使用 e 加密、d 解密后能恢复原始消息。RSA 的安全性依赖于对大数 n 进行因式分解以计算 φ(n) 的困难性。

Although the full RSA algorithm is beyond A-Level scope, understanding Euler’s Theorem gives you valuable insight into how modular arithmetic applies to real-world technology.

尽管完整的 RSA 算法超出 A-Level 范围，但理解欧拉定理能让你深刻体会模运算在现实技术中的应用。

9. Common Pitfalls and Exam Tips | 常见错误与应试技巧

Students often make the following mistakes when applying Euler’s Theorem:

学生在应用欧拉定理时常出现以下错误：

Forgetting the coprimality condition: Euler’s Theorem fails if gcd(a, n) > 1. Always verify gcd(a, n) = 1 first.
忘记互质条件：当 gcd(a, n) > 1 时，欧拉定理不成立。务必先验证 gcd(a, n) = 1。
Incorrect φ(n) computation: Remember φ(pᵏ) = pᵏ − pᵏ⁻¹, not pᵏ − 1 (unless k = 1). For n = 8 = 2³, φ(8) = 8 − 4 = 4, not 7.
φ(n) 计算错误：注意 φ(pᵏ) = pᵏ − pᵏ⁻¹，而非 pᵏ − 1（除非 k = 1）。例如 n = 8 = 2³ 时，φ(8) = 8 − 4 = 4，而不是 7。
Exponent reduction errors: When reducing a^b mod n, write b = q × φ(n) + r, then a^b ≡ a^r (mod n). Do not reduce a itself unless needed.
指数化简错误：化简 a^b mod n 时，将 b 写成 b = q × φ(n) + r，则 a^b ≡ a^r (mod n)。除非必要，不要对底数 a 进行化简。

Exam tip: If the modulus is small, listing the coprime numbers may be faster than using the prime factorization formula. For n = 10, φ(10) = 4 is obvious. Use the formula when n is large or composite with many factors.

应试技巧：若模数较小，列出互质数可能比使用质因数分解公式更快。例如 n = 10 时，φ(10) = 4 一目了然。当 n 较大或因子较多时，再使用公式计算。

10. Worked Exam-Style Problem | 典型考题详解

Problem: (A-Level Further Mathematics style) Find the remainder when 2²⁰²⁴ is divided by 15.

题目：（A-Level 进阶数学风格）求 2²⁰²⁴ 除以 15 的余数。

Solution:

解答：

Step 1: Compute φ(15). Since 15 = 3 × 5, φ(15) = 15 × (1 − 1/3) × (1 − 1/5) = 15 × 2/3 × 4/5 = 8.

第一步：计算 φ(15)。由于 15 = 3 × 5，φ(15) = 15 × (1 − 1/3) × (1 − 1/5) = 15 × 2/3 × 4/5 = 8。

Step 2: Check gcd(2, 15) = 1, so 2⁸ ≡ 1 (mod 15).

第二步：验证 gcd(2, 15) = 1，故 2⁸ ≡ 1 (mod 15)。

Step 3: Divide 2024 by 8: 2024 = 8 × 253, exactly. Thus 2²⁰²⁴ = (2⁸)²⁵³ ≡ 1²⁵³ ≡ 1 (mod 15).

第三步：用 8 除以 2024：2024 = 8 × 253，恰好整除。因此 2²⁰²⁴ = (2⁸)²⁵³ ≡ 1²⁵³ ≡ 1 (mod 15)。

Therefore the remainder is 1.

因此余数为 1。

Extension: What if the exponent were 2023? Then 2023 = 8 × 252 + 7, so 2²⁰²³ ≡ 2⁷ = 128 ≡ 8 (mod 15).

拓展：若指数为 2023 呢？则 2023 = 8 × 252 + 7，所以 2²⁰²³ ≡ 2⁷ = 128 ≡ 8 (mod 15)。

11. Euler’s Theorem with Non-Coprime Bases | 非互质底数的处理技巧

Sometimes the base a is not coprime to n. In such cases, Euler’s Theorem cannot be applied directly. However, we can often decompose the modulus or use the Chinese Remainder Theorem.

有时底数 a 与 n 不互质。此时不能直接应用欧拉定理。不过，我们通常可以分解模数或使用中国剩余定理。

Example: Compute 6¹⁰⁰ mod 12.

例题：计算 6¹⁰⁰ mod 12。

Observe that 6² = 36 = 3 × 12, so 6² ≡ 0 (mod 12). Therefore for any exponent k ≥ 2, 6^k ≡ 0 (mod 12). Hence 6¹⁰⁰ ≡ 0 (mod 12).

注意到 6² = 36 = 3 × 12，所以 6² ≡ 0 (mod 12)。因此对于任何指数 k ≥ 2，6^k ≡ 0 (mod 12)。故 6¹⁰⁰ ≡ 0 (mod 12)。

For a more systematic approach, factor the base and the modulus. If a shares all prime factors of n, the power eventually becomes divisible by n. In other cases, separate the shared and coprime parts and apply Euler’s Theorem only to the coprime part.

更系统的方法是将底数和模数分解质因数。若 a 含有 n 的全部质因子，则幂最终会被 n 整除。在其他情况下，将互质部分与非互质部分分离，只对互质部分应用欧拉定理。

General strategy: Write a = d × a’, where d contains all common prime factors with n, and gcd(a’, n) = 1. Then use Euler’s Theorem on a’ and handle d separately.

一般策略：将 a 写成 a = d × a’，其中 d 包含与 n 的全部公共质因子，且 gcd(a’, n) = 1。然后对 a’ 使用欧拉定理，并单独处理 d。

12. Summary and Further Practice | 总结与拓展练习

Euler’s Theorem is a versatile tool in number theory with applications ranging from simplifying powers to cryptographic protocols. Its essence lies in the beautiful relationship between multiplication modulo n and the totient function φ(n).

欧拉定理是数论中用途广泛的重要工具，其应用涵盖幂运算化简至密码协议等领域。它的精髓在于模 n 乘法与欧拉函数 φ(n) 之间的优美联系。

Key takeaways:

核心要点：

Euler’s Theorem: a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1.
欧拉定理：当 gcd(a, n) = 1 时，a^φ(n) ≡ 1 (mod n)。
φ(n) = n × ∏(1 − 1/p) over distinct primes p dividing n.
φ(n) = n × ∏(1 − 1/p)，其中 p 取遍 n 的互异质因子。
To reduce large exponents, reduce the exponent modulo φ(n).
要化简大指数幂，只需将指数对 φ(n) 取模。
Always check coprimality before applying the theorem.
应用定理前务必检查互质条件。

Practice problem: Find the remainder when 11²⁰²⁶ is divided by 35. (Hint: φ(35) = 24; 2026 = 24 × 84 + 10; compute 11¹⁰ mod 35.)

练习题目：求 11²⁰²⁶ 除以 35 的余数。（提示：φ(35) = 24；2026 = 24 × 84 + 10；计算 11¹⁰ mod 35。）

By mastering Euler’s Theorem, you gain not only a scoring technique for exams but also a deeper appreciation for the elegance of number theory — a branch of mathematics that continues to shape modern technology and cryptography.

掌握欧拉定理，你不仅获得了一项考试得分技巧，更将深入领略数论的优雅之美——这门数学分支至今仍在深刻塑造现代科技与密码学的发展。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Euler’s Theorem and Its Applications in Problem Solving | 欧拉定理及其在题型中的应用