Why does Euclid’s GCD algorithm work?

Sanapala, Seetha Rama Raju (2018) Why does Euclid’s GCD algorithm work? At Right Angles, 7 (1). pp. 60-61. ISSN 2582-1873

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
Authors: Sanapala, Seetha Rama Raju
Document Language:
Uncontrolled Keywords: Positive Integer, GCD, Algorithm, Reasoning, Proof
Subjects: Natural Sciences > Mathematics
Divisions: Azim Premji University > University Publications > At Right Angles
Full Text Status: Public
URI: http://publications.azimpremjiuniversity.edu.in/id/eprint/1320
Publisher URL:

Actions (login required)

View Item View Item