Euler Function and Congruence Theory

Welcome to a crucial topic in number theory: the Euler Totient Function and Congruence Theory. Understanding these concepts is vital for solving many problems in advanced mathematics, cryptography, and computer science. We will break down each concept thoroughly, ensuring you grasp the fundamentals and their applications.

Euler Totient Function (φ(n))

The Euler Totient Function, denoted by φ(n) (phi of n), counts the number of positive integers less than or equal to 'n' that are relatively prime to 'n'. Two integers are relatively prime if their greatest common divisor (GCD) is 1.

Definition and Basic Properties

Mathematically, φ(n) is defined as: φ(n) = |{k ∈ ℤ | 1 ≤ k ≤ n and gcd(k, n) = 1}|

Let's look at some examples to understand this definition:

• φ(1): The only integer is 1. gcd(1, 1) = 1. So, φ(1) = 1.
• φ(2): Integers are 1, 2. gcd(1, 2) = 1. gcd(2, 2) = 2. So, φ(2) = 1.
• φ(3): Integers are 1, 2, 3. gcd(1, 3) = 1. gcd(2, 3) = 1. gcd(3, 3) = 3. So, φ(3) = 2.
• φ(4): Integers are 1, 2, 3, 4. gcd(1, 4) = 1. gcd(2, 4) = 2. gcd(3, 4) = 1. gcd(4, 4) = 4. So, φ(4) = 2.
• φ(5): Integers are 1, 2, 3, 4, 5. gcd(1, 5)=1, gcd(2, 5)=1, gcd(3, 5)=1, gcd(4, 5)=1, gcd(5, 5)=5. So, φ(5) = 4.
• φ(6): Integers are 1, 2, 3, 4, 5, 6. gcd(1, 6)=1, gcd(2, 6)=2, gcd(3, 6)=3, gcd(4, 6)=2, gcd(5, 6)=1, gcd(6, 6)=6. So, φ(6) = 2.

Properties of Euler's Totient Function:

1. If 'p' is a prime number, then φ(p) = p - 1.

   This is because all integers from 1 to p-1 are relatively prime to p. Only p itself shares a common factor (p) with p.

2. If 'p' is a prime number and 'k' is a positive integer, then φ(p^k) = p^k - p^k-1 = p^k(1 - 1/p).

   The numbers not relatively prime to p^k are the multiples of p: p, 2p, 3p, ..., p^k-1p. There are p^k-1 such multiples. So, the count of numbers relatively prime to p^k is the total numbers (p^k) minus these multiples (p^k-1).

   Example: φ(8) = φ(2³) = 2³ - 2^3-1 = 8 - 4 = 4. The numbers are 1, 3, 5, 7.

3. If 'm' and 'n' are relatively prime (gcd(m, n) = 1), then φ(mn) = φ(m)φ(n). This property makes the function multiplicative.

   Example: φ(6) = φ(2 * 3). Since gcd(2, 3) = 1, φ(6) = φ(2) * φ(3) = (2-1) * (3-1) = 1 * 2 = 2. This matches our earlier calculation.

4. For any integer n > 1, φ(n) is even.

   If n has an odd prime factor 'p', then φ(n) will have a factor of φ(p) = p-1, which is even. If n is a power of 2, say n = 2^k with k ≥ 2, then φ(n) = 2^k - 2^k-1 = 2^k-1, which is even. The only case where φ(n) is odd is for n=1 and n=2, where φ(1)=1 and φ(2)=1.

Formula for φ(n)

Using the multiplicative property and the formula for prime powers, we can derive a general formula for φ(n). If the prime factorization of n is given by n = p₁^a₁ * p₂^a₂ * ... * p_k^a_k, where p₁, p₂, ..., p_k are distinct prime numbers and a₁, a₂, ..., a_k are positive integers, then: φ(n) = φ(p₁^a₁) * φ(p₂^a₂) * ... * φ(p_k^a_k) φ(n) = (p₁^a₁ - p₁^a₁-1) * (p₂^a₂ - p₂^a₂-1) * ... * (p_k^a_k - p_k^a_k-1) This can also be written as: φ(n) = n * (1 - 1/p₁) * (1 - 1/p₂) * ... * (1 - 1/p_k)

Let's calculate φ(360) as an example: First, find the prime factorization of 360. 360 = 36 * 10 = (6²) * (2 * 5) = (2 * 3)² * 2 * 5 = 2² * 3² * 2 * 5 = 2³ * 3² * 5¹. The distinct prime factors are 2, 3, and 5. Using the formula: φ(360) = 360 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) φ(360) = 360 * (1/2) * (2/3) * (4/5) φ(360) = 360 * (8 / 30) φ(360) = (360 / 30) * 8 φ(360) = 12 * 8 = 96.

Congruence Theory

Congruence theory is a fundamental part of number theory that deals with remainders. It provides a way to work with integers modulo some number.

Definition of Congruence

Let 'a' and 'b' be integers, and let 'm' be a positive integer. We say that 'a' is congruent to 'b' modulo 'm' if 'm' divides the difference (a - b). This is written as: a ≡ b (mod m)

This notation means that a - b = km for some integer k. Equivalently, 'a' and 'b' have the same remainder when divided by 'm'.

Examples:

• 17 ≡ 2 (mod 5) because 17 - 2 = 15, and 5 divides 15. Also, 17 divided by 5 gives a remainder of 2.
• 23 ≡ 8 (mod 3) because 23 - 8 = 15, and 3 divides 15. Also, 23 divided by 3 gives a remainder of 2, and 8 divided by 3 gives a remainder of 2.
• 10 ≡ 10 (mod 7) because 10 - 10 = 0, and 7 divides 0.
• -5 ≡ 10 (mod 3) because -5 - 10 = -15, and 3 divides -15. Also, -5 divided by 3 gives a remainder of 1 (-5 = -2*3 + 1), and 10 divided by 3 gives a remainder of 1 (10 = 3*3 + 1).

Properties of Congruences

Congruences behave much like equations. If a ≡ b (mod m) and c ≡ d (mod m), then:

1. Addition: a + c ≡ b + d (mod m)

   Example: Since 17 ≡ 2 (mod 5) and 10 ≡ 0 (mod 5), then 17 + 10 ≡ 2 + 0 (mod 5), which means 27 ≡ 2 (mod 5). (27 = 5*5 + 2).

2. Subtraction: a - c ≡ b - d (mod m)

   Example: Since 17 ≡ 2 (mod 5) and 10 ≡ 0 (mod 5), then 17 - 10 ≡ 2 - 0 (mod 5), which means 7 ≡ 2 (mod 5). (7 = 1*5 + 2).

3. Multiplication: ac ≡ bd (mod m)

   Example: Since 17 ≡ 2 (mod 5) and 10 ≡ 0 (mod 5), then 17 * 10 ≡ 2 * 0 (mod 5), which means 170 ≡ 0 (mod 5). (170 = 34*5 + 0).

4. Powers: If a ≡ b (mod m), then a^k ≡ b^k (mod m) for any positive integer k.

   Example: Since 3 ≡ 1 (mod 2), then 3⁵ ≡ 1⁵ (mod 2), which means 243 ≡ 1 (mod 2). (243 is odd).

Division in Congruences

Division is trickier. If ac ≡ bc (mod m), we CANNOT always conclude that a ≡ b (mod m). However, if we know that gcd(c, m) = d, then we can divide by c, but we must also divide the modulus m by d. So, if ac ≡ bc (mod m) and gcd(c, m) = d, then a ≡ b (mod m/d).

Example: 10 ≡ 4 (mod 6). Here a=5, b=2, c=2, m=6. 5 * 2 ≡ 2 * 2 (mod 6) 10 ≡ 4 (mod 6) - This is true. Now, let's divide by c=2. gcd(c, m) = gcd(2, 6) = 2. So d=2. We can conclude that 5 ≡ 2 (mod 6/2), which is 5 ≡ 2 (mod 3). Let's check: 5 divided by 3 leaves remainder 2. 2 divided by 3 leaves remainder 2. So, 5 ≡ 2 (mod 3) is true.

If gcd(c, m) = 1 (i.e., c and m are relatively prime), then we can cancel c directly: ac ≡ bc (mod m) implies a ≡ b (mod m).

Linear Congruences

A linear congruence is an equation of the form ax ≡ b (mod m), where a, b, and m are integers and m > 0. We want to find the integer values of 'x' that satisfy this congruence.

The linear congruence ax ≡ b (mod m) has solutions for x if and only if gcd(a, m) divides b. Let d = gcd(a, m). If d does not divide b, there are no solutions. If d divides b, then there are exactly 'd' incongruent solutions modulo m.

To find the solutions when d divides b: 1. Divide the entire congruence by d: (a/d)x ≡ (b/d) (mod m/d) Let a' = a/d, b' = b/d, m' = m/d. The congruence becomes: a'x ≡ b' (mod m') 2. Now, gcd(a', m') = 1. This means a' has a multiplicative inverse modulo m'. We need to find an integer 'inv' such that a' * inv ≡ 1 (mod m'). 3. Multiply both sides of a'x ≡ b' (mod m') by the inverse 'inv': inv * a'x ≡ inv * b' (mod m') 1 * x ≡ inv * b' (mod m') x ≡ inv * b' (mod m') This gives us one solution, let's call it x₀. x₀ ≡ inv * b' (mod m') 4. The 'd' incongruent solutions modulo m are: x₀, x₀ + m', x₀ + 2m', ..., x₀ + (d-1)m'

Example: Solve 6x ≡ 9 (mod 15) Here, a = 6, b = 9, m = 15. First, find d = gcd(a, m) = gcd(6, 15) = 3. Check if d divides b: 3 divides 9. Yes. So there are d=3 solutions modulo 15. Divide the congruence by d=3: (6/3)x ≡ (9/3) (mod 15/3) 2x ≡ 3 (mod 5) Now, a' = 2, b' = 3, m' = 5. We need to find the multiplicative inverse of 2 modulo 5. We are looking for 'inv' such that 2 * inv ≡ 1 (mod 5). Let's test values: 2 * 1 = 2 ≡ 2 (mod 5) 2 * 2 = 4 ≡ 4 (mod 5) 2 * 3 = 6 ≡ 1 (mod 5). So, the inverse of 2 modulo 5 is 3. Multiply the congruence 2x ≡ 3 (mod 5) by the inverse 3: 3 * (2x) ≡ 3 * 3 (mod 5) 6x ≡ 9 (mod 5) Since 6 ≡ 1 (mod 5), this simplifies to: 1x ≡ 4 (mod 5) x ≡ 4 (mod 5) So, x₀ = 4. The three solutions modulo 15 are: x₀ = 4 x₀ + m' = 4 + 5 = 9 x₀ + 2m' = 4 + 2*5 = 14 The solutions are x ≡ 4, 9, 14 (mod 15). Let's check: For x=4: 6*4 = 24. 24 mod 15 = 9. Correct. For x=9: 6*9 = 54. 54 mod 15 = 9 (since 54 = 3*15 + 9). Correct. For x=14: 6*14 = 84. 84 mod 15 = 9 (since 84 = 5*15 + 9). Correct.

Euler's Theorem

Euler's Theorem is a generalization of Fermat's Little Theorem and is a direct consequence of congruence theory and the Euler totient function.

Statement of Euler's Theorem

If 'a' and 'n' are relatively prime positive integers (i.e., gcd(a, n) = 1), then: a^φ(n) ≡ 1 (mod n)

This theorem is incredibly powerful. It tells us that if we raise 'a' to the power of φ(n) and divide by 'n', the remainder will always be 1, provided 'a' and 'n' share no common factors.

Examples:

• Let a=3, n=7. gcd(3, 7) = 1. φ(7) = 7-1 = 6 (since 7 is prime). Euler's Theorem states: 3⁶ ≡ 1 (mod 7). Let's check: 3¹=3, 3²=9≡2, 3³≡6, 3⁴≡18≡4, 3⁵≡12≡5, 3⁶≡15≡1 (mod 7). It holds true.
• Let a=2, n=9. gcd(2, 9) = 1. Prime factorization of 9 is 3². φ(9) = φ(3²) = 3² - 3^2-1 = 9 - 3 = 6. Euler's Theorem states: 2⁶ ≡ 1 (mod 9). Let's check: 2¹=2, 2²=4, 2³=8, 2⁴=16≡7, 2⁵=32≡5, 2⁶=64. 64 divided by 9 is 7 with a remainder of 1 (64 = 7*9 + 1). So, 64 ≡ 1 (mod 9). It holds true.

Applications of Euler's Theorem

Euler's Theorem is fundamental in simplifying large powers in modular arithmetic. If we need to compute a^k (mod n) where k is very large, we can use Euler's Theorem. If gcd(a, n) = 1, then a^k ≡ a^{k mod φ(n)} (mod n). This is because a^φ(n) ≡ 1 (mod n). So, we can rewrite k as k = q * φ(n) + r, where r = k mod φ(n). Then, a^k = a^{q*φ(n) + r} = (a^φ(n))^q * a^r. Modulo n, this becomes: a^k ≡ (1)^q * a^r (mod n) a^k ≡ a^r (mod n) a^k ≡ a^{k mod φ(n)} (mod n)

Example: Compute 7¹⁰⁰ (mod 10). Here, a=7, n=10. gcd(7, 10) = 1. First, calculate φ(10). The prime factorization of 10 is 2 * 5. φ(10) = 10 * (1 - 1/2) * (1 - 1/5) = 10 * (1/2) * (4/5) = 10 * (4/10) = 4. Now, we need to find the exponent modulo φ(10): 100 mod φ(10) = 100 mod 4 = 0. So, 7¹⁰⁰ ≡ 7⁰ (mod 10). 7¹⁰⁰ ≡ 1 (mod 10). The remainder is 1. Let's verify this logic. Euler's theorem states a^φ(n) ≡ 1 (mod n). So, 7⁴ ≡ 1 (mod 10). 7¹⁰⁰ = 7^{4 * 25} = (7⁴)²⁵. (7⁴)²⁵ ≡ (1)²⁵ (mod 10) 7¹⁰⁰ ≡ 1 (mod 10). Note: If k mod φ(n) is 0, the result is 1, not a⁰=1 in the trivial sense, but rather a^φ(n) ≡ 1 (mod n). So, if the exponent modulo φ(n) is 0, we use φ(n) as the exponent. In our case, 100 mod 4 = 0. So, 7¹⁰⁰ ≡ 7⁴ ≡ 1 (mod 10). If we had 7¹⁰¹ (mod 10), then 101 mod 4 = 1. 7¹⁰¹ ≡ 7¹ ≡ 7 (mod 10).

Fermat's Little Theorem

Fermat's Little Theorem is a special case of Euler's Theorem when the modulus 'n' is a prime number.

Statement of Fermat's Little Theorem

If 'p' is a prime number, then for any integer 'a' not divisible by 'p' (i.e., gcd(a, p) = 1), we have: a^p-1 ≡ 1 (mod p)

Alternatively, for any integer 'a' and any prime 'p': a^p ≡ a (mod p)

Note that φ(p) = p-1 for a prime 'p'. So, a^p-1 ≡ 1 (mod p) is exactly a^φ(p) ≡ 1 (mod p). The second form a^p ≡ a (mod p) can be derived from the first by multiplying both sides by 'a': a * a^p-1 ≡ a * 1 (mod p), which gives a^p ≡ a (mod p). This second form also holds even if 'p' divides 'a', because if p|a, then a ≡ 0 (mod p), so a^p ≡ 0^p ≡ 0 (mod p), and a ≡ 0 (mod p), thus a^p ≡ a (mod p).

Examples:

• Let p=5, a=3. gcd(3, 5) = 1. Fermat's Little Theorem states: 3^5-1 ≡ 3⁴ ≡ 1 (mod 5). Check: 3¹=3, 3²=9≡4, 3³≡12≡2, 3⁴≡6≡1 (mod 5). Correct. Using the second form: 3⁵ ≡ 3 (mod 5). Check: 3⁵ = 3⁴ * 3 ≡ 1 * 3 ≡ 3 (mod 5). Correct.
• Let p=7, a=14. Since 7 divides 14, we use the second form: a^p ≡ a (mod p). 14⁷ ≡ 14 (mod 7). Since 14 ≡ 0 (mod 7), this means 0⁷ ≡ 0 (mod 7), which is 0 ≡ 0 (mod 7). Correct.

Applications

Fermat's Little Theorem is used in:

• Primality Testing: While not a foolproof test, it's a component of some probabilistic primality tests (like the Fermat primality test). If a^n-1 1 (mod n) for some 'a' with gcd(a, n) = 1, then 'n' is definitely composite. If it holds for many 'a', 'n' is likely prime.
• Cryptography: It forms the basis for many cryptographic algorithms, including RSA.
• Simplifying modular exponentiation: Similar to Euler's Theorem, it simplifies calculations of large powers modulo a prime. For a prime 'p', a^k ≡ a^{k mod (p-1)} (mod p), provided p does not divide a.

Chinese Remainder Theorem (CRT)

The Chinese Remainder Theorem (CRT) is a powerful tool for solving systems of simultaneous linear congruences. It allows us to find a unique solution modulo the product of the moduli, provided the moduli are pairwise coprime.

Statement of the Chinese Remainder Theorem

Let n₁, n₂, ..., n_k be positive integers that are pairwise coprime (i.e., gcd(n_i, n_j) = 1 for all i ≠ j). Let a₁, a₂, ..., a_k be any integers. Then, the system of congruences: x ≡ a₁ (mod n₁) x ≡ a₂ (mod n₂) ... x ≡ a_k (mod n_k) has a unique solution modulo N, where N = n₁ * n₂ * ... * n_k.

Constructive Proof and Algorithm

To find the solution 'x': 1. Calculate N = n₁ * n₂ * ... * n_k. 2. For each i from 1 to k, calculate N_i = N / n_i. (This N_i is the product of all moduli except n_i). 3. For each i, find the modular multiplicative inverse of N_i modulo n_i. Let this inverse be y_i, such that N_i * y_i ≡ 1 (mod n_i). Since gcd(N_i, n_i) = 1 (because n_i is coprime to all other n_j's), this inverse always exists. 4. The solution 'x' is given by the sum: x = a₁N₁y₁ + a₂N₂y₂ + ... + a_kN_ky_k 5. The unique solution modulo N is x mod N.

Example: Solve the system: x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7)

Here, n₁=3, n₂=5, n₃=7. They are pairwise coprime. a₁=2, a₂=3, a₃=2.

1. Calculate N = n₁ * n₂ * n₃ = 3 * 5 * 7 = 105.
2. Calculate N_i: N₁ = N / n₁ = 105 / 3 = 35. N₂ = N / n₂ = 105 / 5 = 21. N₃ = N / n₃ = 105 / 7 = 15.
3. Find the inverses y_i: For N₁=35 modulo n₁=3: 35 ≡ 2 (mod 3). We need y₁ such that 2 * y₁ ≡ 1 (mod 3). If y₁ = 2, then 2*2 = 4 ≡ 1 (mod 3). So, y₁ = 2. For N₂=21 modulo n₂=5: 21 ≡ 1 (mod 5). We need y₂ such that 1 * y₂ ≡ 1 (mod 5). So, y₂ = 1. For N₃=15 modulo n₃=7: 15 ≡ 1 (mod 7). We need y₃ such that 1 * y₃ ≡ 1 (mod 7). So, y₃ = 1.
4. Calculate x: x = a₁N₁y₁ + a₂N₂y₂ + a₃N₃y₃ x = (2 * 35 * 2) + (3 * 21 * 1) + (2 * 15 * 1) x = 140 + 63 + 30 x = 233.
5. Find the solution modulo N: x mod N = 233 mod 105. 233 = 2 * 105 + 23. So, x ≡ 23 (mod 105).

The unique solution is x ≡ 23 (mod 105). Let's check: 23 mod 3 = 2. Correct. 23 mod 5 = 3. Correct. 23 mod 7 = 2. Correct.

Summary and Key Takeaways

We have covered the Euler Totient Function, Congruence Theory, Euler's Theorem, Fermat's Little Theorem, and the Chinese Remainder Theorem. These are fundamental building blocks in number theory.

• φ(n) counts numbers less than 'n' and relatively prime to 'n'. Its formula depends on the prime factorization of 'n'.
• Congruence: a ≡ b (mod m) means 'm' divides (a-b). It has properties similar to equality for addition, subtraction, and multiplication.
• Linear Congruences (ax ≡ b mod m): Solvable iff gcd(a, m) divides b. Has gcd(a, m) solutions.
• Euler's Theorem: If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). This allows simplification of large exponents.
• Fermat's Little Theorem: If 'p' is prime and p a, then a^p-1 ≡ 1 (mod p). A special case of Euler's Theorem.
• Chinese Remainder Theorem: Solves systems of congruences with pairwise coprime moduli, yielding a unique solution modulo the product of moduli.

Mastering these concepts will equip you to tackle a wide array of number theory problems encountered in competitive exams and advanced studies. Practice applying these theorems with various examples.