問題

$x^3 + 3367 = 2^n$ となる自然数の組 $(n,x)$ を全て求めよ，という河野玄斗さんの問題。出典は数学オリンピックらしい。

【数学オリンピック】学びの多すぎる整数問題の最高傑作（YouTube）

ダメな解法

左辺の最小値を考える。$x = 1$ のとき，

$$
\textsf{左辺} = 1 + 3367 = 3368 < 4096 = 2^{12} \tag{1}
$$

となるので $n >= 12$ である。すなわち与式は $2^{12} = 4096$ で必ず割り切れるので

$$
x^3 + 3367 \equiv 0 \pmod{4096} \tag{2}
$$

となる。すなわち

$$
x^3 \equiv 729 \pmod{4096} \tag{3}
$$

である。$9^3 = 729$ であるから，$x = 9$ というのが一つの答え。このとき $n = 12$ となる。ただし，他にも解は存在するのかしないのか，コレが最重要問題であるのにも関わらず残念ながらこの解法では辿り着けないようだ。

基本方針

$3367 = 7 \cdot 13 \cdot 37$ なので，なんとなく因数分解したくなるような問題である。もしも $n$ が $3$ の倍数であれば自然数 $m$ を用いて $n = 3m$ とおくと，

$$
x^3 + 7 \cdot 13 \cdot 37 = (2^m)^3 \tag{4}
$$

と書けるので $M = 2^m$ とおくと

$$
M^3 - x^3 = (M - x)\left(M^2 + Mx + x^2\right) = 7 \cdot 13 \cdot 37 \tag{5}
$$

と因数分解できる。$M - x < M^2 + Mx + x^2$ であるから条件を整理すると，以下の4通りだけ調べればよい。

番号	数式	条件1	条件2	条件3	条件4
$①$	$M - x$	$1$	$7$	$13$	$37$
$②$	$M^2 + Mx + x^2$	$7 \cdot 13 \cdot 37$	$13 \cdot 37$	$7 \cdot 37$	$7 \cdot 13$
$③ = ①^2$	$M^2 - 2Mx + x^2$	$1$	$7^2$	$13^2$	$37^2$
$④ = (② - ③)/3$	$Mx$	$1122$	$144$	$30$	$-$
$⑤ = ② + ④$	$(M + x)^2$	$4489$	$625$	$289$	$-$
$⑥ = \sqrt{⑤}$	$M + x$	$67$	$25$	$17$	$-$
$⑦ = (⑥ - ①)/2$	$x$	$33$	$9$	$1$	$-$
$⑧ = (⑥ + ①)/2$	$M$	$34$	$16$	$15$	$-$
$⑨ = \log_2{⑧}$	$m$	$-$	$4$	$-$	$-$

以上より，$x = 9$，$m = 4$ すなわち $n = 3m = 12$ が唯一の解となることが示せる。なお上記の表で不適なもの（自然数にならないもの）はハイフン($-$)で示した。

nが3の倍数であることの証明

河野玄斗さんは $7$ を法とする合同式を用いて証明したが，果たしてこれ以外の方法がないのか確かめてみる。左辺の $x^3 + 3367$ を素数 $p$ で割った余りを以下に示す。余りが $0$ から $p - 1$ まで全て揃っていると $n$ の取りうる値を制限できないので，そのような素数は除外した。なお偶然か必然か分からないが $p - 1$ は全て $6$ の倍数になっている。

表1　左辺の剰余リスト
$p$	$x^3 + 3367 \pmod{p}$
$7$	$0,1,6$
$13$	$0,1,5,8,12$
$19$	$3,4,5,11,12,15,16$
$31$	$3,4,11,15,17,18,19,20,21,23,27$
$37$	$0,1,6,8,10,11,14,23,26,27,29,31,36$
$43$	$2,5,9,11,12,13,14,15,17,21,24,29,34,35,40$

一方，右辺の $2^n$ を素数 $p$ で割った余りを以下に示す。上記の表（左辺の剰余）と一致するセルを着色した。

表2　右辺の剰余の周期性
	$2^n \pmod{p}$
$p$	$2^0$	$2^1$	$2^2$	$2^3$	$2^4$	$2^5$	$2^6$	$2^7$	$2^8$	$2^9$	$2^{10}$	$2^{11}$	$2^{12}$
$7$	$1$	$2$	$4$	$1$	$2$	$4$	$1$	$2$	$4$	$1$	$2$	$4$	$1$
$13$	$1$	$2$	$4$	$8$	$3$	$6$	$12$	$11$	$9$	$5$	$10$	$7$	$1$
$19$	$1$	$2$	$4$	$8$	$16$	$13$	$7$	$14$	$9$	$18$	$17$	$15$	$11$
$31$	$1$	$2$	$4$	$8$	$16$	$1$	$2$	$4$	$8$	$16$	$1$	$2$	$4$
$37$	$1$	$2$	$4$	$8$	$16$	$32$	$27$	$17$	$34$	$31$	$25$	$13$	$26$
$43$	$1$	$2$	$4$	$8$	$16$	$32$	$21$	$42$	$41$	$39$	$35$	$27$	$11$

これより $n$ が $3$ の倍数であることを示せる素数は $7$ 以外にも $13$ と $37$ が存在することが分かる。これも偶然か必然か分からないが，すべて $3367$ の素因数である。

計算に用いたプログラム

表1の計算に用いた javascript (WSH) を以下に示す。

// IE の javascript engine でも動かすための拡張
Array.prototype.indexOf = function( x ) {
	for( var i = 0; i < this.length; i++ ) if( this[i] == x ) return( i );
	return( -1 );
};

// 100 以下の素数リスト
var p_list = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];

// x^3 + 3367 を素数 p で割った余りのリストを求める。
// 余りが 0 から p - 1 まで全て揃っている，すなわち重複しない余りの個数が p 個の場合
// n の取りうる値を制限できないので，そのような素数は除外する。
for( var i = 0; i < p_list.length; i++ ) {
	var	p = p_list[i];
	var	r_list = [];
	for( var x = 0; x < p; x++ ) {
		var r = ( x * x * x + 3367 ) % p;
		if( r_list.indexOf( r ) < 0 ) r_list.push( r );
	}
	r_list.sort( (function( a, b ) { return( a - b ); }) );
	if( p == r_list.length ) continue;
	WScript.Echo( [p, r_list.join(",")].join("\t") );
}

表2の計算に用いた javascript を以下に示す。半分近くは上のプログラムを流用している。

// 2^n を素数 p で割った余りを求める。
// x^3 + 3367 を素数 p で割った余りのリストに含まれていなければ空文字を出力する。
for( var i = 0; i < p_list.length; i++ ) {
	var	p = p_list[i];
	var	r_list = [];
	for( var x = 0; x < p; x++ ) {
		var r = ( x * x * x + 3367 ) % p;
		if( r_list.indexOf( r ) < 0 ) r_list.push( r );
	}
	if( p == r_list.length ) continue;
	var	s_list = [];
	for( var n = 0, y = 1; n < p; n++ ) {
		var	r = y % p;
		var	s = r_list.indexOf( r ) >= 0 ? r : "";
		s_list.push( s );
		y = y * 2;
	}
	WScript.Echo( [p, s_list.join(",")].join("\t") );
}