If A and B are integers (whole numbers) then a common divisor (or common factor) of A and B is an integer which divides both numbers. And, the greatest common divisor (or highest common factor) of A and B is the largest such integer.
For instance, 3 is a common divisor of 12 and 18. But 6 is the greatest common divisor of 12 and 18.
Calculating the greatest common divisor of two numbers is not particularly complicated. Especially for a computer. The method employed serves as a good illustration of a computational algorithm.
The Euclidean algorithm is the most well-known and oldest (third century B.C.) method of computing the greatest common divisor. If you want to find the greatest common divisor of A and B then the procedure is as follows.
1. Rename A and B (if necessary) so that A is greater than B.
2. Divide A by B and find the remainder R1.
R1 = A MOD B
Notice that every number that divides A and B also divides R1. And, conversely, every common divisor of B and R1 is also a divisor of A. It follows that the common divisors of A and B are the same as those of B and R1. Thus the greatest common divisor of A and B equals the greatest common divisor of B and R1.
3. Now divide B by R1 and find the remainder R2.
R2 = B MOD R1
The remarks made above between the numbers B, R1 also apply to R1, R2. Thus the greatest common divisor of A and B equals the greatest common divisor of R1 and R2.
4. Next, divide R2 by R1 to get a remainder R3.
R3 - R1 MOD R2
The process is continued in this manner until the remainder is zero. Notice that the remainders are decreasing on each occasion and so reach zero after a certain number of steps.
R1 = A MOD B | (0 < = R1 < B) | |
R2 = B MOD R1 | (0 < = R2 < R1) | |
R3 = R1 MOD R2 | (0 < = R3 < R2) | |
· | · | |
· | · | |
· | · | |
RN-1 = RN-3 MOD RN-2 | (0 < = RN-1 < RN-2) | |
RN = RN-2 MOD RN-1 | (RN = 0) |
Listing 3.1
LIST
10 REM Greatest common divisor 20 MODE 1:COLOUR 3:PRINT ' TAB(3);"Gr eatest common divisor"':@%=10 30 PRINT "This program calculates the greatest common divisor of two integ ers using theEuclidean algorithm."' 40 COLOUR 1:PRINT '"Enter the two int egers:" 50 REPEAT 60 INPUT '" First integer: ";A% 70 PRINT " First integer is ";A% 80 IF A%<1 THEN COLOUR 3:PRINT '"A p ositive integer please.":COLOUR 1 90 UNTIL A%>0 100 REPEAT 110 INPUT '"Second integer: ";B% 120 PRINT "Second integer is ";B% 130 IF B%<1 THEN COLOUR 3:PRINT '"A p ositive integer please.":COLOUR 1 140 UNTIL B%>0 150 IF A%<B% THEN C%=A%:A%=B%:B%=C% 160 REM The Euclidean algorithm 170 R%=A%:S%=B% 180 REPEAT 190 TEST=-1 200 T%=R% MOD S% 210 IF T%<>0 THEN R%=S%:S%=T%:TEST=0 220 UNTIL TEST 230 COLOUR 2:PRINT '"The greatest comm on divisor is: "; 240 IF LEN(STR$(S%))>8 THEN PRINT 250 PRINT ;S% 260 PRINT '"The least common multiple is: "; 270 T=A%*B%/S% : REM Used in case of l arge numbers 280 IF T>&7FFFFFFF AND LEN(STR$(T))>10 THEN PRINT 290 IF T<=&7FFFFFF THEN T%=A%*B%/S% EL SE T%=1 300 IF LEN(STR$(T%))>10 THEN PRINT 310 IF T>&7FFFFFF THEN PRINT ;T ELSE P RINT ;T% 320 COLOUR 3:PRINT CHR$(7) '' TAB(10); "Another go? Y or N "; 330 REPEAT:G$=GET$:UNTIL G$="Y" OR G$= "N" 340 IF G$="Y" THEN RUN 350 CLS:PRINT '"Bye for now.":END
RUN
Greatest common divisor This program calculates the greatest common divisor of two integers using the Euclidean algorithm. Enter the two integers: First integer: ?148 First integer is 148 Second integer: ?259 Second integer is 259 The greatest common divisor is: 37 The least common multiple is: 1036 Another go? Y or N
The program also calculates the least common multiple of A and B. The least common multiple of two numbers A and B is the smallest number which is divisible by both A and B. The value of the least common multiple of A and B is given by
A*B/(greatest common divisor)
If the greatest common divisor of A and B is D then it is possible to write D as a combination of A and B:
D = S*A + T*B
where S and T are integers. The values of S and T can be found by working backwards with the Euclidean algorithm. Modify the greatest common divisor program so that it also computes S and T.