数学のブログ

整数の基礎的知識 - RSA暗号の導入 - 倍数と約数

基礎から学ぶ整数論: RSA暗号入門 (長嶋 祐二(著)、福田 一帆(著)、コロナ社)の第1章(整数の基礎的知識 - RSA暗号の導入 -)、章末問題の問1の解答を求めてみる。

1

6 = 3 · 2

2

2 = 8 · 0 + 2

3

11 = 5 · 2 + 1

4

任意の

a , b , r ∈ ℕ k 1 , k 2 ∈ ℤ

に対して、

r | a ∧ r | b

ならば、ある整数

c 1 , c 2 ∈ ℤ

が存在して

a = c 1 r b = c 2 r

よって、

k 1 a - k 2 b = k 1 c 1 r - k 2 c 2 r = ( k 1 c 1 - k 2 c 2 ) r

ゆえに、

r | ( k 1 a - k 2 b )

5

任意の

a , b , r ∈ ℕ k 1 , k 2 ∈ ℤ

に対して、

r | a ∧ 2 r | b

ならば、 ある整数

c 1 , c 2 ∈ ℤ

が存在して、

a = c 1 r b = c 2 2 r = 2 c 2 r

が成り立ち、

k 1 a + k 2 b = k 1 c 1 r + 2 k 2 c 2 r = ( k 1 c 1 + 2 k 2 c 2 ) r

ここで

k 1 c 1 + 2 k 2 c 2

が奇数となる場合、例えば

a = 1 b = 2 k 1 = 1 k 2 = 1 r = 1

の場合を考えると、

c 1 = c 2 = 1 k 1 c 1 + 2 k 2 c 2 = 3

となり、

r | a ∧ 2 r | b

が成り立つが、

k 1 a + k 2 b = 3

は

2 r = 2

では割り切れない。

よって、成立する番号は1と4。