home *** CD-ROM | disk | FTP | other *** search
/ Loadstar 12 / 012.d81 / euclidean articl < prev    next >
Encoding:
Text File  |  1985-01-01  |  1.4 KB  |  89 lines
  1.  
  2.       THE EUCLIDEAN ALGORITHM
  3.  
  4.  
  5.  
  6. The Euclidean Algorithm (or Division
  7.  
  8. Algorithm) states that given any two
  9.  
  10. positive integers a and b, there exist
  11.  
  12. unique non-negative integers a and b
  13.  
  14. such that
  15.  
  16. a = bq + r  WITH  0 <= r < b.
  17.  
  18. Note:  The combination of symbols <=
  19.  
  20. is the BASIC notation for 'less than
  21.  
  22. or equal to'.  We adopt it for these
  23.  
  24. articles since the usual symbols are
  25.  
  26. not available.
  27.  
  28. Query: Is there a suitable extension
  29.  
  30. of the Algorithm which includes the
  31.  
  32. negative integers as well?  Extension
  33.  
  34. in this context means that the
  35.  
  36. extended algorithm must agree with
  37.  
  38. the algorithm above if a and b are
  39.  
  40. both positive.  By the way, the answer
  41.  
  42. is yes.  See if you can come up with a
  43.  
  44. statement.  Try
  45.  
  46.       A=BG+R   0<=R<=ABS(B)
  47. or
  48.       A=BG+R   0<=ABS(R)<ABS(B)
  49.  
  50. where ABS(X) denotes the absolute of
  51.  
  52. X.
  53.  
  54. Example: Let a=25 and b=6. Then since
  55.  
  56. 6 'goes into' 25 four times with a
  57.  
  58. remainder of one', q=4 and r=1 are the
  59.  
  60. integers guaranteed by the Algorithm.
  61.  
  62. The uniqueness of q and r is also
  63.  
  64. guaranteed by the Algorithm.  Try to
  65.  
  66. find another pair of integers, q' and
  67.  
  68. r' such that
  69.  
  70.     25 = 6q' + r'  0 <= r' < 6.
  71.  
  72. For example, what's wrong with q'=3
  73.  
  74. and r'=7?
  75.  
  76. As a final comment on the Euclidean
  77.  
  78. Algorithm, you may not be used to the
  79.  
  80. way we have stated it, and you may not
  81.  
  82. recognize it in this form, but if you
  83.  
  84. can do long division, you already know
  85.  
  86. the Euclidean Algorithm.
  87.  
  88. --------------------------------------
  89.