圖例淺談歐氏輾轉相除法

左圖是一個長方形,長34,寬10,
並以最少數的大小正方形鋪排而成。

圖例中

 

  34 10 = 3...4

 10   4 = 2...2

   4 2= 2...0

34=103+4

10=42+2

4=22


34=103+4=(24+2)3+(22)=
212+23+22=217
10=42+2=(22)2+2=42+2=52
因為(17,5)=1,所以(10,34)=2

此外,
2=10-4
2=10-(34-30)2=10-(34-310)2
 =10-34
2+3102=107+34(-2)
所以 (10,34)=10
7+34(-2)



               歐氏輾轉相除法(演算器)

               m =    n =   

                             


              最大公因數 gcd (m,n) =                                               

              最小公倍數 lcm (m,n) = 

               (歐幾里德)                                                                                                                                                                       

           mx+ny=(m,n) :    

  


Copyright ©昌爸工作坊 all rights reserved