Contact me at:
For comments call, or e-mail me. Go to My Home Page or TOP of this page.
Almost a definition of a divided by b is:
a=bq+r
where q is the quotient and
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.
Repeat until one of the successively smaller remainders
becomes zero. The last divisor is k.
This process of repeatedly dividing by the remainder is the Euclidian Algorithm, which was know at least 300 BC but is not taught in most of our schools.
Example: 76,084 and 63,020
76084=1*62020+13064
62020=4*13064+10764
13064=1*10764+2300
10764=4*2300+1564
2300=1*1564+736
1564=2*736+92
736=8*92
Thus we know that 92 divides both 76,084 and 63,020
|
| 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... |
To give you some practice generating "best rational approximations" here are the C.F values you would get using Pi to 50 decimal places.
Pi to 50 decimal places
3,14159 26535 89793 23846 26433 83279 50288 41971 69399 37510
Converted to Continued Fractions Sat 03-11-22 using IA.COM
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 above value. But, a more accurate value
for Pi gives 8 instead of 9 for the next digit and all the rest are
different.)
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 3
|