藍色情懷

下面是今年大學 的文言文數學題~~~大家看一下吧

今有多數21，少數15，問等數幾何？草曰：置21於上，15於下，以下15除去上21，上餘6；又以上6除去下15，下餘3；又以下3除去上6，適盡。則下3為等數合問。在上文中『等數』指的是:




這一題是在做21和15的展轉相除法，所以
答案是兩數之最大公因數(3)。

歐幾里得算法就是求最大公約數的展轉相除法。用c語言描述如下：
int Euclid_Algorithm (int m, int n)
{
        int temp = m;

        if (!m || !n) return 0;
        if (m < n)    {m = n; n = temp;}

        while (1) {
                if (!(m = m % n)) return n;
                if (!(n = n % m)) return m;
        }
}

    knuth說：當m,n取某兩個巨大的數時，展轉的次數超過百萬次。
    我開始還不相信，又翻了幾頁發現用fibonacci數就能找到展轉次數最多的兩個數，這兩個數就是F[n]和F[n+1]^_^，很容易驗證最大展轉次數k = log<G>(n)，就是以黃金分割G為底n的對數。
    寫到這裡就算完了，但還須證明一個先決條件，就是fibonacci相臨兩項互質。一個方法是利用這個性質：
      F[n-1] * F[n+1] - F[n]² = (-1)ⁿ
    =>F[n-1]² + F[n-1] * F[n] - F[n]² = (-1)ⁿ
    說明F[n-1]與F[n]是互素的，因為其中任何公因子都將是(-1)ⁿ的一個因子。