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

Publishing Venue

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

[This page contains 2 pictures or other non-text objects]