Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

shakil.ahamed's blog

Continued fraction: Convergent and GCD
By shakil.ahamed, history, 7 years ago, In English

I am trying to understand continued fraction. But I am unable to understand a statement from SY Yan's book.

Say, a/b = [q0, q1, ...., qn] where qi's are the partial quotients of the fraction. Then, the kth convergent of this fraction is the fraction which have a representation denoted by [q0, q1, ...., qk].

Now, lets the kth convergent is Ck. Then, Ck = Pk/Qk = (qk*Pk-1 + Pk-2)/(qk*Qk-1 + Qk-2) .... (1)

So far I have verified the statements and they are consistent.

But, then Yan stated that, if, Pk = qk*Qk-1 + Qk-2 and Qk = qk*Pk-1 + Pk-2, then GCD(Pk, Qk) = 1 ...... (2)

But, How it can be? As, (2) and (1) impiles Pk/Qk = Qk/Pk, implies Pk = Qk. What did I miss?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Sorry for my terrible english in advance.

P(k) is not always the same as Q(k) because P(0) and Q(0) are different, and P(1) and Q(1) are also different.

say, a/b = [a(0),a(1),a(2),,,,a(n)]

Then Q(0) = 1, Q(1) = a(0) , and P(0) = a(0) , P(1) = a(0) x a(1) + 1.

Although recurrence relation have same form, first and second terms are different.

Therefore, P(k) ans is not always same as Q(k).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me how the second and first equation works consistently? Maybe an concrete example will be helpful.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      First equation can be proven by mathematical induction. Try it. It isn't hard to calculate. It is little bit messy to write on here...

      For Example, ( by Elementary number theory — Kenneth H.Rosen — Sixth Edition ) 173/55 = [3 ; 6 , 1, 7 ]

      P(0) = 3, Q(0) = 1 , C(0) = 3 = P(0)/Q(0)

      P(1) = a(0) * a(1) + 1 = 19 , Q(1) = a(1) = 6 C(1) = [3 ; 6 ] = 3 + 1/6 = 19/6 = P(1) / Q(1)

      P(2) = P(1) * a(2) + P(0) = 22 , Q(2) = Q(1) * a(2) + Q(0) = 7

      C(2) + [ 3 ; 6 , 1] = 3 + 1/ (6 + 1/1) = 22/7 = P(2)/Q(2)

      like this.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      If you know additional theorem , it will be easy to show second equation correct

      P(k)*Q(k-1) — Q(K)*P(k-1) = (-1)^(k-1)

      It can be proven by mathematical induction too. assgin the above example's value.

      And you should know if a*x + b*y = c have solution, then GCD(a,b) | c.

      it means that (P(k),Q(k)) | (-1)^(k-1) if you consider Q(k-1) as x and consider P(k-1) as y.

      (-1)^(k-1) is either 1 or -1.

      Therefore, GCD(P(k),Q(k)) = 1.

      (once more, sorry for my terrible English.)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Your English is good. But my math understanding is not. Anyway, your comment give me some light. I need to spend few more hours to get comfortable with it I think. Thank you.

        And, congrats for your color!

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah! It looks like the kth convergent are always in reduced form. I mean, for any Ck = Pk/Qk, calculating using the above recurrence, Pk, Qk are relatively prime.

        But, did you notice the second equation? The Pk and Qk aren't in the correct place I think.

        Also, He meant, if A then B, but it should be A and B(with Pk and Qk exchanges their place, as of my current understanding, it won't be consistent otherwise).

        The only place where Pk and Qk will be equal is the 0'th convergent where a <= b < 2*a

        → Reply