Confirming your payment

Skip to content

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

For Diwali, Kavya wants to pack 500 diyas and 36 candles into identical gift packs, making as many packs as possible…

Question 384 marksHard

For Diwali, Kavya wants to pack 500 diyas and 36 candles into identical gift packs, making as many packs as possible with nothing left over. Her grandfather tells her that Āryabhaṭa's Āryabhaṭīya (499 CE) found such answers by repeated division instead of repeated subtraction. Kavya runs Euclid's subtraction algorithm, which reduces gcd⁡(m,n)\gcd(m, n) to gcd⁡(n,m−n)\gcd(n, m - n). Her brother runs Āryabhaṭa's division algorithm, which reduces gcd⁡(m,n)\gcd(m, n) to gcd⁡(n,m mod n)\gcd(n, m \bmod n). Both reverse the numbers when m<nm < n, and each use of the reduction step counts as one reduction.

Table of the items to pack: 500 diyas and 36 candles

(i) What problem does Kavya get after her first reduction?

(ii) Write her brother's full trace, with each remainder.

(iii) How many reductions does each of them make? How many packs are made, and what is in each pack?