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$ を得る。こうして、