Loading ...
Sorry, an error occurred while loading the content.

Factor question (not directly prime related).

Expand Messages
  • kradenken
    I m sure the following is true but is it a known theorem. If so what is it called. Given a pair of rational (i.e they dont need to be integer) factors of an
    Message 1 of 2 , Apr 28, 2006
    • 0 Attachment
      I'm sure the following is true but is it a known theorem.
      If so what is it called.
      Given a pair of rational (i.e they dont need to be integer) factors of
      an integer N; p/q and Nq/p
      then the rational (p+Nq)/(q+p) lies between p/q and Nq/p
      This is effectively saying (p+Nq)/(q+p) is a better approximation to
      SQRT(N) than p/q
      A proof would be nice but if someone could just point me at the
      appropriate theorem I would appreciate it.
      Cheers
      Ken
    • Chris Caldwell
      ... Let a 1. Then a a, and (a+c*b)/(1+c) = b - (b-a)/(1+c)
      Message 2 of 2 , Apr 28, 2006
      • 0 Attachment
        > I'm sure the following is true but is it a known theorem.
        > If so what is it called.
        > Given a pair of rational (i.e. they dont need to be integer)
        > factors of an integer N; p/q and Nq/p then the rational
        > (p+Nq)/(q+p) lies between p/q and Nq/p This is effectively
        > saying (p+Nq)/(q+p) is a better approximation to
        > SQRT(N) than p/q
        > A proof would be nice but if someone could just point me at
        > the appropriate theorem I would appreciate it.



        Let a < b and c > 1. Then a < (a+c*b)/(1+c) < b

        Proof. (a+c*b)/(1+c) = a + c*(b-a)/(1+c) > a,
        and (a+c*b)/(1+c) = b - (b-a)/(1+c) < b. End proof.

        Your result:

        Note (p+Nq)/(q+p) = (p/q + N)/(1 + p/q) = (Nq/p + 1)/(1 + q/p)

        follows from:

        if a=p/q < b=Nq/p, then let c=p/q.
        if a=Nq/p < b=p/q, then let c=q/p.
      Your message has been successfully submitted and would be delivered to recipients shortly.