・ ある場合の数 Ｓ．Ｈ氏
２つの正の整数 Ａ 、 Ｂ について、最大公約数を Ｇ とすると、
Ａ＝ａＧ 、 Ｂ＝ｂＧ ただし、 ａ と ｂ は互いに素
と書かれることは、よく知られた事実である。また、このとき、最小公倍数 Ｌ は、
Ｌ＝ａｂＧ
で求められる。
最近、この公式を用いた問題で感動的な計算手法に遭遇したので紹介したいと思う。
問 題 ２つの正の整数 Ａ 、 Ｂ （Ａ＜Ｂ） の最小公倍数が、３０ となるような
Ａ 、 Ｂ の
組（Ａ，Ｂ）は何通りあるか？
まずは、誰でも（？）が計算すると思われるような方法から．．．。
（解） 最大公約数を Ｇ とすると、 Ａ＝ａＧ 、 Ｂ＝ｂＧ （ただし、
ａ と ｂ は互いに素）
と書ける。このとき、 ａｂＧ＝３０＝２×３×５ で、 ２ 、３ 、５ は互いに素である。
最大公約数 Ｇ の取り得る値は、 Ｇ＝ １ 、 ２ 、 ３ 、 ５ 、 ６ 、
１０ 、 １５ 、 ３０ で、
場合に分けて数え上げる。
Ｇ＝１ のとき、 ａｂ＝３０＝２×３×５ （ただし、 ａ と ｂ
は互いに素）
このとき、 ａ ＝ １ 、 ２ 、 ３ 、 ５ 、 ６ 、 １０ 、 １５
、 ３０
ｂ ＝ ３０ 、 １５ 、 １０ 、６ 、 ５ 、 ３ 、
２ 、 １
Ａ＜Ｂ より、 ａ＜ｂ なので、
（ ａ ， ｂ ）＝（ １ ， ３０ ）、（ ２ ， １５ ）、（
３ ， １０ ）、（ ５ ， ６ ）
よって、このときの場合の数は、 ４通り
Ｇ＝２ のとき、 ａｂ＝１５＝３×５ （ただし、 ａ と ｂ は互いに素）
このとき、 ａ ＝ １ 、 ３ 、 ５ 、 １５
ｂ ＝ １５ 、 ５ 、 ３ 、 １
Ａ＜Ｂ より、 ａ＜ｂ なので、 （ ａ ， ｂ ）＝（ １
， １５ ）、（ ３ ， ５ ）
よって、このときの場合の数は、 ２通り
Ｇ＝３ 、 ５ のときも同様にして場合の数はそれぞれ、 ２通り
Ｇ＝６ のとき、 ａｂ＝５ （ただし、 ａ と ｂ は互いに素）
このとき、 ａ ＝ １ 、 ５
ｂ ＝ ５ 、 １
Ａ＜Ｂ より、 ａ＜ｂ なので、 （ ａ ， ｂ ）＝（ １
， ５ ）
よって、このときの場合の数は、 １通り
Ｇ＝１０ 、 １５ のときも同様にして場合の数はそれぞれ、 １通り
Ｇ＝３０ のとき、 ａｂ＝１ （ただし、 ａ と ｂ は互いに素）
このとき、 ａ ＝ １ で、 ｂ ＝ １
これは、 Ａ＜Ｂ より、 ａ＜ｂ であることに矛盾する。
よって、このような場合は起こらない。
以上から、求める場合の数は、 ４＋２＋２＋２＋１＋１＋１＝１３ （通り） （終）
これに対して、次のような解答を見せられると、暑さが吹っ飛ぶようだ。
（別解） 最大公約数を Ｇ とすると、 Ａ＝ａＧ 、 Ｂ＝ｂＧ （ただし、
ａ と ｂ は互いに素）
と書ける。このとき、 ａｂＧ＝３０＝２×３×５ で、 ２ 、３ 、５ は互いに素である。
２ という値は、 ａ または ｂ または Ｇ の何れかが取り得る。よって、３ （通り）。
このうちの１通りに対して、
３ という値も、 ａ または ｂ または Ｇ の何れかが取り得るので、３ （通り）。
このうちの１通りに対して、
５ という値も、 ａ または ｂ または Ｇ の何れかが取り得るので、３ （通り）。
よって、 ａ 、 ｂ 、 Ｇ の３個の文字の重複順列の数は、 ３3＝２７ （通り）
このうち、 ＧＧＧ すなわち、 ａ＝１、ｂ＝１、Ｇ＝３０ という場合は除かれる。
また、 Ａ＜Ｂ より、 ａ＜ｂ であるので、求める場合の数は、
（終）
（コメント） 別解のような柔軟な発想に、いたく感動しました！
読者のために、練習問題を残しておくことにしよう。
練習問題 ２つの正の整数 Ａ 、 Ｂ （Ａ＜Ｂ）の最小公倍数が、２１０ となるような Ａ 、Ｂ
の組（Ａ，Ｂ）は何通りあるか？
（解） ２１０＝２×３×５×７ より、求める場合の数は、（３4−１）/２＝４０ （通り） （終）
この解法について、ＦＮさんが研究の端緒を開かれた。（平成２２年６月６日付け）
上記の問題を完全に一般的な形にするのは表現が複雑になるだけである。少し一般化
した次の問題が解ければこの手の問題はすべて解けることになる。
２つの正の整数Ａ、Ｂ(Ａ＜Ｂ)の最小公倍数が ２p・３q・５r となるような組は何通
りあるか？
この問いかけに、ＧＡＩ さんが表を活用して解を求められた。（平成２２年６月７日付け）
| ｐ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
２ |
２ |
２ |
| ｑ |
１ |
１ |
１ |
１ |
２ |
２ |
２ |
２ |
３ |
３ |
３ |
３ |
２ |
２ |
２ |
| ｒ |
１ |
２ |
３ |
４ |
１ |
２ |
３ |
４ |
１ |
２ |
３ |
４ |
１ |
２ |
３ |
| 組の数 |
２７ |
４５ |
６３ |
８１ |
４５ |
７５ |
１０５ |
１３５ |
６３ |
１０５ |
１４７ |
１８９ |
７５ |
１２５ |
１７５ |
| ｐ |
２ |
２ |
２ |
２ |
２ |
２ |
２ |
２ |
２ |
３ |
３ |
３ |
３ |
| ｑ |
２ |
３ |
３ |
３ |
３ |
４ |
４ |
４ |
４ |
１ |
１ |
１ |
１ |
| ｒ |
４ |
１ |
２ |
３ |
４ |
１ |
２ |
３ |
４ |
１ |
２ |
３ |
４ |
| 組の数 |
２２５ |
１０５ |
１７５ |
２４５ |
３１５ |
１３５ |
２２５ |
３１５ |
４０５ |
６３ |
１０５ |
１４７ |
１８９ |
| ｐ |
３ |
３ |
３ |
３ |
３ |
３ |
３ |
３ |
| ｑ |
２ |
２ |
２ |
２ |
３ |
３ |
３ |
３ |
| ｒ |
１ |
２ |
３ |
４ |
１ |
２ |
３ |
４ |
| 組の数 |
１０５ |
１７５ |
２４５ |
３１５ |
１４７ |
２４５ |
３４３ |
４４１ |
この表から、２p・３q・５1 の数列に注目すると、
| ｐ |
１ |
１ |
１ |
２ |
２ |
２ |
３ |
３ |
３ |
| ｑ |
１ |
２ |
３ |
２ |
３ |
４ |
１ |
２ |
３ |
| ｒ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
１ |
| 組の数 |
２７ |
４５ |
６３ |
７５ |
１０５ |
１３５ |
６３ |
１０５ |
１４７ |
となっている。
ｐ＝１ のとき、ｑ＝１、２、３ と増えるに従い、組の数も ２７、４５、６３ と増えている。
この数列は、初項 ２７ で、公差 １８ の等差数列と考えられる。
同様に、
ｐ＝２ のとき、ｑ＝２、３、４ と増えるに従い、組の数も ７５、１０５、１３５ と増えている。
このことから、ｑ＝１ も含めて、初項 ４５ で、公差 ３０ の等差数列と考えられる。
このとき、ｐ＝１ から ｐ＝２ と増えるに従い、 ２７ から ４５ と １８ だけ増えている。
ｐ＝３ のとき、ｑ＝１、２、３ と増えるに従い、組の数も ６３、１０５、１４７ と増えている。
この数列は、初項 ６３ で、公差 ４２ の等差数列と考えられる。
このとき、ｐ＝２ から ｐ＝３ と増えるに従い、 ４５ から ６３ と １８ だけ増えている。
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
以上から、 ｐ＝１、２、３ に対応する数列は、 ２７、４５、６３ なので、
一般項は、 ２７＋１８（ｐ−１）＝９（２ｐ＋１）
ｐ＝１、２、３ に従い、増える組の数は
ｑ＝１ のとき、 ０ 、 ０ 、 ０
ｑ＝２ のとき、 １８ 、３０ 、 ４２
ｑ＝３ のとき、 ３６ 、 ６０ 、 ８４
よって、一般に、 ２p・３q・５1 となるような組は、
３2（２ｐ＋１）＋｛１８＋１２（ｐ−１）｝（ｑ−１） ・・・（***)
であることが導かれ、 ２p・３q・５r となるような組は、
(***)＋［１８＋１２（ｐ−１）＋｛１２＋８（ｐ−１）｝（ｑ−１）］（ｒ−１）
＝(***)＋｛１２ｐ＋６＋（４＋８ｐ）（ｑ−１）｝（ｒ−１）
で与えられるので、これを整理すると、
＝（２ｐ＋１）（２ｑ＋１）（２ｒ＋１）
に辿り着きました。(意外と美しい式に終わりびっくり！）
Ａ＝Ｂ のときと Ｂ＜Ａ での対称形を考慮して、求める場合の数は、
｛（２ｐ＋１）（２ｑ＋１）（２ｒ＋１）−１｝/２
となる。
ＦＮさんによれば、上記の式でＯＫとのこと！（平成２２年６月７日付け）ただ式の導き方と
しては、「投稿一覧」の「ある場合の数」の解答とほとんど同じように、もっと直接的にできる
そうである。
下記の解はＦＮさんによるものである。（平成２２年６月９日付け）
（解） Ａ、Ｂの最大公約数をＧとして、 Ａ＝ａＧ 、Ｂ＝ｂＧ （ただし、
ａ と ｂ は互いに素）
とする。このとき、 ａｂＧ＝２p・３q・５r において、素因数２について考える。
ａ、ｂ、Ｇ で素因数２を、合わせてｐ個持つが、ａ、ｂは互いに素だから、一方は素因数２
を持たない。ｂが素因数２を持たない場合を考えると、ａとＧで、合わせてｐ個持つことに
なり、
（ａに含まれる２の個数，Ｇに含まれる２の個数）＝（０，ｐ）、（１，ｐ−１）、・・・、（ｐ，０）
の ｐ＋１通りある。このうち最初のもの以外は、ａ、ｂ を入れ替えたものがあるので、合わ
せて、２ｐ＋１通りとなる。
このうちの１通りに対して、素因数３について同様にして、２ｑ＋１通り、さらに、このうち
の１通りに対して、素因数５について、２ｒ＋１通りある。
従って、積の法則により、求める場合の数は、（２ｐ＋１）（２ｑ＋１）（２ｒ＋１）通りとなる。
この中に、ａ＝１、ｂ＝１、Ｇ＝２p・３q・５r 即ち Ａ＝Ｂ の場合が入っているので、これは
除き、さらに、Ａ＜Ｂ なので、２で割って結果が得られる。（終）
（コメント） この解は、冒頭の問題の本解の方の流れを汲む解法ですね！
さらに、ＧＡＩ
さんは、次のような新しい問題を提起された。（平成２２年６月８日付け）
３つの正の整数Ａ、Ｂ、Ｃ（Ａ＜Ｂ＜Ｃ）の最小公倍数が ２p・３q・５r となるような
組は何通りあるか？
さらに、
４つの正の整数Ａ、Ｂ、Ｃ、Ｄ（Ａ＜Ｂ＜Ｃ＜Ｄ）の最小公倍数が ２p・３q・５r とな
るような組は何通りあるか？
これに対して、ＦＮさんは、素因数の数を減らし、Ａ＜Ｂ＜Ｃという条件を無視して、次の問
題を提起された。（平成２２年６月８日付け）
３つの正の整数Ａ、Ｂ、Ｃの最小公倍数が ２p となるような組は何通りあるか？
この問題の解答として、ＧＡＩ
さんは、「３ｐ2＋３ｐ＋１」であることを見いだされた。
（平成２２年６月８日付け）
ＦＮさんによれば、素因数が１個の場合を補題として独立させ、問題を２つに分ければ、も
っとすっきりするだろうとのことである。（平成２２年６月９日付け）
補 題 ｐ を素数、ｅ を自然数とする。２つの自然数Ａ、Ｂの最小公倍数が、ｐｅ と
なるようなＡ、Ｂの組は、２ｅ＋１通りある。
命 題 ｐ、ｑ、・・・、ｒ を素数、ｅ、ｆ、・・・、ｇ を自然数とする。
２つの自然数Ａ、Ｂ（Ａ＜Ｂ）の最小公倍数が、ｐｅ・ｑｆ・・・ｒｇ となるような
Ａ、Ｂの組は、 ｛（２ｅ＋１）（２ｆ＋１）・・・（２ｇ＋１）−１｝/２ 通りある。
上記において、補題部分すなわち素因数１個の場合がかなり重要な位置を占めています。
３つの整数Ａ、Ｂ、Ｃ の場合でもそうです。当然２つの場合より難しいです。考え方は同様で
すが簡単な数列の和を計算することになります。ということで前に書いた問題
３つの正の整数Ａ、Ｂ、Ｃの最小公倍数が ２p となるような組は何通りあるか？
あるいは
補 題 ｐ を素数、ｅ を自然数とする。３つの自然数Ａ、Ｂ、Ｃの最小公倍数が、ｐｅ と
なるような組は、３ｅ2＋３ｅ＋１通りある。
の証明はどうなるでしょうか？
このＦＮさんの問いかけに対して、らすかるさんが補題を一般化して証明された。
（平成２２年６月９日付け）
補 題（らすかる）
ｐ を素数、ｅ を自然数とする。ｎ個の自然数の最小公倍数が、ｐｅ となるような組
は、（ｅ＋１）ｎ−ｅｎ 通りある。
（証明） ｎ個の自然数がすべて ｐ0〜ｐｅ のいずれかである場合の数 （ｅ＋１）ｎ から
ｎ個の自然数がすべて ｐ0〜ｐｅ-1 のいずれかである場合の数 ｅｎ を引けばよい。
（証終）
（コメント） 言われてみると思わず納得．．．。正に「目から鱗」の証明で感動しました！
平成２２年６月１４日付けで、ＦＮさんより、ＧＡＩさんが提起された次の問題
３つの正の整数Ａ、Ｂ、Ｃ（Ａ＜Ｂ＜Ｃ）の最小公倍数が ２p・３q・５r となるような
組は何通りあるか？
の解答をお寄せいただいた。ＦＮさんに感謝します。
次の補題は、３個を ｎ 個にした形でらすかるさんが証明された。
補 題 ｐ を素数、ｅ
を自然数とする。３つの自然数Ａ、Ｂ、Ｃの最小公倍数が、ｐｅ と
なるような組は、３ｅ2＋３ｅ＋１通りある。
補 題（らすかる）
ｐ を素数、ｅ
を自然数とする。ｎ個の自然数の最小公倍数が、ｐｅ となるような組
は、（ｅ＋１）ｎ−ｅｎ
通りある。
文字の使い方が問題と補題で違うことに注意。補題及び２個の場合の結果（ただし、Ａ＜Ｂ
でなく、Ａ≠Ｂとした形で書くことにする）
２つの正の整数
Ａ、Ｂ（Ａ≠Ｂ）の最小公倍数が、２p・３q・５r となるような組は、
（２ｐ＋１）（２ｑ＋１）（２ｒ＋１）−１
通りある。・・・（＊）
を用いて解く。
（解） まず、条件 Ａ＜Ｂ＜Ｃ がないとして考える。
正の整数 Ａ、Ｂ、Ｃ の最小公倍数が、２p・３q・５r であるとする。もちろん、Ａ、Ｂ、Ｃ は、
２、３、５以外の素因数を持たない。
Ａを素因数分解したときの２の累乗部分を Ａ1、３の累乗部分を Ａ2、５の累乗部分を Ａ3
とする。このとき、 Ａ＝Ａ1・Ａ2・Ａ3 である。
（もちろん、Ａ1、Ａ2、Ａ3
のどれか１つか２つ或いは全部が1であることはありうる。)
Ｂ、Ｃも同様に、Ｂ＝Ｂ1・Ｂ2・Ｂ3、Ｃ＝Ｃ1・Ｃ2・Ｃ3 とする。
Ａ1、Ａ2、Ａ3
の最小公倍数は、２p であるから、Ａ1、Ａ2、Ａ3
の取り方は、補題により
３ｐ2＋３ｐ＋１通りある。
同様にして、Ｂ1、Ｂ2、Ｂ3 の取り方、Ｃ1、Ｃ2、Ｃ3 の取り方もそれぞれ、
３ｑ2＋３ｑ＋１通り 、３ｒ2＋３ｒ＋１通り である。
従って、Ａ、Ｂ、Ｃ の取り方は、（ ３ｐ2＋３ｐ＋１）（３ｑ2＋３ｑ＋１）（３ｒ2＋３ｒ＋１）通りある。
この中には２つが同じ場合、３つが同じ場合も含む。
３つが同じ場合は1通りである。
２つが同じ場合を考える。
Ａ＝Ｂ≠Ｃ の場合は（＊）と同じである。Ｂ＝Ｃ≠Ａ、Ｃ＝Ａ≠Ｂ についても同様。
従って、３（２ｐ＋１）（２ｑ＋１）（２ｒ＋１）−３ 通りある。
以上から、Ａ、Ｂ、Ｃ がすべて異なる場合は、
（
３ｐ2＋３ｐ＋１）（３ｑ2＋３ｑ＋１）（３ｒ2＋３ｒ＋１）
−｛３（２ｐ＋１）（２ｑ＋１）（２ｒ＋１）−３｝−１通り
すなわち、
（
３ｐ2＋３ｐ＋１）（３ｑ2＋３ｑ＋１）（３ｒ2＋３ｒ＋１）−３（２ｐ＋１）（２ｑ＋１）（２ｒ＋１）＋２通り
このうち、Ａ＜Ｂ＜Ｃ となるのは、１/６なので、求める場合の数は、
｛（
３ｐ2＋３ｐ＋１）（３ｑ2＋３ｑ＋１）（３ｒ2＋３ｒ＋１）
−３（２ｐ＋１）（２ｑ＋１）（２ｒ＋１）＋２｝/６ 通り
となる。 （終）
さらに、ＦＮさんは、これを ４個、５個、・・・としたときに、できそうかどうかを考えられた。
２つのとき、Ａ＜Ｂ、３つのとき、Ａ＜Ｂ＜Ｃ としたが、上の証明でもわかるように、Ａ と Ｂ
あるいは、Ａ と Ｂ と Ｃ は相異なる、とする方が自然である。後で、２！や３！、・・・、ｎ！で
割るかどうかだけのことなので問題として、次の形で考える。
相異なる ｎ 個の自然数でその最小公倍数が、
Ｌ＝ｐｅ・ｑｆ・・・・ｒｇ （ｐ、ｑ、・・・ｒ
は相異なる素数、ｅ、ｆ、・・・ｇ
は自然数)
であるような組は何通りあるか。
この答えを、Ｆ（ｎ）通りと書くことにする。
まず、らすかるさんの一般化された補題：
補 題（らすかる）
ｐ を素数、ｅ
を自然数とする。ｎ個の自然数の最小公倍数が、ｐｅ となるような組
は、（ｅ＋１）ｎ−ｅｎ
通りある。
において、 （ｅ＋１）ｎ−ｅｎ＝ｗ（ｎ，ｅ） と書くことにする。
まず、相異なるという条件を忘れて、最小公倍数が Ｌ＝ｐｅ・ｑｆ・・・・ｒｇ であるような ｎ 個
の自然数の組が、「ｗ（ｎ，ｅ）ｗ（ｎ，ｆ）・・・ｗ（ｎ，ｇ）通り」あることは上と同様に考えてわかる。
Ｌ＝ｐｅ・ｑｆ・・・・ｒｇ は固定して考えるので、ｗ（ｎ，ｅ）ｗ（ｎ，ｆ）・・・ｗ（ｎ，ｇ）＝Ｗ（ｎ）と書くこと
にする。
このとき、先の結果より、
Ｗ（１）＝１ 、 Ｗ（２）＝（２ｅ＋１）（２ｆ＋１）・・・（２ｇ＋１）
Ｗ（３）＝（３ｅ2＋３ｅ＋１）（３ｆ2＋３ｆ＋１）・・・（３ｇ2＋３ｇ＋１）・・・
である。
上で示したことは、 Ｆ（３）＝Ｗ（３）−３Ｗ（２）＋２Ｗ（１） である。
また、２個、１個の場合の結果は、Ｆ（２）＝Ｗ（２）−Ｗ（１）、Ｆ（１）＝Ｗ（１） である。
Ｆ（３）を計算した過程を書けば、
Ｆ（３）＝Ｗ（３）−３Ｆ（２）−Ｆ（１）
＝Ｗ（３）−３（Ｗ（２）−Ｗ（１））−Ｗ（１）
＝Ｗ（３）−３Ｗ（２）＋２Ｗ（１）
そこで、４個の場合を考えると、
Ｆ（４）＝Ｗ（４）−６Ｆ（３）−（４＋３）Ｆ（２）−Ｆ（１）
＝・・・・
＝Ｗ（４）−６Ｗ（３）＋１１Ｗ（２）−６Ｗ（１）
ただし、６Ｆ（３）の６は、4Ｃ2 で、（４＋３）Ｆ（２）の４は、4Ｃ1 で、３は、4Ｃ2/２ である。
（コメント） 考え方の道筋が分かりました。ＦＮさんに感謝します。
以下、工事中
