home *** CD-ROM | disk | FTP | other *** search
/ Loadstar 12 / 012.d81 / gcd article < prev    next >
Encoding:
Text File  |  1985-01-01  |  1.4 KB  |  94 lines
  1.  
  2.       THE GCD OF TWO INTEGERS
  3.  
  4.  
  5.  
  6. DEFINITION: The GREATEST COMMON
  7.  
  8. DIVISOR (GCD) of two integers, A and
  9.  
  10. B, is an integer D which satisfies the
  11.  
  12. following two criteria:
  13.  
  14.  i)  D divides A and D divides B.
  15.  
  16. ii)  if D' is any other divisor of
  17.      both A and B, then D' also
  18.      divides D.
  19.  
  20. We use the notation (A,B) to denote
  21.  
  22. the GCD of A and B.
  23.  
  24. Repeated use of the Euclidean
  25.  
  26. Algorithm provides a method for
  27.  
  28. finding the GCD of two positive
  29.  
  30. integers.
  31.  
  32. THEOREM:  Let A and B be two positive
  33.  
  34. integers.  Then the following
  35.  
  36. algorithm results in the GCD of A and
  37.  
  38. B:
  39.  
  40. Assume, without loss of generality,
  41.  
  42. that B<A.  Then applying the Euclidean
  43.  
  44. Algorithm, there exist unique integers
  45.  
  46. C and D such that
  47.  
  48.      A = CB + D,   0 <= D < B.
  49.  
  50. If D=0, then B is the GCD of A and B.
  51.  
  52. If D#0, then divide B by D.
  53.  
  54.      B = ED + F    0 <= F < D
  55.  
  56. Now divide D by F.
  57.  
  58.      D = GF + H    0 <= H < F
  59.  
  60. Continuing in this way, always
  61.  
  62. dividing the divisor by the remainder,
  63.  
  64. we get a STRICTLY decreasing sequence
  65.  
  66. of remainders which must eventually
  67.  
  68. end with 0  (because the integers are
  69.  
  70. well-ordered).
  71.  
  72. Then the last non-zero remainder is
  73.  
  74. the GCD of A and B.
  75.  
  76. EXAMPLE: Let A=168 and B=30. Find the
  77.  
  78. GCD and LCM.
  79.  
  80.       168 = (30)(5) + 18
  81.        30 = (18)(1) + 12
  82.        18 = (12)(1) + 6
  83.        12 = (2)(6)
  84.  
  85. The GCD is 6.
  86.  
  87. The LCM is (168)(30)/6 = 840.
  88.  
  89. Press '\' if you  would like to run
  90. \oad "gcd",8
  91. GCD now.
  92.  
  93. --------------------------------------
  94.