代数学入門小テスト

代数学入門小テスト 4
2016 年度後期
工学部・未来科学部 1 年
担当: 原隆 (未来科学部数学系列・助教)
注. どこに解答が書かれているのかがはっきりと分かるようにすること。必要ならば裏も使って良いが、
その旨を明記すること。解答が判別出来ない場合は得点がつかない可能性もあるので気をつけよう。
※ If you are not good at writing Japanese sentences, you can answer the following problems in English.
問題 4-1. 以下の空欄に当て嵌まる人名を答えなさい。
『一次不定方程式 ax + by = d
[2 点]
· · · (∗) に於いて g.c.d.(a, b) | d が成り
立つならば、(∗) は整数解を持つ。この事実は
の補題
と呼ばれている。』
問題 4-2. 一次不定方程式
35x − 49y = 21
· · · (⋆)
について、以下の設問に答えなさい。
(1) 方程式 (⋆) の特殊解 (x0 , y0 ) をユークリッドの互除法を用いて求めなさい。ユークリッドの
互除法を用いていない答案は減点対象とする。
(2) 方程式 (⋆) のすべての整数解を求めなさい。
問題 4-3. 整数 102245 を素因数分解しなさい。
[3 点]
[2 点]
[ボーナス問題; 2 点]
【解答】
問題 4-1. ベズー (Bezout)
※ ユークリッドの補題はまったく別の補題なので不可。きちんと整理して記憶しよう!!
問題 4-2.
(1) 式 (⋆) の左辺の係数組 (35, 49) にユークリッドの互除法を用いて
49 = 35 · 1 + 14
35 = 14 · 2 + 7
(14 = 7 · 2 + 0)
より、これを逆向きに遡ると
7 = 35 − 14 · 2 = 35 − (49 − 35 · 1) · 2 = 35 · 3 − 49 · 2
が得られる。したがって辺々 3 倍して整理すると
35 · 9 − 49 · 6 = 21
となるため、 (x0 , y0 ) = (9, 6) は (⋆) の特殊解となる。
(2)
−)
35
x
− 49
y
= 21
35 ·
9
− 49 ·
6
= 21
35 ( x − 9 ) − 49 ( y − 6 ) = 0
より、
5
7
> − 9) = > − 6)
35(x
49(y
∴
5(x − 9) = 7(y − 6)
が成り立つ。5 と 7 は互いに素であるから、x − 9 は 7 の倍数、、y − 6 は 5 の倍数となる。
したがって x − 9 = 7k (k は整数) とおくと、x = 9 + 7k であり、一方で
7(y − 6) = 5(x − 9) = 5 · 7k
∴
y = 6 + 5k
となる。以上より (⋆) のすべての整数解は (x, y) = (9 + 7k, 6 + 5k) (k は整数) となる。
問題 4-3. 102245 = 5 × 112 × 132
※ このように素因数の大きい整数の素因数分解はかなり大変であり、しかもどこで終了すれ
ば良いのかも判断しずらい (例えば 102245 = 5 × 20449 と分解したあと 20449 が素数かどうかを
判定するのは結構骨が折れるでしょう?)。この素因数分解の困難さを暗号理論に応用したものが、
本講義の終盤で扱う RSA 公開鍵暗号である。

Download Report