インテジャーズ

INTEGERS

数、特に整数に関する記事。

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

パワフル数に関する記事

integers.hatenablog.com

で紹介したMcDanielの定理

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

の証明を紹介します。

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

x^2-Dy^2=n − ①

およびPell方程式

x^2-Dy^2=1 − ②

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

補題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

であるときにいう。

命題1 (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とおけば補題1より(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_0Dで割り切れるようなj > 0が無数に存在することがわかる。つまり、D \mid Y_jとなるようなjが無数に存在し、そのようなjについて(X_j, Y_j)はMcDaniel型である。 Q.E.D.

補題2 (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=1Q.E.D.

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

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。よって、命題1及び補題2より①は互いに素な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。よって、命題1及び補題2より①は互いに素な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は自明。よって、命題1及び補題2より①は互いに素な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は自明。よって、命題1及び補題2より①は互いに素なMcDaniel型の解を無数に持つ。 Q.E.D.

定理の証明

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

n \not \equiv 2 \pmod{4}のとき
命題2によって無数に存在する①の互いに素な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_1m_2は互いに素なパワフル数である。つまり、nを互いに素なパワフル数の差として表す表し方が無数に存在する。

n \equiv 2 \pmod{4}のとき
n=2+4tとおく。n^2/4=4(t^2+t)+1である。命題2の証明における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を得る。こうして、

m_1=X_2^2=2^4\times 53593^2, \quad m_2=DY_2^2=5^4\times 7^3\times 463^2

に対して、9=m_1-m_2が成り立つ。

n=6の場合はn^2/4=9なので、上記X_2に対して

m_1=X_2+3=214375=5^4\times 7^3, \quad m_2=X_2-3=214369=463^3

を考えると、6=m_1-m_2を得る。


Golombの計算では6, 14, 34, 42の表示が?となっていましたが、n=14にMcDanielの証明法による表示を具体的に与えるのは大変です。