Dismiss
InnovationQ will be updated on Sunday, Jan. 21, from 9am - 11am ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

# Greatest Common Divisor Algorithm

IP.com Disclosure Number: IPCOM000074659D
Original Publication Date: 1971-May-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 2 page(s) / 27K

IBM

## Related People

Martino, MJ: AUTHOR

## Abstract

The drawing shows a method for finding the greatest common divisor, GCD, of two integers which are both large in relation to their difference. As step 1 shows, the larger of the two integers is designated N1 and the smaller is designated N2. In step 2, the two integers are subtracted to form the difference M. (M is smaller than either N1 or N2). In step 3, M is tested to determine whether it is prime. If M is prime, the GCD is either M or 1. Block 4 shows the step of testing whether M is a divisor N1.

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 two integers which are both large in relation to their difference. As step 1 shows, the larger of the two integers is designated N1 and the smaller is designated N2. In step 2, the two integers are subtracted to form the difference
M. (M is smaller than either N1 or N2). In step 3, M is tested to determine whether it is prime. If M is prime, the GCD is either M or 1. Block 4 shows the step of testing whether M is a divisor N1.

If M is not prime, it is factored into powers of primes. For example, for M = 60, M has the factors 2/2/. 3/1/. 5/1/. As step 7 shows, the greatest common divisor is the product of the powers of prime factors of M which divide evenly into N1. For example, for N1 = 200 and N2 = 140, and M = 60, N2 has the factors 2/2/. 5/1/. 7/1/. In the factors of M already set out, 2/2/ and 5/1/ appear. Thus, the greatest common divisor of 200 and 140 is 2/2/. 5/1/ = 20.

Step 6 is an optional step which may reduce the computation. Each of the prime factors of M is divided into N1. In the example, 140 is divided successively by 2, 5 and 7. If the prime factor does not divide evenly, it is not necessary to test in the operation of step 7 whether the power of the prime factor divides evenly.

1

Page 2 of 2

2