数学のブログ

最小公倍数と最大公約数 - 整数の組に共通性を探す - 互いに素、積、約数、倍数

基礎から学ぶ整数論: RSA暗号入門 (長嶋 祐二(著)、福田 一帆(著)、コロナ社)の第2章(最小公倍数と最大公約数 - 整数の組に共通性を探す -)、章末問題の問6の解答を求めてみる。

n | b

ではないと仮定すると、ある整数q 、 rが存在して、

b = n q + r ∧ 0 < r < | n |

このとき、

a b = a ( n q + r ) = a n q + a r
n | a b

なので、

n | a r

また、

( a , n ) = 1

なので、

n | r

仮定より

0 < r < | n |

なので、

r = 0

よって

b = n q

ゆえに、

n | b

となり矛盾。

よって、

∀ n , a , b ∈ ℤ [ ( n , a ) = 1 ∧ n | a b ⇒ n | b ]

である。

（証明終）