... Note: the partial quotients of a fraction are not the same as the remainders in the Euclidean algorithm operation, unless the fraction is a Positive Silver
Message 1 of 1
, Sep 26, 2002
--- In Guruevents@y..., "purushaz" <purushaz@y...> wrote:
Note: the partial quotients of a fraction are not the same as the
remainders in the Euclidean algorithm operation, unless the fraction
is a Positive Silver Mean convergent., such as .618...in which case
the series is bar[N].
Take [1,2,3,4] which is 30/43. We can write
1 3 3 4 and underneath, the partial quotients:
1/1 2/3 7/10 30/43 (our fraction in question). But getting out our
pocket calculator and performing the Euclidean algorithm operation,
we first get 1 and 13/30 and we see that 13/30 is not in the above
set of partial quotients. Therefore, we can appeal to a different
method of obtaining a fraction, given the continued fraction terms
[a,b,c...] as follows:
Our fraction is [1,2,3,4]. We start at the right and underneath
the "3", write the inverse of rightmost term giving 1/4. For all
successive terms going to the left, transfer current demominator to
next LEFT numerator. Next denominator is Current continued fraction
term in [a,b,c...] times current denominator, PLUS current numerator.
Simple when you practice. Remember: current denominator gets
transferred to NEXT (going to the left) numerator position, so for
1 2 3 4
30/43 13/30 4/13 1/4
...so that the terms 13/30, 4/13, 1/4 are our remainders using the
Euclidean algorithm, pocket calculator method. i.e 43/30 = 1 & 13/30,
30/13 = 2 and 4/13, etc. The aforegoing can be mapped on a
succession of operations using 1/(1+x) and x/(1+x).
take 30/43 and successively subtract numerator from denominator, then
for the next fraction, going to the right, SUM of n+d has to equal
previous d AND n must be less than d. This forces only one result,
30/43, 13/30, 13/17, 4/13, 4/9, 4/5, 1/4, 1/3, 1/2, 1/1. Then,
starting from the left, note the numbers of terms having repeat
numerators and write the numbers of such terms down: getting....
1 2 3 4 bingo... our
continued fraction terms : [1,2,3,4]. Note that in this series,
the Euclidean algorithm fractions shown in the previous results are
mapped directly onto the series, as first fraction having identical
repeat numerators: 30/43, 13/30, 4/13, and 1/4.
Last but not least, the procedure of finding if p is q quadratic
residue of p is a type of Euclidean alogorithm operation, shortened
by factoring and using the convenient rules for the
Euler/Legendre/Gauss procedure. .....Gary Adamson
--- End forwarded message ---
Your message has been successfully submitted and would be delivered to recipients shortly.