Re: [解題] 最大公因數

[hightacps (海獺)]

※ 引述《firedduck (New-life)》之銘言：
: 1.年級：高一
: 2.科目：第一章
: 3.章節：數與座標
: 4.題目：a = 1271b+2294
:         則(a,b)=(b,2294)
: 5.想法： b=1,   a=1271+2294
:                 (1271+2294,1) = (1,2294) ?
:          看起來不合理 也不是很懂為什麼
:          麻煩一下各位!  感謝

    輾轉相除法
    舉例 ()代表最大公因數
    (20,15) = ?
    |20 |15 |    (20,15) = (5,15)
    |15 |   |              ~~~ 因為20除以15餘5
    ---------
    | 5 |   |
    |   |   |


    |5  |15 |    (5,15) = (5,0) = 5
    |   |15 |                ~~因為15除以5餘0
   ----------
    |   | 0 |

    其實只是把直行的輾轉相除法變成橫向而已

   <ex> 求(311467,155683,4951)的最大公因數

   <sol> (311467,155683,4951) = (101,155683,4951) <---155683除311467餘101
                              = (101,155683,2)    <---101除4951餘2
                              = (1,155683,2)      <---2除101餘1
                              = 1

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 123.204.69.131
推 iamvanson:好像沒有解釋到原理
→ hightacps:原理參考書應該都有 要我把證明過程從參考書複製過來嗎
推 iamvanson:但他這個問題不是就是要問原理嗎
→ iamvanson:直式的輾轉相除反而是橫式的進階應用 這樣解釋好像有點
→ iamvanson:結果論