輾轉相除法原理

      "輾轉相除法",中國古代叫作"更相減損求等",有兩個應用:
     (1)求兩數a,b的最大公因數
     (2)求不定方程式ax+by=c的整數解

    預備性質(1)若,則對任意整數m,n,
    預備性質(2)若,則

輾轉相除法原理
a,b是整數,則存在整數q,r,,使得a=bq+r,這叫作歐幾里德除法原理.此時(a,b)=(b,r) 這叫作輾轉相除法原理
證明
假設(a,b)=d,(b,r)=d'
因為(a,b)=d,則,由(1) ,亦即 ,由(2) ,亦即d 又,因為(b,r)=d',則,由(1) ,亦即 ,由(2) ,亦即
,所以d=d',得證

習作

1. 求(5814,6018)=
2. 試證 任意兩連續正整數互質
3. 試證 對任意正整數n,(14n+3,21n+4)=1
4. 若(p,q)=1試證(2p+3q,3p+4q)=1
5. <a_n>是費氏數列 ,即a₁=a₂=1,a_n+2=a_n+a_n+1試證(a_n,a_n+1)=1
6. 設a,b,q₁,q₂,q₃皆為正整數,且滿足,則(a,b)= ?

1. 輾轉相除法,黃金分割與費氏數列(上)
2. 輾轉相除法,黃金分割與費氏數列(下)