Значения функции Эйлера

The function is Leonhard Euler's. In 1736, early in his first St Petersburg period, he published the first proof of what we now call Fermat's little theorem — that a^(p−1) ≡ 1 modulo a prime p. Fermat had asserted it in a letter in 1640 without proof, and Euler returned to it repeatedly over the following decades, looking for the version that worked for composite moduli. The generalisation he found, printed in 1763 in the St Petersburg Academy's Novi Commentarii, required knowing how many numbers below n are coprime to n. That count is the function, and the result is Euler's theorem: a^φ(n) ≡ 1 modulo n whenever a and n share no factor.

Euler had no settled notation for it. The symbol φ is Carl Friedrich Gauss's, introduced in the Disquisitiones Arithmeticae of 1801, where it anchors the treatment of primitive roots and residue classes. The English name arrived much later still: James Joseph Sylvester coined "totient" in 1879, along with "totitives" for the coprime numbers being counted. Both words were his inventions, and only the first stuck.

The function moved from pure arithmetic to infrastructure in 1977, when Ron Rivest, Adi Shamir and Leonard Adleman built their public-key cryptosystem on it. For a modulus n = pq, φ(n) = (p−1)(q−1), and the private exponent is the inverse of the public one modulo φ(n) — so knowing φ(n) is equivalent to being able to decrypt. Their paper appeared in Communications of the ACM in 1978. Modern implementations usually substitute the closely related Carmichael function λ(n) = lcm(p−1, q−1), which divides φ(n) and yields smaller exponents.

Basic questions remain open. Carmichael conjectured around 1907 that no value of φ is attained by exactly one integer; a century later that is still unproven.

Ключевые свойства

• φ(n) counts the integers from 1 to n that are coprime to n, so φ(1) = 1 and the sequence starts 1, 1, 2, 2, 4, 2, 6, 4, 6, 4.
• φ(n) = n − 1 exactly when n is prime — the condition is necessary as well as sufficient.
• φ is multiplicative: φ(mn) = φ(m)·φ(n) whenever gcd(m, n) = 1, and φ(p^k) = p^k − p^(k−1) for prime p.
• Euler’s product formula: φ(n) = n · ∏(1 − 1/p) over the distinct primes p dividing n.
• Gauss’s identity: summing φ(d) over all divisors d of n gives exactly n.
• φ(n) is even for every n ≥ 3; the only odd value it ever takes is 1, at n = 1 and n = 2.
• φ(n) > √n for every n > 6, and φ(n) ≤ n − √n for every composite n.
• Not every even number is a totient value: 14 is the smallest even number that is φ(n) for no n at all.

Где встречаются

• RSA key generation: for a modulus n = pq the decryption exponent is the modular inverse of the encryption exponent with respect to φ(n) = (p−1)(q−1). Current standards generally use the Carmichael function λ(n) instead, which divides φ(n).
• Euler’s theorem lets huge exponents be reduced modulo φ(n) before any modular exponentiation is performed — the standard shortcut in computer-algebra systems and crypto libraries.
• There are exactly φ(n) primitive nth roots of unity, so the nth cyclotomic polynomial has degree φ(n) and a cyclic group of order n has φ(n) generators.
• The Farey sequence of order n — all reduced fractions in [0, 1] with denominator at most n — has exactly 1 + φ(1) + φ(2) + … + φ(n) terms.
• Totient sums give the coprimality density: the totients up to x add up to about 3x²/π², which is the same statement as "two random integers are coprime with probability 6/π² ≈ 0.6079".
• For n coprime to 10, the repeating block in the decimal expansion of 1/n has length equal to the multiplicative order of 10 modulo n, which always divides φ(n).