UPSC CDS 2 2020 Math Paper

Concept:The Euclidean algorithm is used to find the greatest common divisor (GCD) or highest common factor (HCF) of two integers.Explanation:Given two positive integers $a$ and $b$, the algorithm uses repeated division.We write $a = bq + r$, where $q$ is the quotient and $0 \le r < b$.Then $\text{GCD}(a, b) = \text{GCD}(b, r)$.This process is repeated until the remainder $r$ becomes zero.The last non-zero remainder is the GCD or HCF of the original two integers.Thus, the Euclidean algorithm calculates the HCF of two integers.Answer:Option D: HCF of two integers