インテジャーズ

INTEGERS

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

芸術家の作品

2, 5, 13の三つ組はどの二つをとっても掛け合わせて1引けば平方数となります*1

\begin{equation}\begin{split}&2\times 5-1=3^2\\ &2\times 13-1=5^2 \\ &5\times 13-1=8^2\end{split}\end{equation}


これを四つ組には延長できないことを証明させるのが1986年の国際数学オリンピック第一問です。

証明. 自然数dが存在して、2d-1, 5d-1, 13d-1が全て平方数になったと仮定する。法16における平方剰余は0, 1, 4, 9であることに注意する。2d-1\equiv 0, 4\pmod{16}なる自然数dは存在しないので、2d-1 \equiv 1, 9\pmod{16}でなければならない。そうなるのは、d \equiv 1, 5, 9, 13\pmod{16}のときである。しかしながら、d \equiv 5, 9\pmod{16}ならば5d-1 \equiv 8, 12 \pmod{16}は平方非剰余、d \equiv 1, 13\pmod{16}ならば13d-1 \equiv 12, 8\pmod{16}は平方非剰余となる。矛盾。 Q.E.D.

さっき、少し計算してみたら2, 41, 61の3つ組も同じ性質を満たすことがわかりました:

\begin{equation}\begin{split}&2\times 41-1=9^2 \\ &2\times 61-1=11^2 \\ &41\times 61-1=50^2\end{split}\end{equation}


これも四つ組には延長できません。どなたか四つ組の例を見つけてくださるプログラマがおられると嬉しいです。

追記1

三つ組はサーチすればたくさん見つかるようです。

100以下の範囲では

\begin{align}&[1, 2, 5]\\
&[1, 5, 10]\\
&[1, 5, 65]\\
&[1, 10, 17]\\
&[1, 17, 26]\\
&[1, 26, 37]\\
&[1, 37, 50]\\
&[1, 50, 65]\\
&[1, 65, 82]\\
&[2, 5, 13]\\
&[2, 13, 25]\\
&[2, 25, 41]\\
&[2, 41, 61]\\
&[2, 61, 85]\\
&[5, 10, 29]\\
&[5, 13, 34]\\
&[5, 29, 58]\\
&[5, 34, 65]\\
&[5, 58, 97]\\
&[10, 17, 53]\\
&[10, 29, 73]\\
&[13, 25, 74]\\
&[13, 34, 89]\\
&[17, 26, 85]\end{align}

が見つかります(丸蔵次郎(マルゾー)様(id:maruzo-jiro)に教えて頂きました)。

何故、私がこの中で[ 2, 41, 61] を手計算で発見したかと言うと、全部素数のケースだからですw

追記2

四つ組は存在しないと予想されているようです。
integers.hatenablog.com

追記3

三つ組は無数に存在します。例えば、二つ組[ 1, 2] を延長した[ 1, 2, d] が三つ組になるには

\begin{equation}\begin{split}&d-1=y^2\\ &2d-1=x^2\end{split}\end{equation}

なる自然数x, yが存在すればよいですが、それはPell方程式

x^2-2y^2=1

が無数に自然数解(x, y)を持つことと同値です。Pell方程式は実際に無数に自然数解をもつので、[ 1, 2] の三つ組への延長は無数に存在することが分かります。例えば、

17^2-2\times  12^2 = 1

なので、三つ組[ 1, 2, 145] が得られます。

*1:なぜ題名が『芸術家の作品』であるかは小島寛之著『解法のスーパーテクニック』を読んだ方には伝わると思います。