ユークリッドの互除法 想定問題 2

互除法の手順に A＝391，B＝161 を入れ，割り算の回数と出力される値を求める問題です。

R≠0 なら A←B，B←R として戻り，R＝0 になったら B を書き出します。出力する B は，余りが0になった割り算の「割る数」です。

• 1回目：391 ÷ 161 ＝ 2 余り 69。R≠0 なので A＝161，B＝69
• 2回目：161 ÷ 69 ＝ 2 余り 23。R≠0 なので A＝69，B＝23
• 3回目：69 ÷ 23 ＝ 3 余り 0。R＝0 なので手順4へ
• 確かめ：391 ＝ 23 × 17，161 ＝ 23 × 7。17 と 7 に共通の約数はない
• 書き出すのは B ＝ 23。割り算は3回。答えは ② 3回，23

③（69）：1回目の余りで，最後の割り算では割られる数（A）です。出力するのは B です。

⑤（0）：最後の余り R の値です。出力するのは R ではなく B です。

• 余りが 0 になったときの「割る数」が最大公約数（テキスト・覚えること）
• 流れ図では，R≠0 なら A←B，B←R としてくり返し，R＝0 になったら B を出力する（テキスト・覚えること）
• gcd を，余りが 0 になった割り算の「割られる数」や「余り（0）」と取り違えない（テキスト・ひっかけ）
• 手順をたどる問題は，A，B，R の表を作って1行ずつ書く（テキスト・解き方）