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

Fwd: [PrimeNumbers] Euclid's Lemma

Expand Messages
  • Hugo Scolnik
    The classical analysis of the GCD algorithm uses the Fibonacci sequence Theorem: If a b.ge.0 and the Euclid s algorithm uses k.ge.1 recursive steps then
    Message 1 of 1 , Jan 22, 2013
    • 0 Attachment
      The classical analysis of the GCD algorithm uses the Fibonacci sequence

      Theorem: If a>b.ge.0 and the Euclid's algorithm uses k.ge.1 recursive
      steps then a.ge.F(k+2) and b.ge.F(k)

      where

      F(0) = 0
      F(1) = 1
      F(i) = F(i-1) + F(i-2) for i.ge.2

      Best

      --
      Hugo Scolnik
    Your message has been successfully submitted and would be delivered to recipients shortly.