Arithmetic function φ(n) that counts the positive integers up to n that are coprime to n; equivalently, the order of the multiplicative group of units modulo n.

Principle

Multiplicative and given on prime-power factorization by φ(p^a) = p^a − p^{a−1}; more generally φ(n) = n ∏_{p|n} (1 − 1/p) for n ≥ 1. It reflects how prime divisors reduce the count of invertible residues.

Demonstration

Example: n = 12 has prime factorization 2^2·3, so φ(12) = 12·(1−1/2)·(1−1/3) = 12·1/2·2/3 = 4; the invertible residues modulo 12 are {1,5,7,11}.

Misapplication

Using φ for non-integer inputs, applying multiplicativity without the coprimality requirement (e.g., assuming φ(ab)=φ(a)φ(b) when gcd(a,b)≠1), or confusing φ(n) with the count of prime factors leads to incorrect conclusions.

Consequence

φ(n) determines the structure and size of (Z/nZ)^×, underpins Euler's theorem a^{φ(n)} ≡ 1 (mod n) for gcd(a,n)=1, and is central to public-key cryptography and group-theoretic counting arguments in number theory.

Reversal

The complementary perspective is to count non-coprime residues (n − φ(n)) or to study the exponent of the unit group (Carmichael function λ(n)) which measures the least exponent e with a^e ≡ 1 (mod n) for all units rather than the group order.

Boundary

Defined for positive integers n (with φ(1)=1); extensions to rational or real arguments are not arithmetic in the same way. The multiplicativity holds only across coprime factors; formulae depend on the prime-power factorization.

Semantic Tension

Often compared with the Carmichael function λ(n) (related to exponents rather than order) and with counting functions like the number-of-prime-factors functions; confusion arises when one substitutes order for exponent or local behavior for global average properties.

Synthesis

Euler's totient φ(n) is the multiplicative arithmetic measure of how many residues modulo n are invertible; computed from the prime-power factorization, it encodes both local prime obstruction and global group-theoretic size information used across elementary and computational number theory.