基本情報技術者 2016年秋期午前（科目A）問07

問題文

整数

x

y

(

x > y ≧ 0

)に対して、次のように定義された関数

F (x, y)

がある。

F (231, 15)

の値は幾らか。ここで、

x mod y

は

x

を

y

で割った余りである。　

F (x, y) = {x F (y, x mod y) (y = 0 のとき) (y > 0 のとき)

🖊️ 解答を隠して解いてみる

選択肢

ア：2

イ：3（正解）

ウ：5

エ：7

🔒 解説は解答すると表示されます

ユークリッドの互除法（最大公約数）【午前解説】

正解の理由

関数の定義

F (x, y) = {x F (y, x mod y) (y = 0) (y > 0)

はユークリッドの互除法そのものです。互除法は最大公約数 (gcd) を求めるアルゴリズムで、

F (x, y) = g cd (x, y)

が成り立ちます。したがって

F (231, 15) = g cd (231, 15)

を求めればよく、計算すると3になります。

計算の流れ:

231 mod 15 = 6

より

F (231, 15) = F (15, 6)

15 mod 6 = 3

より

F (15, 6) = F (6, 3)

6 mod 3 = 0

より

F (6, 3) = F (3, 0) = 3

（基底条件）
ゆえに答えは3。

解法ステップ

定義を「再帰的に余りを取ることで最大公約数を求める」互除法と認識する。
与えられた数で順に余りを計算する：まず $231 mod 15$ を求める。
得られた余りが0になるまでステップ2を繰り返す（各ステップで引数を入れ替える）。
余りが0になったときのもう一方の数が答え（gcd）である。
本問では $231 mod 15 = 6$ → $15 mod 6 = 3$ → $6 mod 3 = 0$ で終了、答えは3。

選択肢別の誤答解説

ア: 2 — 231と15の共通因子として3が存在するため2は誤り。231は奇数なので2は共通因子になり得ません。
イ: 3 — 正解。上の計算列に従うと最終的に3が最大公約数になります。
ウ: 5 — 15は5を因子に持ちますが231は5で割り切れないため共通因子ではありません。
エ: 7 — 231は7を因子に持ちますが15は7で割り切れないため最大公約数にはなりません。

よくある誤解

「x mod yを逆に計算する」： $x mod y$ と $y mod x$ を取り違えると全く別の過程になりミスします。
「ベースケースの理解不足」： $y = 0$ のときに $x$ を返す意味を誤解すると計算を止められません。
「単純な割り算ミス」：231 ÷ 15の余りを誤って3や5にしてしまうことがよくあります。

補足コラム

ユークリッドの互除法は紀元前から知られる非常に効率的なgcdアルゴリズムで、通常の整数での計算はステップ数が非常に少なく済みます。素因数分解すると

231 = 3 \times 7 \times 11

、

15 = 3 \times 5

となり共通因子は3のみであることからも答えが3であることが確認できます。拡張ユークリッドの互除法を使えば、gcdと同時に係数を求めて線形結合

a x + b y = g cd (x, y)

を得ることもできます。

FAQ

Q: Fの定義は必ず停止しますか？
A: はい。互除法では各ステップで第2引数（余り）が前回より小さくなるため、最終的に0になり停止します。

Q: 初期でy=0ならどうなりますか？
A: 定義通り

F (x, 0) = x

です。これはgcd(x,0)=xという性質に一致します。

Q: 再帰を使わずに求められますか？
A: ループ（反復）で同じ余り計算を行えば良く、実装上は再帰より反復が一般的に使いやすいです。

関連キーワード: 最大公約数、ユークリッドの互除法、再帰、gcd、余り演算、整数論、拡張ユークリッド法

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！