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
View Answer
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
View Answer
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
View Answer
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
4. Which of the following gives the value for Ø(180)?
a) 44
b) 46
c) 48
d) 50
View Answer
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
View Answer
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
View Answer
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)
View Answer
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
View Answer
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]
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Design and Analysis of Algorithms Books
- Practice Data Structure MCQ
- Apply for Computer Science Internship
