totatives

Totatives of a positive integer n are the integers k in the range 1 ≤ k ≤ n that are coprime to n, i.e., gcd(k, n) = 1. In other words, they are the numbers less than or equal to n that share no prime factor with n. For n > 1, n itself is not a totative because gcd(n, n) = n > 1; for n = 1 the totative is {1}.

The totatives are counted by Euler's totient function φ(n), so there are φ(n) totatives. The set of totatives forms the reduced residue system modulo n, representing the units of the ring Z/nZ. Consequently, the totatives correspond to the congruence classes modulo n that are relatively prime to n.

Examples illustrate the concept: for n = 12, the totatives are {1, 5, 7, 11} and φ(12) = 4. If n is prime, say p, every integer 1 ≤ k ≤ p−1 is a totative, so φ(p) = p−1.

Several properties follow from the definition. If a is a totative of n, then so is n−a (modulo n) and gcd(a, n) = 1 implies gcd(a^m, n) = 1 for any positive integer m. In number theory, the set of all totatives modulo n forms the multiplicative group of units modulo n, of order φ(n). Euler's theorem states that if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). The concept is central to the study of modular arithmetic and arithmetic functions.

---