，，3で割って2余るものの個数を
とする。
，
を求めよ。
を示せ。
であるとき、
がとりうる値を求めよ。
，
，
，
，
，
，
，
，
......[答]
に出てくる素数2，5，7のうち、2と5は3で割ると2余り、7は3で割ると1余ります。2800の約数のうち、例えば
は、3で割ると1余りますが、3で割ると2余る数を2つかけた積を3で割ると1余ります。
は、3で割ると2余りますが、3で割ると2余る数を3つかけた積を3で割ると2余ります。3で割ると2余る数と3で割ると1余る数をかけた積を3で割ると2余ります。| 約数 | 7の指数 | 5の指数 | 2の指数 | 5の指数と2の 指数の和 | 約数を3で 割った余り |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 1 | 2 |
| 4 | 0 | 0 | 2 | 2 | 1 |
| 8 | 0 | 0 | 3 | 3 | 2 |
| 16 | 0 | 0 | 4 | 4 | 1 |
| 5 | 0 | 1 | 0 | 1 | 2 |
| 10 | 0 | 1 | 1 | 2 | 1 |
| 20 | 0 | 1 | 2 | 3 | 2 |
| 40 | 0 | 1 | 3 | 4 | 1 |
| 80 | 0 | 1 | 4 | 5 | 2 |
| 25 | 0 | 2 | 0 | 2 | 1 |
| 50 | 0 | 2 | 1 | 3 | 2 |
| 100 | 0 | 2 | 2 | 4 | 1 |
| 200 | 0 | 2 | 3 | 5 | 2 |
| 400 | 0 | 2 | 4 | 6 | 1 |
| 7 | 1 | 0 | 0 | 0 | 1 |
| 14 | 1 | 0 | 1 | 1 | 2 |
| 28 | 1 | 0 | 2 | 2 | 1 |
| 56 | 1 | 0 | 3 | 3 | 2 |
| 112 | 1 | 0 | 4 | 4 | 1 |
| 35 | 1 | 1 | 0 | 1 | 2 |
| 70 | 1 | 1 | 1 | 2 | 1 |
| 140 | 1 | 1 | 2 | 3 | 2 |
| 280 | 1 | 1 | 3 | 4 | 1 |
| 560 | 1 | 1 | 4 | 5 | 2 |
| 175 | 1 | 2 | 0 | 2 | 1 |
| 350 | 1 | 2 | 1 | 3 | 2 |
| 700 | 1 | 2 | 2 | 4 | 1 |
| 1400 | 1 | 2 | 3 | 5 | 2 |
| 2800 | 1 | 2 | 4 | 6 | 1 |
，
とすると、その積は、
とすると、3で割ると1余る数と3で割ると2余る数の積は、
(jは自然数、
，
，･･･，
は素数、
，
，･･･，
は自然数)とします。
，
，･･･，
の中に3があれば、nは3で割り切れるので、
です。･･･①
，
，･･･，
はいずれも3ではないとして考えます。
，
，･･･，
のうち、3で割って1余るものはnを3で割った余りには関係なく、3で割って2余るものだけを考えればよいので、
，
，･･･，
のうち3で割って2余るものを、
，
，･･･，
(kは自然数で
)とすると、残りの
，･･･，
は3で割ると1余ります。
の約数の個数を、
･･･②
，
，･･･，
の指数の和
が奇数であるときに、nを3で割ると2余ります。指数の和
が偶数であるときには、nを3で割ると1余ります。 ･･･(＊＊＊)
の場合
なのですが、上記の表を見てなぜかと考えると、各約数の2の指数が0～4の奇数通り、5の指数が0～2の奇数通りで、5の指数が0のとき、5の指数と2の指数の和が、偶数であるものが3通り、奇数であるものが2通りで、偶数の方が多く、5の指数が1のとき、5の指数と2の指数の和が、偶数であるものが2通り、奇数であるものが3通りで、5の指数が1増えるごとに、偶奇が入れ替わることが分かります。5の指数が0か1だけなら、両者で指数の和が偶数のものと奇数のものとは同数になります。ですが、5の指数が2の場合があり、このときは、5の指数が0の場合と同じく、指数の和が偶数であるものが3通り、奇数であるものが2通りで、5の指数が0か1か2になる場合では、指数の和が偶数であるものの方が多くなり、7の指数は無関係なので、
ということになっています。つまり、素因数分解のうち、3で割ると2余る素数の5と2の部分
の指数がともに偶数なので、
になっていると分かります。
において、3で割ると2余る素数
，
，･･･，
の指数
，
，･･･，
の中に少なくとも1個奇数があって、仮に
が奇数だとします(
，･･･，
のどれであっても同様です)。
が偶数であるものの個数、つまり、
を3で割ると1余る約数の個数は
(
とします)，
が奇数であるものの個数、つまり、
を3で割ると2余る約数の個数は
(
とします)です。
を3で割ると1余る約数の個数
は、
なので、
を3で割ると1余る約数の個数
に等しく、
を3で割ると2余る約数の個数
は、
なので、
を3で割ると2余る約数の個数
に等しく、
を3で割ると1余る約数の個数
は、
を3で割った余りは2であり、
が偶数、つまり、
が奇数であるものの個数
に等しく、
を3で割ると2余る約数の個数
は、
が奇数、つまり、
が偶数であるものの個数
に等しく、
は、
を3で割った余りは1であり、
が偶数、つまり、
が偶数であるものの個数
に等しく、
は、
が奇数、つまり、
が奇数であるものの個数
に等しく、
は奇数なので(以下、
の指数に注意)、0，2，･･･，
が偶数であり、
が奇数であり、
･･･③
において、3で割ると2余る素数
，
，･･･，
の指数
，
，･･･，
が全て偶数だとします。
の約数は、
，
，･･･，
の
個ありますが、このうち、1，
，･･･，
の
個は、3で割ると1余るので、
，
，･･･，
の
個は、3で割ると2余るので、
･･･④
になっています。
の約数は、
，
，･･･，
の
個ありますが、このうち、1，
，･･･，
の
個は、3で割ると1余り、残りの
，
，･･･，
の
個は3で割ると2余るので、
･･･⑤
･･･⑥
になっています。
･･･⑦
の約数は、
，
，･･･，
の
個ありますが、このうち、1，
，･･･，
の
個は、3で割ると1余り、残りの
，･･･，
の
個は3で割ると2余るので、
(∵ ⑦)
ということは、⑧より、
はNを約数にもつので、
または
または
または
です。
のとき、nの素因数分解は、3で割って1余る素数を含まず、3で割って2余る素数の累乗の積の形をしています。
と書けるとき、
となるために、nは
，
，･･･，
を約数に持ちます(3で割って2余る約数は
個です)。このとき、nが
を約数に持つ(
)か持たない(
)かの2通りありますが、nが
を約数に持たなければ、3で割って1余る約数は、
，
，･･･，
の15個で
(pは奇数)，nが
を約数に持てば、3で割って1余る約数は、
，
，･･･，
の16個で
(pは偶数)，この場合は、
･･･⑩
の場合を掲げたので、以後は、
となる場合、即ち、素因数分解において、3で割ると2余る素数の指数が全て正の偶数となる場合のみ考えます。
(
，
は3で割ると2余る素数、
，
は正の偶数)の形に書けるとき、⑤より、
，
ですが、これを満たす自然数
，
は存在しません。
(
，
，
は3で割ると2余る素数、
，
，
は正の偶数)の形に書けるとき、指数が大きくなると
も大きくなるので、まず、
の場合(
)を考えます。
は、
のみの1個で、3で割ると1余る約数の個数
は、
，
の2個で、
，
，以下、
，
，
が3で割ると2余る素数のとき、
，
です。
の約数の個数は、
個なので
･･･⑪
です。
の場合、
，
なので、
です。
は15より大きくなります。
の場合、
の約数の個数は
個なので、⑪より、
です。
(
，
，
，･･･，
は3で割って2余る素数)のタイプで
となるものはありません。
のとき、
(
は3で割ると2余る素数、
は3で割ると1余る素数)の場合、
は3で割ると1余り、
より、
です。
です。
より
となります。このとき、
･･･⑫
(
，
は3で割ると2余る自然数、
は3で割ると1余る素数)の場合、
です。⑧より
，
ですが、⑤より、
，
は存在しません。
(
，
，
は3で割ると2余る自然数、
は3で割ると1余る素数)の場合、指数の小さい
の場合を考えます。⑪より、
も大きくなるので、⑫以外に
となる場合はありません。
のとき、
(
は3で割ると2余る自然数、
は3で割ると1余る自然数)の場合、
は3で割ると1余り、
より、
です。
であり、
です。
となります。このとき、
･･･⑬
(
，
は3で割ると2余る自然数、
は3で割ると1余る素数)の場合、
です。⑧より
，
ですが、⑤より、
，
は存在しません。
も大きくなるので、⑬以外に
となる場合はありません。
のとき、
(
は3で割ると2余る自然数、
は3で割ると1余る自然数)の場合、
は3で割ると1余り、
より、
です。
であり、
です。
となります。このとき、
･･･⑭
(
，
は3で割ると2余る自然数、
は3で割ると1余る素数)の場合、
です。⑧より
，
ですが、⑤より、
，
は存在しません。
(
は3で割ると2余る自然数、
，
は3で割ると1余る素数)の場合、
です。⑧より
，
ですが、
であれば、
の約数で3で割ると2余る数
が1つ存在します。このとき、nの約数は
個ありますが、
･･･⑮
も大きくなるので、⑭，⑮以外に
となる場合はありません。
がとりうる値は、15，16，18，20，30 ......[答]
です。
個ありますが、
，
･･･⑧