【標準】互いに素と自然数解

🕒 2018/07/25 🔄 2023/05/01

ここでは、「互いに素」という条件を使って、ある方程式を満たす自然数の解を求める問題を見ていきます。

📘 目次

互いに素の性質の復習

【基本】互いに素の後半で、互いに素な2つの整数に関する性質を見ました。 $a,b$ が互いに素な整数で、 $k$ を整数とするとき、 $ak$ が $b$ の倍数なら、 $k$ は $b$ の倍数だ、という性質です。

これは、例えば、 $3k$ が $4$ の倍数だとしたら、 $k$ は $4$ の倍数だ、といってるわけですが、こうして見てみると当たり前ですね。 $k$ が $4$ の倍数でなければ、 $3$ を掛けたところで $4$ の倍数にはなりません。 $3$ と $4$ が互いに素で、共通の素因数がないからですね。

この性質は、単体で見ると当たり前に感じるかもしれません。そこで、具体的にどのように使うかを見てみましょう。

互いに素と自然数解

例題

次の方程式を満たす正の整数の組 $(x,y)$ をすべて求めなさい。\[ 3x+4y=72 \]

普通、文字が2つ入っている方程式を解くには、少なくとも式が2つ必要です。今の場合、条件式が1つだけなので、普通は答えは定まらないのですが、今は「正の整数の組」だけに限定しているので、解を特定することができます。

極端な話、 $x=100$ とすると、 $y$ は負になってしまいます。このことからも、 $x,y$ が取りうる値は、そんなに大きくないことが予想できます。

具体的に、どれくらいの値までとり得るのか、考えてみましょう。 $y=0$ とすれば、 $3x=72$ なので、 $x=24$ ですね。なので、 $x$ は24未満だとわかります。同様にすれば $y$ は $18$ 未満であることがわかります。確かに限定されますが、まだ量が多いです。もっと限定することはできないでしょうか。

ここで、先ほどの「互いに素」の性質を使うことができます。条件式を変形すれば、次のようになります。\[ 3x=72-4y=4(18-y) \]これを見ると、 $3x$ は $4$ の倍数になっていることがわかります。 $3$ と $4$ は互いに素なので、先ほどの性質により、 $x$ は $4$ の倍数であることがわかります。 $k$ のところを $x$ に読み替えているわけですね。

さらに、逆向きに考えてみると、 $4(18-y)$ は $3$ の倍数だ、ということもできます。ここでも、先ほどの性質から、 $18-y$ は $3$ の倍数であることがわかります。 $k$ のところを $18-y$ に読み替えたわけです。

これらの手がかりから、大幅に候補を減らすことができます。もともと候補の少なかった $y$ について考えてみましょう。\[ 3x=4(18-y) \]で、左辺は正だから右辺も正です。よって、 $y$ は1以上18未満の整数です。また、先ほど見た通り、 $18-y$ は3の倍数でもあります。よって、\[ y=3,6,9,12,15 \]の5通りしか候補がないことがわかります。

これらを入れて確かめていけば、 $(x,y)$ は $(20,3)$, $(16,6)$, $(12,9)$, $(8,12)$, $(4,15)$ の5組であることがわかります。

$3x+4y=72$ という方程式で、係数の $3,4$ が互いに素であることから、 $3x=4(18-y)$ と変形することで道が開けたわけですね。「 $3k$ が $4$ の倍数なら、 $k$ は $4$ の倍数」ということを利用するために、このような変形をしました。こうした変形は、今後もよく登場します。