| ■34710 / inTopicNo.2) |
Re[1]: Euclidの互除法
|
□投稿者/ WIZ 軍団(129回)-(2008/07/28(Mon) 08:54:09)
 | タイトルにある通りユークリッドの互除法を使うだけです。
87654321 = 12345678*7+1234575 ⇒ (12345678,87654321) = (12345678,1234575)
12345678 = 1234575*9+1234503 ⇒ (12345678,1234575) = (1234575,1234503)
1234575 = 1234503*1+72 ⇒ (1234575,1234503) = (1234503,72)
1234503 = 72*17145+63 ⇒ (1234503,72) = (72,63) = (9,63) = 9
|
|
