2017-02-27

突然57個の素数を要求されたときの対処法

整数整数-133 整数-6729 整数-158379 整数-1720294 整数-6823316 整数-1705829 整数-1313701 整数-991127 整数-729173 整数-519643 整数-355049 整数-228581 整数-134077 整数-65993 整数-19373 整数-10181 整数-26539 整数-33073 整数-32687 整数-27847 整数-20611 整数-12659 整数-5323 整数-383 整数-3733 整数-4259 整数-1721 整数-3923 整数-12547 整数-23887 整数-37571 整数-53149 整数-70123 整数-87977 整数-106207 整数-124351 整数-142019 整数-158923 整数-174907 整数-189977 整数-204331 整数-218389 整数-232823 整数-248587 整数-266947 整数-289511 整数-318259 整数-355573 整数-404267 整数-467617 整数-549391 整数-653879 整数-785923 整数-950947 整数-1154987 整数-1404721 整数-1707499 整数-2071373 整数-2505127 整数-3018307 整数-3621251 整数-4325119

街中で突然怖い人に

「今すぐ57個素数を教えないと殺す。一桁や二桁の小さいものは駄目だ。」

と言われたとしましょう。

要求される個数が24個であれば $357686312646216567629137$ を覚えていれば十分でした*1。

しかし、今回の怖い人はグロタンディーク素数*2が好きなのか、要求してくる素数の数が57個と多めです。しかも、一桁や二桁の小さい素数では満足してくれそうにありません。

そんなときにオススメしたいのが Shyam Sunder Gupta多項式です！！

$\displaystyle f(n)=\frac{n^5 - 133n^4 + 6729n^3 - 158379n^2 + 1720294n - 6823316}{4}$

この多項式さえ覚えておけば、あとは $n$ に $0$ から $56$ を代入していくだけの簡単なお仕事。出てくる値の絶対値を答えれば殺される心配はありません！

$\begin{align} &f(0)=-1705829\\ &f(1)=-1313701 \\ &f(2)=-991127 \\ &f(3)=-729173 \\ &f(4)=-519643 \\ &f(5)=-355049 \\ &f(6)=-228581 \\ &f(7)=-134077 \\ &f(8)=-65993 \\ &f(9)=-19373 \\ &f(10)=10181 \\ &f(11)=26539 \\ &f(12)=33073 \\ &f(13)=32687 \\ &f(14)=27847 \\ &f(15)=20611 \\ &f(16)=12659 \\ &f(17)=5323 \\ &f(18)=-383 \\ &f(19)=-3733 \\ &f(20)=-4259 \\ &f(21)=-1721 \\ &f(22)=3923 \\ &f(23)=12547 \\ &f(24)=23887 \\ &f(25)=37571 \\ &f(26)=53149 \\ &f(27)=70123 \\ &f(28)=87977 \\ &f(29)=106207 \\ &f(30)=124351 \\ &f(31)=142019 \\ &f(32)=158923 \\ &f(33)=174907 \\ &f(34)=189977 \\ &f(35)=204331 \\ &f(36)=218389 \\ &f(37)=232823 \\ &f(38)=248587 \\ &f(39)=266947 \\ &f(40)=289511 \\ &f(41)=318259 \\ &f(42)=355573 \\ &f(43)=404267 \\ &f(44)=467617 \\ &f(45)=549391 \\ &f(46)=653879 \\ &f(47)=785923 \\ &f(48)=950947 \\ &f(49)=1154987 \\ &f(50)=1404721 \\ &f(51)=1707499 \\ &f(52)=2071373 \\ &f(53)=2505127 \\ &f(54)=3018307 \\ &f(55)=3621251 \\ &f(56)=4325119 \end{align}$

*1:integers.hatenablog.com

*2:integers.hatenablog.com

2017-02-25

フィボナッチ数とp進数

定理解説

$F_n$ を $n$ 番目のFibonacci数とします：

integers.hatenablog.com

$\mathcal{F}:=\{F_n \mid n \in \mathbb{Z}_{>0}\}$ に対して、二つのFibonacci数の商からなる集合 $Q({\mathcal F})$ を

$\displaystyle Q(\mathcal{F}) := \left\{ \left. \frac{F_n}{F_m} \right| n, m \in \mathbb{Z}_{>0} \right\}$

と定義します。黄金比を $\displaystyle \phi := \frac{1+\sqrt{5}}{2}$ とするとき、Binetの公式

$\displaystyle F_n = \frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}$

より $Q(\mathcal{F})$ の元は $\mathbb{R}$ において $\phi$ の整数乗の近くにしか分布しません。一方、次が成り立ちます：

定理*1 任意の素数 $p$ に対して、 $Q(\mathcal{F})$ は $p$ 進数体 $\mathbb{Q}_p$ で稠密である。

この記事ではこの定理の証明を解説します。

準備

補題１ $m \mid n \Longrightarrow F_m \mid F_n$ .

証明. これは30：Lucas数列と原始的約数 - INTEGERSに書いてある一般的な命題をFibonacci数に適用したもの。 Q.E.D.

補題２ $m$ を正の整数とし、 $n_1, n_2$ を整数とする(ここでは $0$ 以下の整数も許す)。このとき、 $F_{n_1}$ と $F_{n_2}$ がともに $m$ で割り切れるならば、 $F_{n_1+n_2}$ も $m$ で割り切れる。

証明. 整数 $n_1, n_2$ に対して $F_{n_1+n_2}=F_{n_2-1}F_{n_1}+F_{n_2}F_{n_1+1}$ が成り立つ(例えば、Binetの公式で右辺を計算すると $(L_{n_1+n_2-1}+L_{n_1+n_2})/5$ に等しいことがわかる。 $L_{n-1}+L_n=5F_n$ が成り立つことは数学的帰納法で示せる*2 )。よって、 $F_{n_1}$ と $F_{n_2}$ が $m$ で割り切れるならば $F_{n_1+n_2}$ も割り切れる。 Q.E.D.

補題２と $F_n=(-1)^{n-1}F_{-n}$ より

$A_n:=\{n \in \mathbb{Z} \colon \ m \mid F_n\}$

は $\mathbb{Z}$ のイデアルをなすことがわかる。 $A_n$ を生成する正の整数を $z(m)$ で表す。冒頭のフィボナッチ数の記事で述べたように $F_n$ が偶数であるための必要十分条件は $n$ が $3$ の倍数であることだったので、 $z(2)=3$ がわかる。

補題３ (Lucas) $n, m, k$ を正整数とする。このとき、

$\displaystyle (m+n)^k=m^k+n^k-\sum_{j=1}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j}$

が成り立つ*3。

証明. $k$ に関する数学的帰納法で証明する。 $k=1, 2$ の場合は成り立っている。 $k$ 以下で成り立つと仮定して $k+1$ の場合にも成り立つことを証明しよう。まず、 $k$ のときに成立するという仮定より

$\begin{align} (m+n)^{k+1} &= (m+n)(m+n)^k \\ &=(m+n)(m^k+n^k)-\sum_{j=1}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j+1}\end{align}$

が成り立つ。次に、 $k-1$ の場合に成立するという仮定より

$\displaystyle mn(m^{k-1}+n^{k-1})=mn(m+n)^{k-1}+\sum_{j=1}^{\left[\frac{k-1}{2}\right]}(-1)^j\frac{k-1}{j}\binom{k-j-2}{j-1}(mn)^{j+1}(m+n)^{k-2j-1}.$

これを最初の式に代入することにより

$\begin{align}(m+n)^{k+1}&=m^{k+1}+n^{k+1}+mn(m+n)^{k-1}\\ &\quad +\sum_{j=1}^{\left[ \frac{k-1}{2}\right]}(-1)^j\frac{k-1}{j}\binom{k-j-2}{j-1}(mn)^{j+1}(m+n)^{k-2j-1}\\ &\quad -\sum_{j=1}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j+1}\end{align}$

を得る。最後の和は

$\begin{align}&\quad -\sum_{j=1}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j+1} \\ &= kmn(n+n)^{k-1} -\sum_{j=2}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j+1} \\ &= kmn(m+n)^{k-1}+\sum_{j=1}^{\left[ \frac{k-1}{2}\right]}(-1)^j\frac{k}{j+1}\binom{k-j-2}{j}(mn)^{j+1}(m+n)^{k-2j-1}\end{align}$

と変形できるので*4、

$\begin{align}(m+n)^{k+1} &= m^{k+1}+n^{k+1}+(k+1)mn(m+n)^{k-1}\\ & \quad +\sum_{j=1}^{\left[ \frac{k-1}{2}\right]}(-1)^j\left\{ \frac{k-1}{j}\binom{k-j-2}{j-1}+\frac{k}{j+1}\binom{k-j-2}{j}\right\}(mn)^{j+1}(m+n)^{k-2j-1} \\ &=m^{k+1}+n^{k+1}+(k+1)mn(m+n)^{k-1} \\ &\quad +\sum_{j=1}^{\left[\frac{k-1}{2}\right]}(-1)^j\frac{k+1}{j+1}\binom{k-j-1}{j}(mn)^{j+1}(m+n)^{k-2j-1} \\ &= m^{k+1}+n^{k+1}-\sum_{j=1}^{\left[\frac{k+1}{2}\right]}(-1)^j\frac{k+1}{j}\binom{k-j}{j-1}(mn)^j(m+n)^{k-2j+1}\end{align}$

となって、 $k+1$ のときも成立することが示された。 Q.E.D.

補題４ $p$ を奇素数とする。このとき、任意の正の整数 $k, i$ に対して

$\mathrm{ord}_p(F_{kz(p)p^i}) = \mathrm{ord}_p(F_{kz(p)})+i$

が成り立つ。

証明. 補題３において $m\mapsto \phi^{kz(p)}, n\mapsto-(-\phi)^{-kz(p)}, k\mapsto p^i$ とすると、

$\displaystyle F_{kz(p)p^i}=\sqrt{5}^{p^i-1}F_{kz(p)}^{p^i}+\sum_{j=1}^{\frac{p^i-1}{2}}(-1)^{jkz(p)}\sqrt{5}^{p^i-2j-1}\frac{p^i}{j}\binom{p^i-j-1}{j-1}F_{kz(p)}^{p^i-2j}$

が得られる。右辺について、和の $j=\frac{p^i-1}{2}$ のときの項が $p$ -orderが最も小さく、その項は符号を無視すれば $p^iF_{kz(p)}$ であり、 $p$ -orderは $\mathrm{ord}_p(F_{kz(p)})+i$ である。 $j < \frac{p^i-1}{2}$ のときに $1/j$ の寄与が気になるのでチェックしておく。

$\begin{align} &\quad \mathrm{ord}_p\left( (-1)^{jkz(p)}\sqrt{5}^{p^i-2j-1}\frac{p^i}{j}\binom{p^i-j-1}{j-1}F_{kz(p)}^{p^i-2j} \right) \\ &\geq \mathrm{ord}_p\left( \frac{p^i}{j} \right) + \mathrm{ord}_p(F_{kz(p)}^{p^i-2j}) = i-\mathrm{ord}_p(j)+(p^i-2j)\mathrm{ord}_p(F_{kz(p)})\end{align}$

なので、

$i-\mathrm{ord}_p(j)+(p^i-2j)\mathrm{ord}_p(F_{kz(p)}) > \mathrm{ord}_p(F_{kz(p)})+i$

すなわち

$(p^i-2j-1)\mathrm{ord}_p(F_{kz(p)}) > \mathrm{ord}_p(j)$

を示せばよい。今、 $\mathrm{ord}_p(F_{kz(p)}) \geq 1$ であることに注意する。 $1 \leq \mathrm{ord}_p(j)=t \leq i-1$ であったと仮定する( $t=0$ のときは自明)。このとき、 $j < \frac{p^i-1}{2}$ であることから $j \leq \frac{p^i-p^t}{2}$ であることがわかる。よって、

$p^i-2j-1 \geq p^t-1 > t$

であり、示すべきことは全て示された。 Q.E.D.

補題５ 任意の正の整数 $i$ に対して

$\mathrm{ord}_2(F_{3\cdot 2^i}) = i+2$

が成り立つ。

証明. $i$ に関する数学的帰納法で証明する。 $\mathrm{ord}_2(F_6)=\mathrm{ord}_2(8)=3$ なので $i=1$ のときは成立する。 $\mathrm{ord}_2(F_{3\cdot 2^i})=i+2$ を仮定する。

144：フィボナッチ平方数 - INTEGERSの補題１とリュカ数の記事で紹介した $L_{2n}=L_n^2+(-1)^{n-1}\cdot 2$ より、

$L_{2n}=(-1)^n\cdot 2+5F_n^2$

が成り立つ。また、 $F_3=2$ なので、補題１より $F_{3\cdot 2^{i-1}}$ は偶数である。よって、

$\mathrm{ord}_2(L_{3\cdot 2^i})=\mathrm{ord}_2(L_{2(3\cdot 2^{i-1})}) = \mathrm{ord}_2((-1)^{3\cdot 2^{i-1}}\cdot 2+5F_{3\cdot 2^{i-1}}^2) = 1.$

$144$ の記事の補題１より $F_{2n}=F_nL_n$ なので、

$\mathrm{ord}_2(F_{3\cdot 2^{i+1}}) = \mathrm{ord}_2(F_{2(3\cdot 2^i)}) = \mathrm{ord}_2(F_{3\cdot 2^i}) + \mathrm{ord}_2(L_{3\cdot 2^i}) = i+3$

となって、 $i+1$ のときも成立することが示された。 Q.E.D.

補題６ 任意の素数 $p$ に対して、 $\{p^{-r}n \mid n, r \in \mathbb{Z}_{\geq 0}\}$ は $\mathbb{Q}_p$ で稠密である。

証明. $p$ 進数 $x$ を任意にとる。 $x$ の $p$ 進展開が整数 $k$ を用いて

$\displaystyle x=p^k\sum_{j=0}^{\infty}a_jp^j$

と書けているとする( $a_j$ は $0$ から $p-1$ の整数)。 $N$ を $N\geq k+1$ を満たすような整数とし、 $\displaystyle n:=\sum_{j=0}^{N-k-1}a_jp^j \in \mathbb{Z}$ とする。このとき、

$\displaystyle \mathrm{ord}_p(x-p^kn) = \mathrm{ord}_p\left( p^k\sum_{j=N-k}^{\infty}a_jp^j \right) = k +\mathrm{ord}_p\left( \sum_{j=N-k}^{\infty}a_jp^j \right) \geq k+(N-k) = N$

となるので、 $x$ の非常に近いところに $p^kn$ はいる。 Q.E.D.

補題７ 任意の素数 $p$ および正整数 $i$ に対して

$\phi^{4z(p)p^{2i}} \equiv 1, \quad (-\phi)^{-4z(p)p^{2i}} \equiv 1 \pmod{p^{2i}\mathcal{O}_{K}}$

が成立する。ここで、 $\mathcal{O}_{K}$ は $K:=\mathbb{Q}(\sqrt{5})$ の整数環 $\mathbb{Z}[\phi]$ 。

証明. $\phi^{4z(p)p^{2i}} \equiv 1$ を示せば十分。 $p$ が奇素数のときは補題４より、 $p=2$ の場合は補題５より $p^{2i} \mid F_{z(p)p^{2i}}$ なので、

$\phi^{z(p)p^{2i}}-(-\phi)^{-z(p)p^{2i}} = \sqrt{5}F_{z(p)p^{2i}} \equiv 0 \pmod{p^{2i}\mathcal{O}_K}.$

よって、 $\phi^{z(p)p^{2i}}\equiv (-\phi)^{-z(p)p^{2i}} \pmod{p^{2i}\mathcal{O}_K}$ であり、これを変形すれば所望の合同式となる。 Q.E.D.

補題８ 任意の素数 $p$ と正整数 $k$ 、非負整数 $r$ に対して

$\mathrm{ord}_p(F_{4z(p)p^{2(k+2r)}})=\mathrm{ord}_p(F_{4z(p)p^{2(k+r)}})+2r$

が成り立つ。

証明. $p$ が奇素数の場合は補題４、 $p=2$ の場合は補題５より従う。 Q.E.D.

定理の証明

$n, k$ を任意の正整数、 $r$ を任意の非負整数とする。正整数 $m$ に対して成り立つ恒等式

$x^m-y^m=(x-y)(x^{m-1}+x^{m-2}y+\cdots + xy^{m-2}+y^{m-1})$

に $x=\phi^{4z(p)p^{2i}}, y=(-\phi)^{-4z(p)p^{2i}}$ を代入することによって( $i$ は正整数)、

$\begin{align} \frac{F_{4z(p)p^{2i}m}}{F_{4z(p)p^{2i}}} &= \frac{\phi^{4z(p)p^{2i}m}-(-\phi)^{-4z(p)p^{2i}m}}{\phi^{4z(p)p^{2i}}-(-\phi)^{-4z(p)p^{2i}}} \\ &=(\phi^{4z(p)p^{2i}})^{m-1}+\cdots + ((-\phi)^{-4z(p)p^{2i}})^{m-1} \\ &\equiv m \pmod{p^{2i}}\end{align}$

ここで、左辺の分数が補題１によって有理整数であることと補題７を用いたことに注意。また、補題８より $p$ と素な正整数 $l$ が存在して、

$\displaystyle \frac{F_{4z(p)p^{2(k+2r)}}}{F_{4z(p)p^{2(k+r)}}} = p^{2r}l$

が成り立つ。先ほどの式で $m=p^rnl, i=k+r$ とすると、

$\displaystyle p^{2r}l\frac{F_{4z(p)p^{2(k+r)}p^rnl}}{F_{4z(p)p^{2(k+2r)}}} = \frac{F_{4z(p)p^{2(k+r)}p^rnl}}{F_{4z(p)p^{2(k+r)}}} \equiv p^rnl \pmod{p^{k+r}}$

となり、 $l$ が $p$ と互いに素であることから

$\displaystyle p^{2r}\frac{F_{4z(p)p^{2(k+r)}p^rnl}}{F_{4z(p)p^{2(k+2r)}}} \equiv p^rn \pmod{p^{k+r}}$

を得る。従って、

$\displaystyle \mathrm{ord}_p \left( \frac{F_{4z(p)p^{2(k+r)}p^rnl}}{F_{4z(p)p^{2(k+2r)}}}-p^{-r}n \right) \geq k-r$

が示された。 $k, r, n$ は任意だったので、任意の $p^{-r}n$ という形の有理数にはいくらでも近いところに $Q(\mathcal{F})$ の元がいることがわかった(ただし、今までの議論では $n \neq 0$ )。 $0$ のいくらでも近いところにも $Q(\mathcal{F})$ の元がいることは補題４、５よりわかる。よって、補題６より証明が完了する。 Q.E.D.

*1:S. R. Garcia, F. Luca, Quotients of Fibonacci numbers, Amer. Math. Monthly, Vol. 123, Mp. 10, (2016), pp. 1039-1044.

*2: $L_n$ はLucas数: integers.hatenablog.com

*3: $\displaystyle \frac{k}{j}\binom{k-j-1}{j-1}=\binom{k-j}{j}+\binom{k-j-1}{j-1}$ は整数。

*4: $n < k$ なら $\displaystyle \binom{n}{k}=0$ とする。

2017-02-21

パワフル数に関するMcDanielの定理の証明

定理解説

パワフル数に関する記事

integers.hatenablog.com

で紹介したMcDanielの定理

定理 (McDaniel 1982) $0$ でない任意の整数に対して、その数を二つの互いに素なパワフル数で表す表し方が無数に存在する。

の証明を紹介します。

$D$ を平方数でないような整数とし、正整数 $n$ に対する方程式

$x^2-Dy^2=n$ − ①

およびPell方程式

$x^2-Dy^2=1$ − ②

を考える。解といったら、整数解を表すものとする。

補題１ $(p, q)$ が①の解であり、 $(u, v)$ が②の解であるとする。このとき、 $(pu+Dqv, pv+qu)$ は①の解である。

証明. $(pu+Dqv)^2-D(pv+qu)^2=(p^2-Dq^2)(u^2-Dv^2)=n.$ Q.E.D.

$A:=\left( \begin{smallmatrix} p & Dq \\ q & p \end{smallmatrix}\right)$ とおくと、 $\det A=n \neq 0$ であり、 $\binom{pu+Dqv}{pv+qu}=A\binom{u}{v}$ である。このことと、Pell方程式が無数に解を持つことから、①は一つ解があれば無数に解を持つことがわかる。

定義 $(p, q)$ が①の解であり、 $(u, v)$ が②の解であるとする。このとき、 $(pu+Dqv, pv+qu)$ が①のMcDaniel型の解であるとは、

$u$ が奇数
$v$ が偶数
$D \mid pv+qu$

であるときにいう。

命題１ $(p, q)$ を①の解とし、 $(x_0, y_0)$ を $x^2-Dy^2=\pm 1$ の解とする。ただし、 $y_0 \neq 0$ 。また、 $d:=(2py_0, D)$ とおく(最大公約数)。このとき、 $d \mid q$ ならば①はMcDaniel型の解を無数に持つ。

証明. $x_1:=x_0^2+Dy_0^2, y_1:=2x_0y_0$ とする。このとき、

$x_1^2-Dy_1^2=(x_0^2-Dy_0^2)^2=1$

なので、 $(x_1, y_1)$ は②の解である。 $y_1$ は偶数であるから、 $x_1$ は奇数である。

$x_j+y_j\sqrt{D}=(x_1+y_1\sqrt{D})^j, \quad j=1, 2, \dots$

で定まる $(x_j, y_j)$ は②の解であり、 $y_1\neq 0$ であるからこれらは全て相異なる解である。具体的に

$\displaystyle x_j=x_1^j+\sum_{\substack{k=2 \\ k: \text{偶数}}}^j\binom{j}{k}x_1^{j-k}y_1^kD^{\frac{k}{2}},$

$\displaystyle y_j=jx_1^{j-1}y_1+\sum_{\substack{k=3 \\ k: \text{奇数}}}^j\binom{j}{k}x_1^{j-k}y_1^kD^{\frac{k-1}{2}}$

と書ける。これより、 $x_j$ が奇数で $y_j$ が偶数であることがわかる。 $X_j:=px_j+Dqy_j, Y_j:=py_j+qx_j$ とおけば補題１より $(X_j, Y_j)$ は①の解であるが、これがMcDaniel型であるような $j$ が無数に存在することを示す。

$Y_j= py_j+qx_j\equiv pjx_1^{j-1}y_1+qx_1^j= x_1^{j-1}(pjy_1+qx_1) \pmod{D}$

であり、

$pjy_1+qx_1=2pjx_0y_0+q(x_0^2+Dy_0^2) \equiv 2pjx_0y_0+qx_0^2 = x_0((2py_0)j+qx_0) \pmod{D}$

である。 $d=(2py_0, D) \mid q$ という仮定より、方程式 $(2py_0)s+Dt=-qx_0$ は整数解 $(s, t)$ を無数に持つ。 $s$ 及び $t$ はそれぞれある合同類で定まるので、 $(2py_0)j+qx_0$ が $D$ で割り切れるような $j > 0$ が無数に存在することがわかる。つまり、 $D \mid Y_j$ となるような $j$ が無数に存在し、そのような $j$ について $(X_j, Y_j)$ はMcDaniel型である。 Q.E.D.

補題２ $(u, v)$ を②の解とする。このとき、 $(p, q)=1$ (すなわち、 $p, q$ が互いに素な整数)であるならば、 $(pu+Dqv, pv+qu)=1$ 。

証明. $d:=(pu+Dqv, pv+qu)$ とする。このとき、

$d \mid u(pv+qu)-v(pu+Dqv) = q(u^2-Dv^2)=q$

かつ

$d \mid u(pu+Dqv)-vD(pv+qu) = p(u^2-Dv^2)=p$

なので、 $d=1$ 。 Q.E.D.

命題２ $n$ を $n \equiv 0, \pm 1 \pmod{4}$ であるような正整数とする。このとき、或る平方数でないような奇数 $D$ が存在して、①は互いに素なMcDaniel型の解を無数に持つ。

証明. $n=4k-1, k \geq 1$ の場合

$D:=16k^2-8k+5$
$p:=8k^2-6k+2$
$q:=2k-1$
$x_0:=32k^3-24k^2+12k-2$
$y_0:=8k^2-4k+1$

とする。このとき、 $D$ は平方数ではない奇数で、 $p^2-Dq^2=n, x_0^2-Dy_0^2=-1$ が成り立つ。 $d_0:=(p, D)$ とすると

$d_0 \mid 4(D-2p)-((D-2p)^2-D)=8$

で、 $D$ は奇数なので $d_0=1$ 。 $d_1:=(y_0, D)$ とすると、 $d_1 \mid D-2y_0=3$ 及び $D \not \equiv 0 \pmod{3}$ より $d_1=1$ 。よって、命題１から①は無数にMcDaniel型の解を持つことがわかるが、 $d_2:=(p, q)$ とすると $d_2 \mid (4k-1)q-p=-1$ より $d_2=1$ であるから、補題２よりそれらの解は全て互いに素である。

$n=1$ の場合

$D=3$
$p=2$
$q=1$
$x_0=2$
$y_0=1$

とする。このとき、 $p^2-Dq^2=1, x_0^2-Dy_0^2=1$ が成り立ち、 $(py_0, D)=(p, q)=1$ 。よって、命題１及び補題２より①は互いに素なMcDaniel型の解を無数に持つ。

$n=5$ の場合

$D=11$
$p=4$
$q=1$
$x_0=10$
$y_0=3$

とする。このとき、 $p^2-Dq^2=5, x_0^2-Dy_0^2=1$ が成り立ち、 $(py_0, D)=(p, q)=1$ 。よって、命題１及び補題２より①は互いに素なMcDaniel型の解を無数に持つ。

$n=4k+1, k \geq 2$ の場合

$D:=4k^2-4k-1$
$p:=2k$
$q:=1$
$x_0:=4k^2-4k$
$y_0:=2k-1$

とする。このとき、 $D$ は平方数ではない奇数で、 $p^2-Dq^2=n, x_0^2-Dy_0^2=1$ が成り立つ。 $d_0:=(p, D)$ とすると、 $d_0 \mid p^2-2p-D=1$ 。 $(y_0, D)=(p, q)=1$ は自明。よって、命題１及び補題２より①は互いに素なMcDaniel型の解を無数に持つ。

$n=4k, k \geq 1$ の場合

$D:=4k^2+1$
$p:=2k+1$
$q:=1$
$x_0:=2k$
$y_0:=1$

とする。このとき、 $D$ は平方数ではない奇数で、 $p^2-Dq^2=n, x_0^2-Dy_0^2=-1$ が成り立つ。 $d:=(py_0, D)$ とすると $d \mid D-(2k-1)py_0=2$ なので、 $d=1$ 。 $(p, q)=1$ は自明。よって、命題１及び補題２より①は互いに素なMcDaniel型の解を無数に持つ。 Q.E.D.

定理の証明

正の整数 $n$ に対して互いに素なパワフル数の差として表す表し方が無数に存在することを示せば十分である。

$n \not \equiv 2 \pmod{4}$ のとき
命題２によって無数に存在する①の互いに素なMcDaniel型の解を $(X_j, Y_j)$ とする。このとき、 $m_1:=X_j^2, m_2:=DY_j^2$ とすれば $n=m_1-m_2$ であり、 $D \mid Y_j$ であるから $m_1$ と $m_2$ は互いに素なパワフル数である。つまり、 $n$ を互いに素なパワフル数の差として表す表し方が無数に存在する。

$n \equiv 2 \pmod{4}$ のとき
$n=2+4t$ とおく。 $n^2/4=4(t^2+t)+1$ である。命題２の証明における $n=1, n=4k+1, k \geq 2$ の場合において、 $n \mapsto n^2/4$ として考える。すなわち、

$\displaystyle D:=\begin{cases} 3 & t=0 \\ 4(t^2+t)^2-4(t^2+t)-1 & t \geq 1 \end{cases}$

とすると、方程式 $x^2-Dy^2=\frac{n^2}{4}$ は互いに素なMcDaniel型の解を無数に持つ。そのような解 $(X_j, Y_j)$ に対して、 $m_1:=X_j+\frac{n}{2}, m_2:=X_j-\frac{n}{2}$ とおく。このとき、 $n=m_1-m_2$ が成り立つので、 $m_1, m_2$ が互いに素なパワフル数であることを示せばよい。

解の構成 $X_j=px_j+Dqy_j$ より $X_j$ は偶数なので、 $m_1, m_2$ は奇数である。 $d:=(m_1, m_2)$ とすると、 $d \mid m_1+m_2=2X_j$ 及び $d \mid m_1-m_2=n$ 。 $(X_j, Y_j)=1$ であることと、 $X_j^2-DY_j^2=n^2/4$ より、 $(X_j, n)=1$ 。以上より、 $(m_1, m_2)=1$ がわかった( $D \mid Y_j$ に注意)。

また、

$\displaystyle m_1m_2=\left( X_j+\frac{n}{2} \right) \left( X_j-\frac{n}{2} \right) = X_j^2-\frac{n^2}{4} = DY_j^2$

なので、 $D \mid Y_j^2$ であることから $m_1m_2$ はパワフル数。このことと、 $m_1, m_2$ が互いに素であることから $m_1, m_2$ はそれぞれパワフル数であることがわかる。 Q.E.D.

具体例

冒頭にあげた過去の記事において紹介した

$6=5^4\times 7^3-463^2$

という表示がこの証明法から導出できることを確認しましょう。まず、 $9$ に対してこの証明法による表示を与えることから始めます(自明な表示は $9=5^2-4^2$ でした)。

$n=9=4\times 2+1$ に対しては、 $D=7, p=4, q=1, x_0=8, y_0=3$ というデータを取れる。このとき、 $x_1=x_0^2+Dy_0^2=127, y_1=2x_0y_0=48$ 。一次方程式 $(2py_0)s+Dt=-qx_0$ はこの場合は $24s+7t=-8$ となっており、 $s$ の一般解は $2\bmod{7}$ 。よって、 $X_2=px_2+Dqy_2, Y_2=py_2+qx_2$ が一番簡単な場合となる。 $(127+48\sqrt{7})^2=32257+12192\sqrt{7}$ より $x_2=32257, y_2=12192$ なので、 $X_2=214372, Y_2=81025$ を得る。こうして、