こんにちは、ウチダです。
さて、皆さんは「互いに素」という言葉の意味をしっかり理解できましたか？
$2$ つの自然数 $a$，$b$ に共通な素因数が存在しないとき、$a$，$b$ は互いに素であるという。
たとえば歯車を作る際、それぞれの歯の数が互いに素になるように設計することで、全体が均一に摩耗し、歯当たりが滑らかになります。
[ふきだし set=”悩む男性”]へ～。工業製品にも応用されている概念なんだね～。[/ふきだし]
[ふきだし set=”悩む女性”]互いに素は重要って聞くけど、実際どのように応用すればいいんですか？[/ふきだし]
よって本記事では、互いに素のもう一つの意味から、互いに素の応用例 $7$ 選まで
- 東北大学理学部数学科卒業
- 教員採用試験に１発合格 → 高校教諭経験アリ
の僕がわかりやすく解説します。
互いに素な自然数とは？【「最大公約数が１」という意味です】
「互いに素」であるとは、共通な素因数を持たないことと定義しました。
これを、今までで習った言葉に置き換えると…
と表すこともできます。
式にすると $GCD( \ a \ , \ b \ )=1$ ですね。
[ふきだし set=”ウチダ”]数式として扱えるため、こちらの定義の方が便利です。最大公約数については「最大公約数と最小公倍数の求め方とは？【ヒント：素因数分解】」の記事で詳しく解説しております。[/ふきだし]
それでは、互いに素であるかどうか見極める練習問題を、何問か解いてみましょう。
互いに素を見極める練習
(1) $15$ と $28$
(2) $39$ と $52$
(3) $143$ と $187$
(3)の数が大きいので、少し難しいです。
【解答】
(1) $15=3・5$，$28=2^2・7$ より、共通する素因数がない。
したがって、互いに素である。
(2) $39=3・13$，$52=2^2・13$ より、$GCD( \ 39 \ , \ 52 \ )=13$ である。
したがって、互いに素ではない。
(3) $1-4+3=0$，$1-8+7=0$ より、どちらとも $11$ の倍数である。
したがって、互いに素ではない。
(解答終了)
(3)は、各桁を交互に足し引きしたものが $0$ であることを利用し、$11$ の倍数であることを見破りましょう。
[ふきだし set=”ウチダ”]その他の倍数判定法についても「【倍数判定法まとめ】３の倍数・４の倍数・７の倍数などの見分け方とは？」の記事で詳しく解説してます！[/ふきだし]
互いに素な自然数の応用問題（応用例）７選
さて、互いに素の定義や意味については、大体理解できたと思います。
ここからは互いに素の主な応用例について見ていきましょう。
具体的には
- 互いに素な自然数の性質（連続する整数の性質）
- 互いに素な自然数の個数（オイラー関数）
- 互いに素と同値な条件（不定方程式の整数解）
- その他の応用例 $4$ 選
- フェルマーの小定理（合同式の性質）
- 完全数（約数関数の性質）
- 原始ピタゴラス数の公式
- 互いに素である確率（バーゼル問題）
の計 $7$ つです。
[ふきだし set=”ウチダ”]互いに素は応用例が非常に豊富です。知らないのはもったいないですが、全部知るのも大変なので、興味のある所だけでもじっくり読んでほしいと思います＾＾[/ふきだし]
互いに素な自然数の性質（連続する整数の性質）
さあ、まずは「連続する整数の性質」を証明していきましょうか。
互いに素を示す方針は
- 最大公約数を $G$ とおく。
- $G=1$ であることを導く。
基本は、ほぼほぼこれです。
【証明】
$n$ と $n+1$ の最大公約数を $G$ とすると、ある自然数 $a$，$b$ を用いて、
$$\left\{\begin{array}{ll}n=Ga &…①\\n+1=Gb &…②\end{array}\right.$$
と表すことができる。（ $n<n+1$ より $a<b$ ）
ここで、② $-$ ①を計算すると、$(左辺)=(n+1)-n=1$，$(右辺)=Gb-Ga=G(b-a)$ より、
$$1=G(b-a)$$
よって、$G$ も $b-a$ も整数であるため、$G=b-a=1$ が成り立つ。
(証明終了)
こんな感じで色んな性質を示すことができます。
結果だけを記すと…
- 連続する $2$ つの自然数は互いに素である。
- 「 $a$ と $b$ が互いに素である」ことと「 $a+b$ と $b$ が互いに素である」ことは同値である。
- 「 $a$ と $b$ が互いに素である」ことと「 $a+b$ と $ab$ が互いに素である」ことも同値である。
[ふきだし set=”ウチダ”]ちなみに「互いに素でない」と仮定すると、ある素数 $p$ を公約数に持つことが言えるため、そこから矛盾を示す方針でも証明ができます。（背理法の原理）[/ふきだし]
背理法については「背理法とは～（準備中）」の記事で詳しく解説してますので、ここではスルーします。
互いに素な自然数の個数（オイラー関数）
(1) $f(15)$ を求めなさい。
(2) $f(16)$ を求めなさい。
(3) $f(pq)$，$f(p^k)$ がどう表せるか予想せよ（ $p$，$q$ は異なる素数であり、$k$ はある自然数）。
(1)(2)はただ数えるしかありません。
その結果をもとに、(3)を予想するところまでやってみましょう。
【解答】
(1) $15$ までの自然数のうち、互いに素でない自然数を数え上げる。
ここで、$15=3・5$ より、$3$ の倍数または $5$ の倍数を数えればいいので、
$$15÷3+15÷5-1=7 \ (個)$$
したがって、$f(15)=15-7=8$ である。
(2) 同様に、$16$ までの自然数のうち、互いに素でない自然数を数え上げる。
ここで、$16=2^4$ より、$2$ の倍数を数えればいいので、
$$16÷2=8 \ (個)$$
したがって、$f(16)=16-8=8$ である。
(3) これまでの話の一般化である。
つまり、
と予想できる。
(解答終了)
ちなみに、この $f(n)$ は「オイラー関数」と呼ばれ、整数の分野において広く応用されています。
[ふきだし set=”ウチダ”](3)の予想に対する証明やオイラー関数の応用例については、「オイラー関数とは？【公式の証明や応用例２選をわかりやすく解説します】」の記事で詳しく解説しております。[/ふきだし]
互いに素と同値な条件（不定方程式の整数解）
$ax+by=1$ のように、解が有限個に定まらない方程式のことを「不定方程式」といいます。
ここでは、予想といくつかの例を挙げるところまで考察してみましょう。
【解答】
$a$ と $b$ が互いに素であれば、不定方程式 $ax+by=1$ は必ず整数解を持つと予想できる。
ここでは、例を $3$ つほど挙げておこう。
① $a=3 \ , \ b=4$ のとき
$x=-1 \ , \ y=1$ とすれば、$3・(-1)+4・1=1$ より成り立つ。
② $a=5 \ , \ b=7$ のとき
$x=3 \ , \ y=-2$ とすれば、$5・3+7・(-2)=1$ より成り立つ。
③ $a=25 \ , \ b=28$ のとき
$x=9 \ , \ y=-8$ とすれば、$25・9+28・(-8)=1$ より成り立つ。
(解答終了)
実は、
- $a$ と $b$ が互いに素である
- 不定方程式 $ax+by=1$ が整数解を持つ
この $2$ つは同値な条件として知られており、さらに一般的に以下が成り立ちます。
$a$ と $b$ の最大公約数を $GCD( \ a \ , \ b \ )$ と表す。
このとき、$ax+by=GCD( \ a \ , \ b \ )$ を満たす整数 $x$，$y$ が必ず存在する。
互いに素であるときは $GCD( \ a \ , \ b \ )=1$ であり、今回の問題に帰着するわけですね。
[ふきだし set=”ウチダ”]実はここら辺の話が不定方程式を解く上での原理になってきます。詳しくは「一次不定方程式の解き方とは？【応用問題３選もわかりやすく解説します】」の記事で解説してますので、よろしければあわせてご覧ください。[/ふきだし]
その他の応用例（フェルマーの小定理・完全数・ピタゴラス数・バーゼル問題）
さて、ここからはかなり発展的な内容になります。
ですので、理解できなくても落ち込む必要はありません。
再度お伝えしておくと、
- フェルマーの小定理（合同式の性質）
- 完全数（約数関数の性質）
- 原始ピタゴラス数の公式
- 互いに素である確率（バーゼル問題）
を簡単に解説していきます。
[ふきだし set=”ウチダ”]どれも面白い話ばかりですので、ぜひ概要だけでも掴んで友達に自慢しちゃいましょう！[/ふきだし]
フェルマーの小定理（合同式の性質）
$p$ を素数とし、$a$ を $p$ と互いに素な自然数とする。
このとき、$$a^{p-1}≡1 \pmod{p} …①$$
つまり、$a^{p-1}$ を $p$ で割った余りは $1$ となる。
もしくは、$$a^p≡a \pmod{p} …②$$
つまり、$a^p$ を $p$ で割った余りは $a$ とも言える。
①を「第 $1$ 形式」、②を「第 $2$ 形式」と呼ぶこともあります。
さて、「この定理がなぜ成り立つのか」気になりますよね！
それには、合同式の除法の性質が深く関係しているのです。
法を $p$ とする。
このとき、$ab≡ac$ で、a と p が互いに素であるとき、$b≡c$
つまり合同方程式においては、互いに素でなければ両辺を同じ数で割ってはいけない、ということになります。
[ふきだし set=”ウチダ”]フェルマーの小定理は、現代のネット社会を支えている「RSA暗号」にも応用される、極めて重要な定理です。[/ふきだし]
参考記事はこちらから
- 合同式の除法の性質 → 合同式（mod）を応用して京大入試問題を解こう【不定方程式の問題も解説】
- フェルマーの小定理 → フェルマーの小定理の２通りの証明とは？【京大入試を含む問題３選も解説】
完全数（約数関数の性質）
完全数の記事において、$n$ の正の約数の総和を表す「約数関数 $S(n)$ 」なるものを定めました。
$n$ と $m$ が互いに素であるとき、$$S(nm)=S(n)S(m)$$が成り立つ。（約数関数の乗法性）
この性質を使って、完全数の公式を証明しました。
[ふきだし set=”ウチダ”]オイラー関数は「約数でないものの個数」、約数関数は「約数の総和」と定義しました。非常に似てますね。また、どちらも乗法性が成り立ちます。[/ふきだし]
完全数については「完全数（496や8128）とは？一覧とその求め方【公式の証明もわかりやすく解説】」の記事で解説してますので、興味のある方はぜひご覧ください。
原始ピタゴラス数の公式
ピタゴラス数とは、$( \ 6 \ , \ 8 \ , \ 10 \ )$ のように、ピタゴラスの定理
$$a^2+b^2=c^2$$
の関係が成り立つ自然数 $3$ つの組のことで、原始ピタゴラス数は特に互いに素である組のことです。
たとえば $( \ 3 \ , \ 4 \ , \ 5 \ )$ や $( \ 5 \ , \ 12 \ , \ 13 \ )$ などがあり、原始ピタゴラス数は無限に存在することが知られています。
$m$、$n$ を自然数とする。
このとき、$$a=m^2-n^2 , b=2mn , c=m^2+n^2$$とすると、$(a,b,c)$ はピタゴラス数になる。
ここでも互いに素は大活躍してますね！
[ふきだし set=”ウチダ”]ピタゴラス数を自分で見つける作業は非常に楽しいです！これも興味のある方は「ピタゴラス数が一発でわかる公式【証明もあわせて解説】」の記事を読んでいただきたいと思います。[/ふきだし]
互いに素である確率（バーゼル問題）
さて、最後は「適当に選んだ $2$ つの自然数が互いに素である確率」です。
これ、大体何パーセントぐらいだと思いますか？
予想してみてください。
↓↓↓（正解発表）
正解は、なんと…約 $60$ % でした～！
結構高いですよね。
この証明の概要を、わかりやすく簡潔に書くとこうなります。
【証明の概要】
選んだ整数 $a$，$b$ が互いに素ならば、必ずどちらかは $2$ の倍数ではない。
これは、「どちらとも $2$ の倍数である」という事象の余事象の確率であるため、
$$1-(\frac{1}{2})^2=1-\frac{1}{2^2}$$
と求めることができる。
≫参考記事：余事象の確率とは？【〇〇の問題で絶大な威力を発揮します】
同様に、必ずどちらかは $3$ の倍数でない確率は
$$1-(\frac{1}{3})^2=1-\frac{1}{3^2}$$
これを素数全てに対して行って、すべての積を取ると、
※ $ζ(s)$ はリーマンのゼータ関数と呼ばれ、$ζ(2)$ を求めることは「バーゼル問題」と言われています。
(概要終了)
このように、最終的に「バーゼル問題」を解くことに帰着します。
[ふきだし set=”ウチダ”]大学数学の知識が必要ですが、高校生が読んでも面白い内容です。詳しくは「バーゼル問題～（準備中）」をお読みください。[/ふきだし]
互いに素な自然数に関するまとめ
内容が盛りだくさんでしたね(^_^;)
最後に、本記事の要点をまとめたいと思います。
互いに素な自然数は、整数問題の至る所に登場します。
全てを理解する必要はないので、興味が出るところから勉強してみましょう＾＾
「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!
終わりです。
コメントを残す
コメント一覧 （1件）
実数直線上の自然数の本性（パラダイムシフト）は、3冊の絵本で・・・
絵本「哲学してみる」
絵本「わのくにのひふみよ」
絵本「もろはのつるぎ」
数の言葉ヒフミヨ（1234）は、＋ ー × ÷ √ ＝ をモトモト持ち合わせている。