Integers: a divided by b can be written as an equation:
a=bq+r
(Where q is the quotient and r is the remainder.)
r can be 0 through b-1 i.e. r < b
Said another way r=a-bq
If it turns out a and b have a common divisor k,
one could say:
a=kn and b=km substituting these for a and b
in the above.
r=kn-kmq or r=k(n-mq) which tells us that r
must also be divisible by k.
If that worked once we can do it again: divide b by r (both have the common divisor k) and get a new remainder (smaller than r) that also has the divisor k. Simply repeat this until one of the successively smaller remainders becomes zero. The last divisor is k generally called "The Greatest Common Divisor".
We start doing the divides at the right side of our "page".
8 2 1 4 1 4 1 92)736)1564)2300)10764)13064)63020)76084 736 1472 1564 9200 10764 52256 63020 0 92 736 1564 2300 10764 13064Thus, we have found 92 divides both 76,084 and 63,020 92 is divisable by: 2,4, and 23 so each of these divides either of the original two numbers. |
For this the quotients are ignored!
The process of repeatedly dividing the remainder into the divisor is the Euclidian Algorithm. It was known prior to 300 BC, but is not taught today in most of our schools. There is also a Subtraction Version which some may feel is simpler.
The mathematically inclined may know: 1,4,1,4,1,2,8 is the Continued Fraction representation of 76084/63020)=(827/685). It is used for generating "best" approximations.
Look at the quotients: 1,4,1,4,2,8 in the order generated. Spread out a little |
1 4 1 4 1 2 8 |
0 1 1 5 6 29 35 99 827 1 0 1 4 5 24 29 82 685 |
S L S L S L S L =The 2nd and 3rd lines above are fractions with the numerator on the second line and the denominator on the third. In the line above the "S" and the "L" indicates if the fraction is Smaller or Larger than the value being approximated. Yes, they always alternate. Consequently, the error of any fraction is less than the difference between it and the next one. Note: (76084/63020)=(827/685)=1.2072992... and (6/5)=1.20 (29/24)=1.2083... (35/29)=1.20689... |
3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1 2 2 2 2 1 84 2 1 1 15 3 13 1 4 2 6 6 99 1 2 2 6 3 5 1 1 6 (The following are correct for the 50 digit truncated approximation of Pi. But, a more accurate value for Pi gives 8 instead of 9 for the next value, and different following values. The following values are not correct for Pi, but they are correct for this 50 place value which is less than Pi.) 9 3 2 1 1 1 17 2 33 1 6 2 5 1 1 1 26 1 4 10 1 1 4 2 6 2 3 2 1 65 2 1 13 1 8 1 1 18 10 2 3 1 3 1 7 1 1 3Yes, I did convert a 1000 digit approximation, but decided for here this is enough, and I wanted to make a point about approximate values. It is interesting to change the last digit 0 to a 1 and convert that larger than Pi value. |
Multiple precision division was necessary.
Go to: My Home Page | Go to: This page TOP |