這題贈送給很愛思考數學的人(但要知道輾轉相除法)

Question

輾轉相除法是用來找公因數用的 這我知道

但我不知道 為什麼輾轉相除法可以用來找公因數

請知道的人幫我 謝謝

Answer 1

假設兩數
A= a*c
B=b*c
假設 A>B
c 為其最大公因數
輾轉相除法的步驟就是互除 留餘數
so, first
A-(n*B)=(a-nb) *c; n 為任何自然數 1,2,3....
為了方便 R1=(a-nb)*c ; r1=(a-nb); R1=r1*c; 要注意 r1有可能是 1
由此可知 r1 也是 c 的倍數
下一步..
B-(n*R1)=(b-n*r1)*c; 假設 r1是1 這個結果會等於零 也就是說 b-n*r1 等於零
這時你就知道 c 是最大公因數
如果不等於零 繼續下去 反正你的餘數的因數 包含了這個解
example
找最大工因數 of 32,56
B=32=8x4
A=56=8x7
56-32 =(7-4)x8=24;
下一步
32-24=8
下一步
24-3*8=0
因此可知8 解