Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Greatest Common Divisor Algorithm

IP.com Disclosure Number: IPCOM000080123D
Original Publication Date: 1973-Jan-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 2 page(s) / 32K

IBM

Cuff, RN: AUTHOR

Abstract

The drawing shows a method for finding the greatest common divisor (GCD) of a set of positive integers. It does not involve decomposition into primes, and is largely independent of the size of the integers and their pairwise differences. It relies on the fact that the GCD of X and Y is also the GCD of Y and X - mY for any integer m.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 2

Greatest Common Divisor Algorithm

The drawing shows a method for finding the greatest common divisor (GCD) of a set of positive integers. It does not involve decomposition into primes, and is largely independent of the size of the integers and their pairwise differences. It relies on the fact that the GCD of X and Y is also the GCD of Y and X - mY for any integer m.

Let the numbers be N(1), N(2),...,N(J). Initially (step 1) the first pair is assigned to T and V. Step 2 assigns the larger to C and the smaller to A. Step 3 calculates the remainder of C/A. If the division was not exact (step 4), then (step
5) the two smallest values (the remainder and A) are substituted and step 3 repeated. Eventually an exact division is found, and the current value of A is the GCD of the pair.

If the end of the input list is reached (step 6), or there is already two coprime numbers the final GCD must be unity, then the process is complete. Otherwise (step 7), the GCD of A must be found and the next input number, and so on.

1

Page 2 of 2

2