数学のブログ

整数約数と倍数ユークリッド互除法、互いに素ではないための十分条件

親切な代数学演習新装2版―整数・群・環・体
 楽天ブックス
Yahoo!ショッピング
au PAY マーケット

学習環境

親切な代数学演習新装2版―整数・群・環・体 (加藤明史(著)、現代数学社)の第Ⅰ部(整数)、第1章(約数と倍数)の問29の解答を求めてみる。

ユークリッド互除法により、

\begin{array}{l} 8 l + 7 = (5 l + 6) \cdot 1 + (3 l + 1) \\ 5 l + 6 = (3 l + 1) \cdot 1 + (2 l + 5) \\ 3 l + 1 = (2 l + 5) \cdot 1 + (l - 4) \\ 2 l + 5 = (l - 4) \cdot 2 + 13 \end{array}

よって、

(8 l + 7, 5 l + 1) = (l - 4, 13)

ゆえに互いに素ではないためには、

\begin{array}{l} n \in ℤ \\ l - 4 = 13 n \\ l = 13 n + 4 \end{array}