Euler’s Totient Function Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Euler’s Totient Function”.

1. Which of the following counts the number of integers between 1 and N, which are relatively prime to N?
a) Euler’s totient function
b) Catalan numbers
c) Factorial of a number
d) Fibonacci series

Explanation: If N is any positive integer, then the phi function returns the positive integers less than N, which are co-prime to N. This is called Euler’s totient function. The Euler’s totient function is denoted by a Greek letter as Ø(n). For example, Ø(3) = 2 (1 and 2 are co-prime to 3).

2. What does co-prime mean in the Euler’s totient function?
a) lcm(a, b) = 1
b) gcd(a, b) = 1
c) gcd(a, b) = 2
d) lcm(a, b) = 2

Explanation: Two numbers a and b are said to be relatively prime if the greatest common divisor of both the number is equal to 1. Hence, in Euler’s totient function co-prime means gcd(a, b) = 1 and 1 is the co-prime to any number.

3. What will be the output of the following code in C++?

```#include <stdio.h>
int ETF(int n)
{
int a, result = n;
for (a = 2; a * a <= n; ++a)
{
if (n % a == 0)
{
while (n % a == 0)
n = n / a;
result = result - result / a;
}
}
if (n > 1)
result = result - result / n;
return result;
}
int main()
{
int n;
for (n = 1; n <= 4; n++)
printf("%d\n", ETF(n));
return 0;
}```

a) 0 1 2 3
b) 0 1 2 4
c) 1 1 2 2
d) 1 2 3 4

Explanation: The above code is the implementation of Euler’s totient function in C++. It gives the totient function for n = 1, 2, 3, 4. The values are: Ø(1) = 1, Ø(2) = 1, Ø(3) = 2, Ø(4) = 2. Hence, the output of the following code will be 1 1 2 2.
Output:

`1 1 2 2 `
Note: Join free Sanfoundry classes at Telegram or Youtube

4. Which of the following gives the value for Ø(180)?
a) 44
b) 46
c) 48
d) 50

Explanation: Instead of iterating all the numbers from 1 to n – 1, the value of Euler’s totient function can also be given by Euler’s product formula as Ø(n) = n (1 – ) (1 – ) . . . (1 – ). , . . . are the prime factors of n. Here, 180 can also be written as (22 * 32 * 5). Hence, by substituting 2, 3 and 5 in the given equation, we get the value of Ø(180) as 48.

5. Euler’s totient function is multiplicative.
a) True
b) False

Explanation: A function f with integers as its domain, two numbers a and b are said to be multiplicative if f(ab) = f(a)*f(b), provided that a and b are relatively prime. Euler’s totient function is a multiplicative function as, Ø(ab) = Ø(a)Ø(b), where a and b are co-prime.

6. The Euler’s totient function of a prime number will be (p – 1), where p is a prime number.
a) True
b) False

Explanation: Totient function returns the number of positive integers, less than n, that are co-prime to N. For a prime number p, it will count all the numbers from 1 to p – 1 but not p. Hence, the Euler’s totient function of a prime number will be p – 1, where p is a prime number.

7. Which of the following property of Euler’s totient function is used in RSA algorithm?
a) Ø(ab) = (a – 2)(b – 2)
b) Ø(ab) = (a)(b)
c) Ø(ab) = (a – 1)(b – 1)
d) Ø(ab) = (2a)(2b)

Explanation: The property of Euler’s totient function Ø(ab) = (a – 1)(b – 1), where a and b are two prime numbers, is used in the RSA algorithm. This property of Euler’s totient function is used to assure the secrecy in calculating the private key.

8. Which of the following is an application of Euler’s totient function?
a) Pre-order traversal
b) To find the number of generators in a cyclic group
c) Number of possible BST in a tree
d) Detecting cycle in a graph

Explanation: An element A is said to be the generator of the set, if A is smaller than the total number of elements and with the help of A, we can generate all the elements of the group. For any number n, the number of generators is equal to the Euler’s totient function of n.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]