基礎知識

【整数】互いに素とは

ここでは整数論でたびたび用いられる「互いに素」について解説していきたいと思います。

互いに素とは

二つの整数 a, b の最大公約数が1のとき、 ab互いに素であるといいます。

互いに素な整数の例

二つの整数の最大公約数が1かどうかが互いに素であるかどうかになりますので、

  • (1, 2)
  • (2, 3)
  • (2, 5)
  • (4, 9)

などは互いに素な整数となります。

マスマスターの思考回路

互いに素の「素」は素数の「素」ですが、互いに素な整数の組としてそれらが素数である必要性はありません。

上の例では1や4といった素数でない数が含まれていますが、数字の組としては互いに素となる場合があります。

また、互いに素の定義から、1と全ての整数は互いに素となります。

互いに素であることを用いた証明の例題

一つ例題を扱ってみましょう。

例題

2つの自然数 n, n+1 が互いに素であることを示せ

解答例

マスマスターの思考回路

2つの自然数の最大公約数が1であることを証明すれば良いでしょう。

nn+1 の最大公約数を G とすると、互いに素な自然数 a, b を用いて、

    \begin{eqnarray*} n &=& aG \\\\ n+1 &=& bG \\\\ \end{eqnarray*}

と表すことができ、上式より、

    \begin{eqnarray*} aG+1 &=& bG \\\\ G(b-a) &=& 1 \\\\ \end{eqnarray*}

ここで、 Gb-a は自然数なので上式をみたすには、

    \begin{eqnarray*} G &=& 1 \\\\ b-a &=& 1 \\\\ \end{eqnarray*}

でなければなりません。

G = 1 より、nn+1 の最大公約数は 1 となるので、nn+1 が互いに素であることが証明されました。

互いに素の説明の終わりに

いかがでしたか?

互いに素の説明だけではそれ自体が何の役にたつかがわかりませんが、互いに素という考え方がなければ既約分数を文字式で表すことができませんし、ユークリッドの互除法や不定方程式への応用など、様々な場面で互いに素という考え方が重要になります。

整数問題はシンプルに見えますが、非常に奥深く難しい分野ですので、様々な問題に触れながら解決方法を身につけていきましょう。

【基礎】整数の性質のまとめ

関連記事

教科別目次

プロフィール

-このサイトの記事を書いている人-

某国立大工学部卒のwebエンジニアです。
学生時代に塾講師として勤務していた際、生徒さんから「解説を聞けば理解できるけど、なぜその解き方を思いつくのかがわからない」という声を多くいただきました。
授業という限られた時間の中ではこの声に応えることは難しく、ある程度の理解度までに留めつつ、繰り返しの復習で覚えてもらうという方法を採らざるを得ないこともありました。
本ブログでは「数学の問題を解くための思考回路」に重点を置いています。
それらを通じて自らの力で問題を解決する力が身につくお手伝いができれば幸いです。

お問い合わせ

ピックアップ

検索

カテゴリー

タグ

新着記事