Euler's theorem
Euler's theorem, also known as Euler's totient theorem, is a fundamental result in number theory that generalizes Fermat's Little Theorem to composite moduli. It states that if a and n are coprime positive integers with n \geq 2, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi(n) denotes Euler's totient function, which counts the positive integers up to n that are relatively prime to n}.[1][2] Named after the Swiss mathematician Leonhard Euler, the theorem was first published by him in 1763 as an extension of Fermat's Little Theorem, which applies specifically when n is prime and states that a^{p-1} \equiv 1 \pmod{p} for prime p not dividing a. Euler introduced the totient function \phi(n) in this context, building on earlier work by Pierre de Fermat and Gottfried Leibniz. The theorem can be proved using the structure of the multiplicative group of integers modulo n, which has order \phi(n). The function \phi(n) is multiplicative for coprime arguments and can be computed explicitly as \phi(n) = n \prod_{p \mid n} (1 - 1/p) for the prime factorization of n.[1][3] Euler's theorem plays a central role in modular arithmetic and has broad applications in modern cryptography, such as the RSA algorithm, where the totient function helps determine exponents for encryption and decryption using a modulus n = pq for distinct primes p and q. It also explains the periodicity of decimal expansions for fractions $1/b, where the period length divides \phi(b) if b is coprime to 10. Additionally, the theorem underpins more advanced results in algebraic number theory and is essential for computing large powers modulo n efficiently via exponentiation by squaring after reducing the exponent modulo \phi(n).[1][2]Introduction
Overview
Euler's theorem is a fundamental result in number theory that pertains to modular arithmetic. It asserts that if a and n are coprime positive integers, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi denotes Euler's totient function, which counts the number of integers up to n that are coprime to n.[1] This theorem serves as a generalization of Fermat's little theorem, extending its principle from prime moduli to arbitrary positive integers n, and it elucidates key properties of the multiplicative group of integers modulo n.[1] Euler's contributions to number theory during the 18th century were profound, and the theorem first appeared in his 1763 paper Theoremata arithmetica nova methodo demonstrata, where he provided a proof using innovative arithmetic techniques.[4] In contemporary applications, Euler's theorem underpins cryptographic protocols such as the RSA algorithm, enabling efficient modular exponentiation essential for secure communication and data protection.[5]Historical context
Leonhard Euler's contributions to number theory emerged in the context of earlier work by Pierre de Fermat, who stated what is now known as Fermat's little theorem in a 1640 letter to Frenicle de Bessy, asserting that if p is prime and a is not divisible by p, then a^{p-1} \equiv 1 \pmod{p}, though without proof.[6] Euler provided the first published proof of this theorem in 1736, using an elementary approach based on mathematical induction on a, marking a significant advancement in the 18th-century development of the field.[7] His interest in such topics was stimulated by correspondence with Christian Goldbach, which began in 1729 and included discussions of Fermat's conjectures, fostering Euler's prolific output in arithmetic during the 1730s and 1740s.[8] Euler's own theorem, a generalization of Fermat's result, built on these foundations by incorporating the totient function \phi(n), which counts the positive integers up to n that are coprime to n. He first described this function in his 1758 paper "Demonstration of a new method in the theory of arithmetic" (E271), though it received formal publication in 1763 in "Theoremata arithmetica nova methodo demonstrata," where he proved key properties such as multiplicativity for coprime arguments and used it to state that if a and n are coprime, then a^{\phi(n)} \equiv 1 \pmod{n}.[9] Related ideas appeared indirectly in his 1748 work Introductio in analysin infinitorum, which advanced function theory and infinite series in ways that supported broader arithmetic investigations.[8] By the 1760s, Euler had extended his proofs of Fermat's theorem into this more general form, solidifying its place in number theory.[7] Euler's productivity persisted despite personal challenges; he became nearly blind in his right eye by 1738 and lost vision in his left by 1766, culminating in total blindness in 1771, yet he continued dictating mathematical work with remarkable output, producing over half his lifetime publications afterward.[8] His ideas profoundly influenced subsequent mathematicians, notably Carl Friedrich Gauss, whose 1801 Disquisitiones Arithmeticae synthesized and expanded upon results from Euler, Fermat, and Lagrange, establishing number theory as a rigorous discipline and introducing notation like \phi(n) for the totient function.[9][10]Mathematical prerequisites
Euler's totient function
Euler's totient function, denoted \phi(n), counts the number of positive integers less than or equal to n that are relatively prime to n, that is, whose greatest common divisor with n is 1. This function was introduced by Leonhard Euler in his 1763 paper "Theoremata arithmetica nova methodo demonstrata."[11] For example, \phi(1) = 1 since the only positive integer up to 1 is 1, which is coprime to itself.[12] To compute \phi(n), first factorize n into primes: suppose n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}, where the p_i are distinct primes and k_i \geq 1. Then, \phi(n) = n \prod_{i=1}^r \left(1 - \frac{1}{p_i}\right). For a prime power, this simplifies to \phi(p^k) = p^k - p^{k-1}, as exactly one in every p numbers up to p^k is divisible by p, leaving the rest coprime to p^k.[12] This formula arises from inclusion-exclusion over the prime factors, subtracting multiples of each prime and adding back overcounts.[12] The totient function is multiplicative: if \gcd(a, b) = 1, then \phi(ab) = \phi(a) \phi(b).[12] This property extends the computation to composite n by applying the prime power formula to each factor. A brief sketch of the proof uses the Chinese Remainder Theorem, which provides a bijection between the integers modulo ab and the pairs of residues modulo a and modulo b. Under this bijection, an integer is coprime to ab if and only if its residues are coprime to a and to b, respectively, so the count \phi(ab) equals the product \phi(a) \phi(b).[13] Illustrative examples include \phi(6), where $6 = 2 \cdot 3, so \phi(6) = 6 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 2; the coprime integers are 1 and 5. For the prime $7, \phi(7) = 7 - 1 = 6, as all integers from 1 to 6 are coprime to 7. For $12 = 2^2 \cdot 3, \phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 4; the coprime integers are 1, 5, 7, and 11.[12]Modular arithmetic and coprimality
Modular arithmetic provides a framework for performing operations on integers where numbers "wrap around" after reaching a fixed modulus n, often visualized as clock arithmetic. Two integers a and b are congruent modulo n, denoted a \equiv b \pmod{n}, if n divides the difference a - b, or equivalently, if a and b leave the same remainder when divided by n.[14][15] This congruence relation is an equivalence relation that partitions the integers into n distinct residue classes, each represented by the integers from 0 to n-1. Arithmetic operations such as addition, subtraction, and multiplication are well-defined on these classes, preserving congruence: if a \equiv a' \pmod{n} and b \equiv b' \pmod{n}, then a + b \equiv a' + b' \pmod{n} and a \cdot b \equiv a' \cdot b' \pmod{n}.[16][17] A key concept in modular arithmetic is the greatest common divisor (gcd) of two integers a and n, defined as the largest positive integer d that divides both a and n without leaving a remainder. The gcd can be computed using the Euclidean algorithm, an efficient iterative process based on the property that \gcd(a, n) = \gcd(n, a \mod n), continuing until the remainder is zero, at which point the last non-zero remainder is the gcd.[18][19] Two integers a and n (with n > 0) are said to be coprime, or relatively prime, if \gcd(a, n) = 1; for example, 5 and 8 are coprime since \gcd(5, 8) = 1, whereas 4 and 6 are not, as \gcd(4, 6) = 2. A fundamental property is that if \gcd(a, n) = 1, then a possesses a multiplicative inverse modulo n, meaning there exists an integer b such that a \cdot b \equiv 1 \pmod{n}.[20][21] The multiplicative inverse b modulo n can be found using the extended Euclidean algorithm, which not only computes \gcd(a, n) but also expresses it as a linear combination $1 = a \cdot s + n \cdot t for integers s and t, where s \equiv b \pmod{n}. For instance, the inverse of 3 modulo 7 is 5, since $3 \cdot 5 = 15 \equiv 1 \pmod{7}.[22] The set of all residue classes modulo n that are coprime to n—precisely those with inverses—forms the multiplicative group of units, denoted U(n), under multiplication modulo n. This group has order equal to Euler's totient function \phi(n), the number of integers from 1 to n-1 coprime to n.[23]Statement and examples
Formal statement
Euler's theorem, also known as Euler's totient theorem, states that if n and a are integers with n > 1 and \gcd(a, n) = 1, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi denotes Euler's totient function.[1][24] The theorem applies to positive integers n \geq 2, as the case n = 1 is trivial: \phi(1) = 1 and every integer a satisfies \gcd(a, 1) = 1, but congruence modulo 1 holds universally for any integers since 1 divides all differences, rendering the statement vacuously true yet typically excluded from the theorem's scope.[1] The condition \gcd(a, n) = 1 ensures a is coprime to n, meaning no prime dividing n divides a. Although the theorem assumes a positive in its standard formulation, it extends to negative a whenever \gcd(a, n) = 1, since -a \equiv b \pmod{n} for some positive b coprime to n, and the result follows from the multiplicative inverse properties in the multiplicative group modulo n.[1] Exponentiation in the theorem is understood in the modular arithmetic sense: a^k \pmod{n} denotes the remainder when a raised to the power k is divided by n, computed via repeated multiplication modulo n to avoid large intermediates. A key corollary is that the multiplicative order of a modulo n—the smallest positive integer d such that a^d \equiv 1 \pmod{n}—divides \phi(n).[1][24] This property enables efficient computation of large powers a^k \pmod{n} by reducing the exponent modulo \phi(n), yielding a^k \equiv a^{k \mod \phi(n)} \pmod{n} when \gcd(a, n) = 1.[1]Illustrative examples
To illustrate Euler's theorem, consider the case where n = 7, a prime number. Euler's totient function gives \phi(7) = 6, since there are six integers from 1 to 6 that are coprime to 7. Take a = 2, which is coprime to 7 as \gcd(2, 7) = 1. The theorem states that $2^6 \equiv 1 \pmod{7}. To verify, compute the powers of 2 modulo 7 step by step:- $2^1 = 2 \equiv 2 \pmod{7}
- $2^2 = 4 \equiv 4 \pmod{7}
- $2^3 = 8 \equiv 1 \pmod{7}
- $2^4 = 2 \cdot 1 = 2 \equiv 2 \pmod{7}
- $2^5 = 2 \cdot 2 = 4 \equiv 4 \pmod{7}
- $2^6 = 2 \cdot 4 = 8 \equiv 1 \pmod{7}
- $3^1 = 3 \equiv 3 \pmod{10}
- $3^2 = 9 \equiv 9 \pmod{10}
- $3^3 = 27 \equiv 7 \pmod{10}
- $3^4 = 81 \equiv 1 \pmod{10}
- $2^1 = 2 \equiv 2 \pmod{9}
- $2^2 = 4 \equiv 4 \pmod{9}
- $2^3 = 8 \equiv 8 \pmod{9}
- $2^4 = 16 \equiv 7 \pmod{9}
- $2^5 = 32 \equiv 5 \pmod{9}
- $2^6 = 64 \equiv 1 \pmod{9}