Mathematics
Coprime Numbers and Euler's Totient Function in Modular Arithmetic
Quick fact
For any number n, exactly φ(n) integers from 1 to n are coprime to n—and these are precisely the numbers that have a multiplicative inverse modulo n. For example, φ(10)=4 because only 1, 3, 7, and 9 are coprime to 10; indeed, each of these has an inverse modulo 10, such as 3·7 ≡ 1 (mod 10).
Why this is interesting
Think of the numbers from 1 to 10. Some of them can be multiplied together to get back to 1, but only if they share no secret factor. What's the hidden rule that decides which numbers are 'lucky'?
Read the full explanation
Understanding Coprime Numbers and Euler's Totient Function in Modular Arithmetic
In modular arithmetic, we work with remainders after division by a fixed number, the modulus. For instance, modulo 10, the numbers 0,1,2,...,9 repeat like a clock. When we multiply two numbers modulo 10, we take the remainder of their product. But not every number has a multiplicative inverse—a number that when multiplied together gives 1. For example, 3 has an inverse because 3·7=21 ≡ 1 (mod 10), but 2 does not, because no number times 2 gives 1 modulo 10. The key is that a number has an inverse if and only if it is coprime to the modulus—they share no common factor other than 1. Why? Because if two numbers share a factor, their product will also share that factor, and the product modulo n cannot become 1 unless that factor is 1. The set of numbers coprime to n forms a special set called the reduced residue system, and their count is exactly φ(n).
A deeper explanation
The mechanism behind coprimality and inverses is the Euclidean algorithm. Two numbers a and n are coprime if their greatest common divisor is 1. By the extended Euclidean algorithm, there exist integers x and y such that ax + ny = 1. Taking this equation modulo n, we get ax ≡ 1 (mod n), meaning x is the multiplicative inverse of a modulo n. Thus, coprimality is the exact condition for invertibility. Euler's totient function φ(n) counts these invertible elements. To compute φ(n), we use the prime factorization of n: if n = p₁^e₁ · p₂^e₂ · ... · pₖ^eₖ, then φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pₖ). This formula works because a number is coprime to n if it is not divisible by any of its prime factors. The totient function is central to Euler's theorem: for any a coprime to n, a^φ(n) ≡ 1 (mod n). This theorem generalizes Fermat's Little Theorem and is the engine behind RSA encryption, where the security relies on the difficulty of factoring n, but the decryption uses φ(n) to find the private key. Understanding φ(n) reveals why the group of units modulo n has exactly φ(n) elements, making it the cornerstone of modern cryptographic systems.