ユークリッド の 互除法じょほう一いち問もん一いち答とう

この一問一答で出る問題

全20問。答えと解説は「スタート」を押すと1問ずつ表示されます。

1. 整数の割り算定理せいすうのわりざんていり $a = bq + r$ で、 余よ り $r$ が満みたす条件じょうけんはどれですか？ ($b > 0$)
   • ・$0 \le r \le b$
   • ・$0 < r < b$
   • ・$1 \le r \le b$
   • ・$0 \le r < b$
2. 23 を 5 で割わったときの商しょうと余あまりはいくらですか？
   • ・商 4, 余 り 3
   • ・商 3, 余 り 8
   • ・商 5, 余 り -2
   • ・商 4, 余 り 5
3. ユークリッドの互除法ゆーくりっどのごじょほう の中心ちゅうしんとなる性質せいしつはどれですか？ ($a = bq + r$)
   • ・$\gcd(a, b) = \gcd(b, r)$
   • ・$\gcd(a, b) = \gcd(a, q)$
   • ・$\gcd(a, b) = \gcd(q, r)$
   • ・$\gcd(a, b) = q \cdot r$
4. 互除法じょほうで gcd を求もとめるとき、 計算けいさんはいつ終了しゅうりょうしますか？
   • ・商 が 1 に な っ た と き
   • ・商 が 0 に な っ た と き
   • ・余 り が 1 に な っ た と き
   • ・余 り が 0 に な っ た と き、 そ の 直 前 の 余 り (= 割 る 方) が gcd
5. 互除法じょほうで $\gcd(252, 198)$ を求もとめるといくらになりますか？
   • ・18
   • ・6
   • ・9
   • ・36
6. $\gcd(1071, 1029)$ はいくらですか？
   • ・3
   • ・7
   • ・42
   • ・21
7. $\gcd(2730, 663)$ はいくらですか？
   • ・13
   • ・39
   • ・21
   • ・51
8. $\gcd(7, 11)$ はいくらですか？
   • ・0
   • ・7
   • ・77
   • ・1
9. $\gcd(a, b) = 1$ と な る 2 数かずを何なんと呼よびますか？
   • ・素数そすう
   • ・合成数ごうせいすう
   • ・互いに素たがいにそ
   • ・完全数かんぜんすう
10. 互除法じょほうの計算けいさん量りょう (ステップ数すう) はおおむねどのくらいですか？
    • ・$\log a$ に 比 例 (各 ス テ ッ プ で 数 が ほ ぼ 半 分 以 下 に な る)
    • ・$a$ に 比 例
    • ・$\sqrt{a}$ に 比 例
    • ・常 に 一 定 で 10 回 以 下
11. ベズーの等式べずーのとうしき として正ただしいものはどれですか？
    • ・任 意 の 整 数 $a, b$ (両 方 0 で な い) に 対 し、 $ax + by = \gcd(a, b)$ を 満 た す 整 数 $x, y$ が 存 在 す る
    • ・$ax + by = 1$ は 常 に 解 を 持 つ
    • ・$\gcd(a, b) = a + b$
    • ・$\gcd(a, b)$ は 一 意 で は な い
12. 拡張ユークリッド互除法かくちょうゆーくりっどごじょほう を用もちいて $17x + 12y = 1$ の整数せいすう解かいとして正ただしいものはどれですか？
    • ・$(x, y) = (3, -4)$
    • ・$(x, y) = (7, -5)$
    • ・$(x, y) = (2, -3)$
    • ・$(x, y) = (5, -7)$
13. 拡張かくちょう互除法じょほうで $252x + 198y = 18$ を解とくと、 1 つの整数せいすう解かいはどれですか？
    • ・$(x, y) = (1, -1)$
    • ・$(x, y) = (4, -5)$
    • ・$(x, y) = (3, -2)$
    • ・$(x, y) = (2, -3)$
14. $\gcd(a, b)$ を素因数そいんすう分解ぶんかいで求もとめるとき、 各かく素因数そいんすうの指数しすうはどう取とりますか？
    • ・最 小 値 $\min(a_i, b_i)$
    • ・和 $(a_i + b_i)$
    • ・差 $(a_i - b_i)$
    • ・最 大 値 $\max(a_i, b_i)$
15. $\gcd(252, 198) = 18$ である。 これより $\mathrm{lcm}(252, 198)$ はいくらですか？
    • ・2772
    • ・450
    • ・2520
    • ・4536
16. 次つぎのうち、 $ax + by = c$ が整数せいすう解かいを 持もつ ための必要十分条件ひつようじゅうぶんじょうけんはどれですか？
    • ・$\gcd(a, b) \mid c$
    • ・$\gcd(a, b) > c$
    • ・$c$ が 偶 数
    • ・$a, b$ が 互 い に 素
17. 互除法じょほうが古代こだいから知しられていることを著あらわした古典こてんとして知しられるのは誰だれの著作ちょさくですか？
    • ・ピ タ ゴ ラ ス
    • ・ユ ー ク リ ッ ド (原 論)
    • ・ア ル キ メ デ ス
    • ・ガ ウ ス
18. $\gcd(360, 84)$ を互除法じょほうで求もとめるといくらですか？
    • ・6
    • ・18
    • ・24
    • ・12
19. $13x + 8y = 1$ の整数せいすう解かいとして正ただしいものはどれですか？
    • ・$(x, y) = (-3, 5)$
    • ・$(x, y) = (1, -1)$
    • ・$(x, y) = (5, -8)$
    • ・$(x, y) = (3, -4)$
20. 互除法じょほうの重要じゅうような応用おうようとして適切てきせつでないものはどれですか？
    • ・大 き な 数 の gcd を 速 く 求 め る
    • ・一 次 不 定 方 程 式 の 解 を 求 め る
    • ・暗 号 (RSA) で の 計算
    • ・実 数 解 の 微 分 を 求 め る