Confirming your payment

Skip to content

Competency-Based Questions (CBQ) · Question 37 of 40

A coding club must share 217 badges and 155 stickers equally among the largest possible number of members, so it needs…

Question 373 marksHard

A coding club must share 217 badges and 155 stickers equally among the largest possible number of members, so it needs gcd⁡(217,155)\gcd(217, 155). The members compare how much work five methods take. Count one check for each number tested, and one reduction for each use of Step 3 of Euclid's algorithm.

Table of five gcd methods with an empty column for the amount of work

(i) Find the number of checks for methods 1, 2 and 3.

(ii) Method 4 checks k=155,154,…k = 155, 154, \ldots downwards and stops at the first kk dividing both numbers, counting that kk. At which kk does it stop, and how many checks does it make?

(iii) Find the number of reductions for method 5. Rank the five methods from least to most work.