互いに素な自然数とは?【応用例7選もわかりやすく解説します】

2019 12/14
互いに素な自然数とは?【応用例7選もわかりやすく解説します】

こんにちは、ウチダショウマです。

さて、皆さんは「互いに素」という言葉の意味をしっかり理解できましたか?

【互いに素な自然数の定義】
$2$ つの自然数 $a$,$b$ に共通な素因数が存在しないとき、$a$,$b$ は互いに素であるという。

たとえば歯車を作る際、それぞれの歯の数が互いに素になるように設計することで、全体が均一に摩耗し、歯当たりが滑らかになります。

悩む男性 悩む男性
へ~。工業製品にも応用されている概念なんだね~。
悩む女性 悩む女性
互いに素は重要って聞くけど、実際どのように応用すればいいんですか?

よって本記事では、互いに素のもう一つの意味から、互いに素の応用例 $7$ 選まで

  • 東北大学理学部数学科卒業
  • 教員採用試験に1発合格 → 高校教諭経験アリ

の僕がわかりやすく解説します。

スポンサーリンク
目次

互いに素な自然数とは?【「最大公約数が1」という意味です】

「互いに素」であるとは、共通な素因数を持たないことと定義しました。

これを、今までで習った言葉に置き換えると…

最大公約数が $1$ である

と表すこともできます。

式にすると $GCD( \ a \ , \ b \ )=1$ ですね。

ウチダ ウチダ
数式として扱えるため、こちらの定義の方が便利です。最大公約数については「最大公約数と最小公倍数の求め方とは?【ヒント:素因数分解】」の記事で詳しく解説しております。

それでは、互いに素であるかどうか見極める練習問題を、何問か解いてみましょう。

互いに素を見極める練習

問題. 次の $2$ つの自然数について、互いに素であるか否かを答えなさい。
(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$ の倍数であることを見破りましょう。

ウチダ ウチダ
その他の倍数判定法についても「【倍数判定法まとめ】3の倍数・4の倍数・7の倍数などの見分け方とは?」の記事で詳しく解説してます!

互いに素な自然数の応用問題(応用例)7選

さて、互いに素の定義や意味については、大体理解できたと思います。

ここからは互いに素の主な応用例について見ていきましょう。

具体的には

  • 互いに素な自然数の性質(連続する整数の性質)
  • 互いに素な自然数の個数(オイラー関数)
  • 互いに素と同値な条件(不定方程式の整数解)
  • その他の応用例 $4$ 選
    • フェルマーの小定理(合同式の性質)
    • 完全数(約数関数の性質)
    • 原始ピタゴラス数の公式
    • 互いに素である確率(バーゼル問題)

の計 $7$ つです。

ウチダ ウチダ
互いに素は応用例が非常に豊富です。知らないのはもったいないですが、全部知るのも大変なので、興味のある所だけでもじっくり読んでほしいと思います^^

互いに素な自然数の性質(連続する整数の性質)

問題. 連続する $2$ つの自然数 $n$,$n+1$ は互いに素であることを示しなさい。

さあ、まずは「連続する整数の性質」を証明していきましょうか。

互いに素を示す方針は

  1. 最大公約数を $G$ とおく。
  2. $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$ が互いに素である」ことも同値である。
ウチダ ウチダ
ちなみに「互いに素でない」と仮定すると、ある素数 $p$ を公約数に持つことが言えるため、そこから矛盾を示す方針でも証明ができます。(背理法の原理)

背理法については「背理法とは~(準備中)」の記事で詳しく解説してますので、ここではスルーします。

互いに素な自然数の個数(オイラー関数)

問題. $n$ を自然数として、$f(n)$ を「 $m≦n$ で $n$ と互いに素であるような自然数 $m$ の個数」と定義する。このとき、次の問いに答えよ。
(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$ である。

15と互いに素な自然数の個数(オイラー関数)

(2) 同様に、$16$ までの自然数のうち、互いに素でない自然数を数え上げる。

ここで、$16=2^4$ より、$2$ の倍数を数えればいいので、

$$16÷2=8 \ (個)$$

したがって、$f(16)=16-8=8$ である。

(3) これまでの話の一般化である。

つまり、

\begin{align}f(pq)&=pq-(p+q-1)\\&=(p-1)(q-1)\\&=pq(1-\frac{1}{p})(1-\frac{1}{q})\end{align}

\begin{align}f(p^k)&=p^k-p^k÷p\\&=p^k-p^{k-1}\\&=p^k(1-\frac{1}{p})\end{align}

と予想できる。

(解答終了)

ちなみに、この $f(n)$ は「オイラー関数」と呼ばれ、整数の分野において広く応用されています。

ウチダ ウチダ
(3)の予想に対する証明やオイラー関数の応用例については、「オイラー関数とは?【公式の証明や応用例2選をわかりやすく解説します】」の記事で詳しく解説しております。

互いに素と同値な条件(不定方程式の整数解)

問題. $a$ と $b$ が互いに素であるとき、不定方程式 $ax+by=1$ が整数解を持たないことがあるかどうか、予想しなさい。

$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$ であり、今回の問題に帰着するわけですね。

ウチダ ウチダ
実はここら辺の話が不定方程式を解く上での原理になってきます。詳しくは「一次不定方程式の解き方とは?【応用問題3選もわかりやすく解説します】」の記事で解説してますので、よろしければあわせてご覧ください。
スポンサーリンク

その他の応用例(フェルマーの小定理・完全数・ピタゴラス数・バーゼル問題)

さて、ここからはかなり発展的な内容になります。

ですので、理解できなくても落ち込む必要はありません。

再度お伝えしておくと、

  • フェルマーの小定理(合同式の性質)
  • 完全数(約数関数の性質)
  • 原始ピタゴラス数の公式
  • 互いに素である確率(バーゼル問題)

を簡単に解説していきます。

ウチダ ウチダ
どれも面白い話ばかりですので、ぜひ概要だけでも掴んで友達に自慢しちゃいましょう!

フェルマーの小定理(合同式の性質)

【フェルマーの小定理】
$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$

つまり合同方程式においては、互いに素でなければ両辺を同じ数で割ってはいけない、ということになります。

ウチダ ウチダ
フェルマーの小定理は、現代のネット社会を支えている「RSA暗号」にも応用される、極めて重要な定理です。

参考記事はこちらから

完全数(約数関数の性質)

完全数の記事において、$n$ の正の約数の総和を表す「約数関数 $S(n)$ 」なるものを定めました。

【約数関数の性質】
$n$ と $m$ が互いに素であるとき、$$S(nm)=S(n)S(m)$$が成り立つ。(約数関数の乗法性)

この性質を使って、完全数の公式を証明しました。

ウチダ ウチダ
オイラー関数は「約数でないものの個数」、約数関数は「約数の総和」と定義しました。非常に似てますね。また、どちらも乗法性が成り立ちます。

完全数については「完全数(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)$ はピタゴラス数になる。

ここでも互いに素は大活躍してますね!

ウチダ ウチダ
ピタゴラス数を自分で見つける作業は非常に楽しいです!これも興味のある方は「ピタゴラス数が一発でわかる公式【証明もあわせて解説】」の記事を読んでいただきたいと思います。

互いに素である確率(バーゼル問題)

さて、最後は「適当に選んだ $2$ つの自然数が互いに素である確率」です。

問題. $1$ ~ $n$ までの自然数の中からランダムに $2$ つ選ぶとき、これらが互いに素である確率を $p_n$ とおく。このとき、$\displaystyle \lim_{n \to \infty}p_n$ を求めなさい。

これ、大体何パーセントぐらいだと思いますか?

予想してみてください。

↓↓↓(正解発表)

正解は、なんと…約 $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}$$

これを素数全てに対して行って、すべての積を取ると、

\begin{align}\lim_{n \to \infty}p_n&=(1-\frac{1}{2^2})(1-\frac{1}{3^2})(1-\frac{1}{5^2})…\\&=\frac{1}{ζ(2)}\\&=\frac{6}{π^2}\end{align}

※ $ζ(s)$ はリーマンのゼータ関数と呼ばれ、$ζ(2)$ を求めることは「バーゼル問題」と言われています。

(概要終了)

このように、最終的に「バーゼル問題」を解くことに帰着します。

ウチダ ウチダ
大学数学の知識が必要ですが、高校生が読んでも面白い内容です。詳しくは「バーゼル問題~(準備中)」をお読みください。

互いに素な自然数に関するまとめ

内容が盛りだくさんでしたね(^_^;)

最後に、本記事の要点をまとめたいと思います。

互いに素な自然数は、整数問題の至る所に登場します。

全てを理解する必要はないので、興味が出るところから勉強してみましょう^^

「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!

あわせて読みたい
整数の性質とは?【高校数学Aの解説記事総まとめ25選】
整数の性質とは?【高校数学Aの解説記事総まとめ25選】「整数の性質」の総まとめ記事です。本記事では、整数の性質の解説記事全25個をまとめています。「整数の性質をしっかりマスターしたい」「整数の性質を自分のものにしたい」という方は必見です。

終わりです。

目次