[数A]互いに素とは？互いに素である2つの証明方法

2つの整数が互いに素である。

このようなことを聞いたことはありませんか？

「互いに素」、きっと2つの整数の関係性を示す言葉だろうと想像できた人もいるでしょう。

これから、「互いに素」とはどのような関係のことなのか詳しく解説します。

また互いに素であることを2つの方法で証明するので、最後までご覧ください。

互いに素とは？

互いに素とは、2つの整数a、bの最大公約数が1であることです。

たとえば、7と8の場合を考えてみましょう。

7の約数は1、7で、8の約数は1、2、4、8ですね。

よって、最大公約数は1です。

したがって、7と8は互いに素であるとわかります。

では6と9はどうでしょうか。

6の約数は1、2、3、6であり、9の約数は1、3、9です。

よって、最大公約数は3になるので、6と9は互いに素ではありません。

以上のように、互いに素であるか調べるときは2つの数の最大公約数を調べましょう。

また、互いで素である条件を「共通の約数が1のみである」や「公約数が1のみ」というときもあります。

どの表現の仕方も同じ意味なので、覚えておくとよいでしょう。

互いに素である証明 (最大公約数が1)

それでは2つの整数が互いに素であることを証明してみましょう。

$a$を自然数とし、$a$と$a+1$が互いに素であることを証明します。

$a$と$a+1$の最大公約数を$g$とすると、$a=mg$、$a+1=ng$（$m$、$n$は互いに素な自然数）と表されます。

$a=mg$を$a+1=ng$に代入すると、

\[mg+1=ng\]

\[ng-mg=1\]

\[(n-m)g=1\]

$n$、$m$、$g$は自然数なので、この等式を満たすのは、$n-m=1$、$g=1$のときのみです。

よって、$a$と$a+1$の最大公約数は1なので、$a$と$a+1$は互いに素であることが証明されました。

同様に考えると、$a$と$a+1$が負の整数でも成り立つので、0を含まない連続する2つの整数は互いに素であることがわかります。

このように最大公約数が1であることを証明することで、2つの整数が互いに素であることが証明可能です。

今回は2つの連続する数を用いて互いに素である証明をしましたが、連続していない2つの整数も互いに素である場合があります。

その点には注意しましょう。

互いに素である証明(背理法)

2つの整数$a$と$a+1$が互いに素であることを背理法を用いて証明しましょう。

まず、仮定として$a$と$a+1$が互いに素でないと仮定します。つまり、$a$と$a+1$の最大公約数を$d$とし、$d\geq 2$と仮定します。

このとき、$a$と$a+1$は$d$で割り切れると考えられます。つまり、$a=md$、$a+1=nd$（ここで$m$と$n$は整数）と表すことができます。

ここで、$a+1-a=nd-md$を考えます。

$a+1-a=1$であり、$nd-md=d(n-m)=1$です。このとき、$n-m$は整数であり、したがって$d$は1に等しいか-1に等しい必要があります。

しかし、仮定では$d\geq 2$と仮定しており、$d$が1であることと$d\geq 2$の仮定は矛盾します。

したがって、仮定が誤っており、$a$と$a+1$は互いに素であることが証明されました。

以上のように、背理法を用いて、2つの整数$a$と$a+1$が互いに素であることを証明しました。

互いに素とは？のまとめ

互いに素について解説しました。

ポイントは下記の3つです。

• 互いに素とは、2つの整数a、bの最大公約数が1であることです。
• 互いに素であることは背理法を用いて証明することもできます。
• 連続する2つの整数は互いに素です。

互いに素であることの証明は、最大公約数が1であることを証明する方法と、背理法を用いる2つの方法があります。

どちらの方法も使えるようにしておくと、さまざまな問題に対応できるのでおすすめです。