[中學] 請問輾轉相除法的證明

[MaInNine (anonymous)]

我有點看不懂課本的寫法

a=bq+r

有人能幫我解說

(a,b)=(b,r)

的推導過程嗎

感謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.230.38.218
推 JohnMash    :互相被對方整除
要怎麼證明呢!!
※ 編輯: MaInNine        來自: 125.230.38.218       (05/28 20:31)
推 suhorng     :假設 (a,b) = d_1, (b,r) = d_2
→ suhorng     :那麼 d_1|b, d_1|r (因為 r = a - bq)
→ suhorng     :因此 d_1|d_2
→ suhorng     :又   d_2|b, d_2|a (因為 a = bq + r)
→ suhorng     :所以 d_2|d_1 => d_1 = d_2
= =.....
※ 編輯: MaInNine        來自: 125.230.38.218       (05/28 22:34)
→ sostwe      :http://ppt.cc/hFf2 這個影片剛好有證明這個公式
→ sostwe      :可以直接跳到10幾分開始看
推 rehearttw   :這應該就是課本寫法吧！原 PO 把課本的列出來
→ rehearttw   :並說說哪個地方不懂，大家來幫忙解釋
→ MaInNine    :我看懂了謝謝!
→ sneak       : 又   d_2|b,  https://noxiv.com
→ sneak       : 我看懂了謝謝! https://daxiv.com