We recollect that for two positive integers a and b, the operation a mod b (a % b in java) outputs the remainder of the division operation where a is the dividend and b is the divisor. We also recollect that a prime number is a positive integer greater than or equal to 2 that is only divisible by itself and 1. Consider the Euclidean Algorithm for computing the greatest common divisor of two non-negative integers a and b, denoted as gcd(a, b). Out of the following, tick the true statements and leave the false statements unticked. (More than one of the statements could be true. You get full marks only for marking all the statements correctly. There are no partial marks.) A. The execution of the Euclidean algorithm does not require the result that for a positive integer a, we have gcd(a, 0) = a. B. When two positive integers are not divisible by any common (prime) positive integer greater than 1, the output of the Euclidean algorithm is 1. C. The Euclidean algorithm for computing gcd(a, b) requires the computation of the prime factorisations of the numbers a and b. D. At every step of the Euclidean algorithm, we use the result that for any two positive integers a and b, we have gcd(a, b) = gcd(b, a mod b).
We recollect that for two positive integers a and b, the operation a mod b (a % b in java) outputs the remainder of the division operation where a is the dividend and b is the divisor. We also recollect that a prime number is a positive integer greater than or equal to 2 that is only divisible by itself and 1.
Consider the Euclidean
Out of the following, tick the true statements and leave the false statements unticked.
(More than one of the statements could be true. You get full marks only for marking all the statements
correctly. There are no partial marks.)
The execution of the Euclidean algorithm does not require the result that for a positive integer a, we have gcd(a, 0) = a.
When two positive integers are not divisible by any common (prime) positive integer greater than 1, the output of the Euclidean algorithm is 1.
The Euclidean algorithm for computing gcd(a, b) requires the computation of the prime factorisations of the numbers a and b.
At every step of the Euclidean algorithm, we use the result that for any two positive integers a and b, we have gcd(a, b) = gcd(b, a mod b).
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
