Which function counts the positive integers up to n that are relatively prime to n?

Which function counts the positive integers up to n that are relatively prime to n?

• A. Euler's Totient Function
• B. Greatest Common Divisor
• C. Least Common Multiple
• D. Möbius Function

Answer: (A)

Relating numbers to n by a common factor is the idea here: we want to know how many integers from 1 through n share no factor with n. The function that counts exactly that is Euler’s totient function, usually written φ(n). It counts the integers k in the set {1, 2, ..., n} for which gcd(k, n) = 1, meaning k and n are coprime. This is why it’s the right tool for the problem. For intuition, take n = 10. The numbers from 1 to 10 that are coprime to 10 are 1, 3, 7, and 9, so φ(10) = 4. The other options don’t perform this counting: the greatest common divisor reduces two numbers to their largest shared factor; the least common multiple finds the smallest multiple they both divide; and the Möbius function assigns -1, 0, or 1 based on prime factors, not a counting of coprimes.

Relating numbers to n by a common factor is the idea here: we want to know how many integers from 1 through n share no factor with n. The function that counts exactly that is Euler’s totient function, usually written φ(n). It counts the integers k in the set {1, 2, ..., n} for which gcd(k, n) = 1, meaning k and n are coprime. This is why it’s the right tool for the problem.

For intuition, take n = 10. The numbers from 1 to 10 that are coprime to 10 are 1, 3, 7, and 9, so φ(10) = 4. The other options don’t perform this counting: the greatest common divisor reduces two numbers to their largest shared factor; the least common multiple finds the smallest multiple they both divide; and the Möbius function assigns -1, 0, or 1 based on prime factors, not a counting of coprimes.