はじめに
こんにちは. kkkaaaです. この記事では, 以下の記事で匿(Tock)さんが考案した問題を解きます.
https://mathlog.info/articles/2048
また, 後半では私が昨日
ツイート
した問題も解説します.
問題
(原題から少し表現を変更しています. )
をなる正整数とする. 任意の正整数に対してがの倍数となるようなを全て求めよ.
(解答をすぐに見たくない人もいると思うので少し行間をあけておきます. )
解答
とする.
のときを考える.
の素因数とにおける原始根をとる.
とすると, がの倍数である必要があるため, はの約数である.
正整数に対し, をの正の約数の個数とする. の正の約数を小さい順にとして, でを定義する. の素因数はとなる整数が存在する.
Zsigmondyの定理より, 以上の整数がを満たすとき, の素因数のうち, におけるの位数がとなるものが存在する. はの約数であるため, となる整数が存在するときの素因数は個以上, そのようなが存在しないとき個以上である.
前者の場合, より, の以外の正の約数にを足した数は素数である必要がある. よっては以外の素因数を持たず, を約数に持たず, を約数として持つため, .
後者の場合, より, の以外の正の約数にを足した数は素数である必要がある. よって, は奇素数を素因数として持たず, を約数に持たないため, .
以上より, の場合も含めて.
のときを考えると, がの倍数となる必要があるため, 列挙すると, 以下のようになる.
これらが条件を満たすか調べると, 以外の13個は条件を満たすため, 問題の条件を満たすは, 以下の個である.
別解という名の縛りプレイ
上の解答はZsigmondyの定理を知っている前提だったが, 知らない人向けにZsigmondyの定理(や, 円分多項式)を使わないでが上で示した通りであることを示す. その前に, 以下の補題を示す. なお, この補題の証明は, 冒頭でも書いた, 私がツイートした問題の解説にもなっている.
正整数に対し, をの正の約数の個数とする. となる正整数は, 以下の個である.
の正の約数のうち以下のものは, が平方数でないとき個, が平方数のとき個であるため, .
よって,
ゆえに, 微分や数学的帰納法等を用いると, であることがわかる.
より, で, となる.
互いに素な整数に対し, である. すなわち関数は乗法的関数である.
が素べきで, となるものを列挙すると, 以下のようになる.
よって, となる以上の整数は以下のようになる.
これらのうちを満たすものは以下の個である.
余談だが, なる実数で, を満たす以上の整数を考え, を素数とすると, がの素因数になり得ることと, となることは同値である. (上の議論を利用して証明できる. )
それでは, 本題に戻り, Zsigmondyの定理を使わずにが上で示した通りであることを示す.
とする.
のときを考える.
の素因数とにおける原始根をとる. 二項定理より, .
よって, または.
ゆえに, をがで割り切れる回数とすると, における位数がとなる整数で, となるものが存在する.
とすると, がの倍数となる必要があるため, はの倍数である.
LTEの補題より, 以下が成立する.
よって, .
をの正の約数の個数とすると, がの約数であるため, の素因数の個数は高々である. (は明らかにを素因数として持たないため. ) また, それらの素因数はいずれも以下である.
の素因数を小さい順にとおくと, 以下が成立する.
よって,
補題より, の場合も含めては高々通りであり, はそれぞれの素因数であるため, に限られる.
のときも含めてのときを考えると, がの倍数となる必要があるため, 各に対しては有限個に絞られるため, 問題の条件を満たすは上で示した通りである.
おわりに
計算ミス等の確認をあまりしていないので, 間違いが結構あるかもしれません. 間違いらしき点を見つけたらコメントで優しく教えてもらえると助かります.