Why does Euclid’s GCD algorithm work?

SANAPALA, SEETHA RAMA RAJU (2018) Why does Euclid’s GCD algorithm work? At Right Angle, 7 (1). pp. 60-61.

Text - Published Version
Download (250kB) | Preview


We start with the definition of the GCD of two numbers. (Throughout this article, ‘number’ means ‘integer.’) Definition: The GCD or ‘Greatest Common Divisor’ of two numbers, also called the Highest Common Factor (HCF), is: • A divisor of both the numbers, i.e., it is a common divisor. • Of all the common divisors, it is the greatest. Note that the GCD is a multiple of every other common factor of the two numbers.

Item Type: Articles in APF Magazines
Uncontrolled Keywords: Positive Integer, GCD, Algorithm, Reasoning, Proof
Subjects: Natural Sciences > Mathematics
Divisions: Azim Premji University > University publications > At Right Angles
Depositing User: Mr. Sachin Tirlapur
Date Deposited: 15 Sep 2018 06:59
Last Modified: 15 Sep 2018 06:59
URI: http://publications.azimpremjifoundation.org/id/eprint/1320
Publisher URL:

Actions (login required)

View Item View Item