n^a-n^bが2^a-2^bの倍数となるa,bを求める
はじめに
こんにちは. kkkaaaです. この記事では, 以下の記事で匿(Tock)さんが考案した問題を解きます.
https://mathlog.info/articles/2048
また, 後半では私が昨日
ツイート
した問題も解説します.
問題
(原題から少し表現を変更しています. )
$a, b$を$a>b$なる正整数とする. 任意の正整数$n$に対して$n^a-n^b$が$2^a-2^b$の倍数となるような$(a,b)$を全て求めよ.
(解答をすぐに見たくない人もいると思うので少し行間をあけておきます. )
解答
$a-b=c$とする.
$c>1$のときを考える.
$2^c-1$の素因数$p$と$\bmod p$における原始根$r$をとる.
$n=r$とすると, $r^c-1$が$p$の倍数である必要があるため, $p-1$は$c$の約数である.
正整数$n$に対し, $d(n)$を$n$の正の約数の個数とする. $c$の正の約数を小さい順に$a_1, a_2, \cdots, a_{d(c)}$として, $p_i=a_i+1$で$p_1, p_2,\cdots, p_{d(c)}$を定義する. $2^c-1$の素因数$p$は$p=p_i$となる整数$i$が存在する.
Zsigmondyの定理より, $2$以上の整数$i$が$a_i\neq 6$を満たすとき, $2^{a_i}-1$の素因数のうち, $\bmod p$における$2$の位数が$a_i$となるものが存在する. $2^{a_i}-1$は$2^c-1$の約数であるため, $a_k=6$となる整数$k$が存在するとき$2^{a_i}-1$の素因数は$d(c)-2$個以上, そのような$k$が存在しないとき$d(c)-1$個以上である.
前者の場合, $p_1=2, p_3=4$より, $c$の$1,3$以外の正の約数に$1$を足した数は素数である必要がある. よって$c$は$2,3$以外の素因数を持たず, $8,9$を約数に持たず, $6$を約数として持つため, $c=6,12$.
後者の場合, $p_1=2$より, $c$の$1$以外の正の約数に$1$を足した数は素数である必要がある. よって, $c$は奇素数を素因数として持たず, $8$を約数に持たないため, $c=2,4$.
以上より, $c=1$の場合も含めて$c=1,2,4,6,12$.
$n=3$のときを考えると, $3^c-1$が$2^b$の倍数となる必要があるため, 列挙すると, 以下のようになる.
$$(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$の正の約数の個数とする. $2^n\leq n^{d(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$の正の約数のうち$\sqrt{n}$以下のものは, $n$が平方数でないとき$\dfrac{d(n)}{2}$個, $n$が平方数のとき$\dfrac{d(n)+1}{2}$個であるため, $d(n)<2\sqrt{n}$.
よって, $2^\sqrt{n}\leq n^{\tfrac{d(n)}{\sqrt{n}}} < n^2$
ゆえに, 微分や数学的帰納法等を用いると, $2\leq n\leq255$であることがわかる.
$n<256$より, $2^n\leq n^{d(n)}<2^{8d(n)}$で, $n<8d(n)$となる.
互いに素な整数$(x,y)$に対し, $\dfrac{xy}{d(xy)}=\dfrac{x}{d(x)}\times\dfrac{y}{d(y)}$である. すなわち関数$\dfrac{x}{d(x)}$は乗法的関数である.
$n$が素べきで, $\dfrac{n}{d(n)}<8$となるものを列挙すると, 以下のようになる.
| $ n $ | $ \dfrac{n}{d(n)} $ | $ n $ | $ \dfrac{n}{d(n)} $ |
|---|---|---|---|
| $2^1$ | $1$ | $3^2$ | $3$ |
| $2^2$ | $\dfrac{4}{3}$ | $3^3$ | $\dfrac{27}{4}$ |
| $2^3$ | $2$ | $5^1$ | $\dfrac{5}{2}$ |
| $2^4$ | $\dfrac{16}{5}$ | $7^1$ | $\dfrac{7}{2}$ |
| $2^5$ | $\dfrac{16}{3}$ | $11^1$ | $\dfrac{11}{2}$ |
| $3^1$ | $\dfrac{3}{2}$ | $13^1$ | $\dfrac{13}{2}$ |
よって, $\dfrac{n}{d(n)}<8$となる$2$以上の整数$n$は以下のようになる.
$$2\leq n\leq16, n=18,20,21,22,24,26,27,28,30,32,36,40,42,44,45,48,54,56,60,72,84,90,120$$
これらのうち$2^n\leq n^{d(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< t\leq2$なる実数$t$で, $t^n\leq n^{d(n)}$を満たす$2$以上の整数$n$を考え, $p$を素数とすると, $p$が$n$の素因数になり得ることと, $t^p<4p^2$となることは同値である. (上の議論を利用して証明できる. )
それでは, 本題に戻り, Zsigmondyの定理を使わずに$(a,b)$が上で示した$13$通りであることを示す.
$a-b=c$とする.
$c>1$のときを考える.
$2^c-1$の素因数$p$と$\bmod p$における原始根$r$をとる. 二項定理より, $(p+1)^{p-1}\not\equiv 1\pmod{p^2}$.
よって, $r^{p-1}\not\equiv1\pmod{p^2}$または$(r(p+1))^{p-1}\not\equiv1\pmod{p^2}$.
ゆえに, $v_p(n)$を$n$が$p$で割り切れる回数とすると, $\bmod p$における位数が$p-1$となる整数$s$で, $v_p(s^{p-1}-1)=1$となるものが存在する.
$n=s$とすると, $s^c-1$が$p$の倍数となる必要があるため, $c$は$p-1$の倍数である.
LTEの補題より, 以下が成立する.
$v_p(s^c-1)=v_p(s^{p-1}-1)+v_p\left(\dfrac{c}{p-1}\right)=v_p\left(\dfrac{c}{p-1}\right)+1$
よって, $p^{v_p(s^{c}-1)}\leq\dfrac{pc}{p-1}$.
$d(n)$を$n$の正の約数の個数とすると, $p-1$が$c$の約数であるため, $2^c-1$の素因数の個数$k$は高々$d(c)-1$である. ($2^c-1$は明らかに$2$を素因数として持たないため. ) また, それらの素因数はいずれも$c+1$以下である.
$2^c-1$の素因数を小さい順に$p_1, p_2, \cdots, p_k$とおくと, 以下が成立する.
$$2^c-1=p_1^{v_{p_1}(s^c-1)}p_2^{v_{p_2}(s^c-1)}\cdots p_k^{v_{p_k}(s^c-1)}\leq c^k\times\dfrac{p_1}{p_1-1}\times\dfrac{p_2}{p_2-1}\times\cdots\times\dfrac{p_k}{p_k-1}\leq c^{d(c-1)}\times \dfrac{3\times\cdots\times(c+1)}{2\times\cdots\times c}< c^{d(c)}$$
よって, $2^c\leq c^{d(c)}$
補題より, $c=1$の場合も含めて$c$は高々$23$通りであり, $7,17,31,73,127,151,257$はそれぞれ$2^3-1,2^8-1,2^5-1,2^9-1,2^7-1,2^{15}-1,2^{16}-1$の素因数であるため, $c=1,2,4,6,12$に限られる.
$c=1$のときも含めて$n=3$のときを考えると, $3^c-1$が$2^b$の倍数となる必要があるため, 各$c$に対して$b$は有限個に絞られるため, 問題の条件を満たす$(a,b)$は上で示した$13$通りである.
おわりに
計算ミス等の確認をあまりしていないので, 間違いが結構あるかもしれません. 間違いらしき点を見つけたらコメントで優しく教えてもらえると助かります.
