2
競技数学解説
文献あり

n^a-n^bが2^a-2^bの倍数となるa,bを求める

524
1

はじめに

こんにちは. kkkaaaです. この記事では, 以下の記事で匿(Tock)さんが考案した問題を解きます.
https://mathlog.info/articles/2048
また, 後半では私が昨日 ツイート した問題も解説します.

問題

(原題から少し表現を変更しています. )

a,ba>bなる正整数とする. 任意の正整数nに対してnanb2a2bの倍数となるような(a,b)を全て求めよ.

(解答をすぐに見たくない人もいると思うので少し行間をあけておきます. )























解答

ab=cとする.
c>1のときを考える.
2c1の素因数pmodpにおける原始根rをとる.
n=rとすると, rc1pの倍数である必要があるため, p1cの約数である.
正整数nに対し, d(n)nの正の約数の個数とする. cの正の約数を小さい順にa1,a2,,ad(c)として, pi=ai+1p1,p2,,pd(c)を定義する. 2c1の素因数pp=piとなる整数iが存在する.
Zsigmondyの定理より, 2以上の整数iai6を満たすとき, 2ai1の素因数のうち, modpにおける2の位数がaiとなるものが存在する. 2ai12c1の約数であるため, ak=6となる整数kが存在するとき2ai1の素因数はd(c)2個以上, そのようなkが存在しないときd(c)1個以上である.
前者の場合, p1=2,p3=4より, c1,3以外の正の約数に1を足した数は素数である必要がある. よってc2,3以外の素因数を持たず, 8,9を約数に持たず, 6を約数として持つため, c=6,12.
後者の場合, p1=2より, c1以外の正の約数に1を足した数は素数である必要がある. よって, cは奇素数を素因数として持たず, 8を約数に持たないため, c=2,4.
以上より, c=1の場合も含めてc=1,2,4,6,12.
n=3のときを考えると, 3c12bの倍数となる必要があるため, 列挙すると, 以下のようになる.
(a,b,c)=(2,1,1),(3,1,2),(4,2,2),(5,1,4),(5,3,2),(6,2,4),(7,1,6),(7,3,4),(8,2,6),(8,4,4),(9,3,6),(13,1,12),(14,2,12),(15,3,12),(16,4,12)
これらが条件を満たすか調べると, (a,b,c)=(7,1,6),(13,1,12)以外の13個は条件を満たすため, 問題の条件を満たす(a,b)は, 以下の13個である.
(a,b)=(2,1),(3,1),(4,2),(5,1),(5,3),(6,2),(7,3),(8,2),(8,4),(9,3),(14,2),(15,3),(16,4)

別解という名の縛りプレイ

上の解答はZsigmondyの定理を知っている前提だったが, 知らない人向けにZsigmondyの定理(や, 円分多項式)を使わないで(a,b)が上で示した13通りであることを示す. その前に, 以下の補題を示す. なお, この補題の証明は, 冒頭でも書いた, 私がツイートした問題の解説にもなっている.

正整数nに対し, d(n)nの正の約数の個数とする. 2nnd(n)となる正整数nは, 以下の22個である.
n=2,3,4,6,8,9,10,12,14,15,16,18,20,24,28,30,36,40,42,48,60,72

nの正の約数のうちn以下のものは, nが平方数でないときd(n)2個, nが平方数のときd(n)+12個であるため, d(n)<2n.
よって, 2nnd(n)n<n2
ゆえに, 微分や数学的帰納法等を用いると, 2n255であることがわかる.
n<256より, 2nnd(n)<28d(n)で, n<8d(n)となる.
互いに素な整数(x,y)に対し, xyd(xy)=xd(x)×yd(y)である. すなわち関数xd(x)は乗法的関数である.
nが素べきで, nd(n)<8となるものを列挙すると, 以下のようになる.

nnd(n)nnd(n)
211323
224333274
2325152
241657172
25163111112
3132131132

よって, nd(n)<8となる2以上の整数nは以下のようになる.
2n16,n=18,20,21,22,24,26,27,28,30,32,36,40,42,44,45,48,54,56,60,72,84,90,120
これらのうち2nnd(n)を満たすものは以下の22個である.
n=2,3,4,6,8,9,10,12,14,15,16,18,20,24,28,30,36,40,42,48,60,72

余談だが, 1<t2なる実数tで, tnnd(n)を満たす2以上の整数nを考え, pを素数とすると, pnの素因数になり得ることと, tp<4p2となることは同値である. (上の議論を利用して証明できる. )

それでは, 本題に戻り, Zsigmondyの定理を使わずに(a,b)が上で示した13通りであることを示す.

ab=cとする.
c>1のときを考える.
2c1の素因数pmodpにおける原始根rをとる. 二項定理より, (p+1)p11(modp2).
よって, rp11(modp2)または(r(p+1))p11(modp2).
ゆえに, vp(n)npで割り切れる回数とすると, modpにおける位数がp1となる整数sで, vp(sp11)=1となるものが存在する.
n=sとすると, sc1pの倍数となる必要があるため, cp1の倍数である.
LTEの補題より, 以下が成立する.
vp(sc1)=vp(sp11)+vp(cp1)=vp(cp1)+1
よって, pvp(sc1)pcp1.
d(n)nの正の約数の個数とすると, p1cの約数であるため, 2c1の素因数の個数kは高々d(c)1である. (2c1は明らかに2を素因数として持たないため. ) また, それらの素因数はいずれもc+1以下である.
2c1の素因数を小さい順にp1,p2,,pkとおくと, 以下が成立する.
2c1=p1vp1(sc1)p2vp2(sc1)pkvpk(sc1)ck×p1p11×p2p21××pkpk1cd(c1)×3××(c+1)2××c<cd(c)
よって, 2ccd(c)
補題より, c=1の場合も含めてcは高々23通りであり, 7,17,31,73,127,151,257はそれぞれ231,281,251,291,271,2151,2161の素因数であるため, c=1,2,4,6,12に限られる.
c=1のときも含めてn=3のときを考えると, 3c12bの倍数となる必要があるため, 各cに対してbは有限個に絞られるため, 問題の条件を満たす(a,b)は上で示した13通りである.

おわりに

計算ミス等の確認をあまりしていないので, 間違いが結構あるかもしれません. 間違いらしき点を見つけたらコメントで優しく教えてもらえると助かります.


参考文献

投稿日:2021915
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

kkkaaa
25
9362

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 問題
  3. 解答
  4. 別解という名の縛りプレイ
  5. おわりに
  6. 参考文献