Question

____________ is an arithmetic function that calculates the total number of positive integers less than or equal to some number n, that are relatively prime to n.

(a) Euler’s phi function

(b) Euler’s omega function

(c) Cauchy’s totient function

(d) Legrange’s function

I had been asked this question during an internship interview.

The above asked question is from Number Theory topic in section Number Theory of Data Structures & Algorithms II

Answer 1

The correct answer is (a) Euler’s phi function

The best explanation: Euler’s phi function is an arithmetic function that calculates the total number of positive integers less than or equal to some number n, that are relatively prime to n. The inclusion-exclusion principle is used to obtain a formula for Euler’s phi function.