【京大2021】pが素数ならばp⁴＋14が素数ではないことを示せ

問題

$p$ が素数ならば $p^4 + 14$ が素数ではないことを示せ。

京都大学2021年文系第5問より

軽く実験

$p \ne 3$ のときは $3$ で割り切れ，$p \ne 5$ のときは $5$ で割り切れそうである。$p \ne 3$ かつ $p \ne 15$ のときは $3 \times 5$ で割り切れそうである。

$p$	$p^4 + 14$	素因数分解
$2$	$30$	$2\times3\times5$
$3$	$95$	$5\times19$
$5$	$639$	$3^2\times71$
$7$	$2415$	$3\times5\times7\times23$
$11$	$14655$	$3\times5\times977$
$13$	$28575$	$3^2\times5^2\times127$
$17$	$83535$	$3\times5\times5569$
$19$	$130335$	$3\times5\times8689$

フェルマーの小定理

自然数 $a$ と素数 $p$ が互いに素のとき

$a^{p-1} \equiv 1 \pmod{p}$

となるというのがフェルマーの小定理。こいつを使ってみる。

証明

最小の素数 $p = 2$ を代入すると $p^4 + 14 = 30$ となるので $p^4 + 14$ が素数になるとしても $31$ 以上の素数であり，これより小さい素数になる可能性は排除してよい。

• $p \ne 5$ のとき，フェルマーの小定理より $p^4 \equiv 1 \pmod{5}$ が成立する。すなわち $p^4 + 14 \equiv 15 \equiv 0 \pmod{5}$ となる。

• $p \ne 3$ のとき，フェルマーの小定理より $p^2 \equiv 1 \pmod{3}$ が成立するので $(p^2)^2 \equiv p^4 \equiv 1 \pmod{3}$ となる。すなわち $p^4 + 14 \equiv 15 \equiv 0 \pmod{3}$ となる。

以上より，すべての素数 $p$ に対して $p^4 + 14$ は $31$ 以上の値をとり，かつ $3$ または $5$ または $3\times5$ の倍数であるから，決して素数にはならないことが示された。

素数判定に用いた javascript プログラム

以下の javascript (WSH) を用いて素数判定および素因数分解を行った。高速化のため 100 以下の素数リストを用意しているが，以降は奇数をサーチしていくというベタなアルゴリズムである。

checkprime.js

//------------------------------------------------------------------------------
// 素数チェックおよび素因数分解を行います。
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
// 100 以下の素数リスト
//------------------------------------------------------------------------------
var	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];
//------------------------------------------------------------------------------
// 素数をチェックする
// ・素数の場合は 1 を返す
// ・合成数の場合は最小の素因数を返す
//------------------------------------------------------------------------------
function check_prime( n ) {
	var	m;
	//--------------------------------------------------------------------------
	// 素数リストをチェックする
	//--------------------------------------------------------------------------
	for( var i = 0; i < list.length; i++ ) {
		m = list[i];
		if( m * m > n ) return( 1 );
		if( n % m == 0 ) return( m );
	}
	//--------------------------------------------------------------------------
	// 素因数の候補を探す
	//--------------------------------------------------------------------------
	for(;;) {
		m += 2;
		if( m * m > n ) return( 1 );
		if( check_prime( m ) != 1 ) continue;
		list.push( m );
		if( n % m == 0 ) return( m );
	}
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
function main( args ) {
	//--------------------------------------------------------------------------
	// オプション解析
	//--------------------------------------------------------------------------
	if( args.Count == 0 ) {
		WScript.Echo( "素数のチェック，合成数の場合は素因数分解を行います。" );
		WScript.Echo( "" );
		WScript.Echo( "CHECKPRIME(.JS) [整数]" );
		return( -1 );
	}
	var	n = parseInt( args(0) );
	if( n < 2 ) {
		WScript.Echo( "2 以上の整数を入力して下さい!!" );
		return( -1 );
	}
	//--------------------------------------------------------------------------
	// 再帰的に素因数分解を行う
	//--------------------------------------------------------------------------
	var	a = [];
	for( var p = n; ( q = check_prime( p ) ) > 1; p = p / q )
		a.push( q );
	a.push( p );
	if( a.length == 1 ) {
		WScript.Echo( "整数 " + n + " は素数です。" );
	} else {
		WScript.Echo( "整数 " + n + " は合成数です。" );
		WScript.Echo( a.join(",") + " を素因数に持ちます。" );
	}
	return( 0 );
}
var	ret = main( WScript.Arguments.Unnamed );
try {
	WScript.Quit( ret );
} catch(e) {
	/* 何もしない */
}

こいつを使って $p = 97$ のとき，$p^4 + 14 = 88529295$ の素数判定を行うと下記のようになる。

C:\>checkprime 88529295
整数 88529295 は合成数です。
3,5,487,12119 を素因数に持ちます。

まともな素数判定プログラムを作りたい方は下記の記事を参照されたい。

CPU のベンチマーク

自作の素数判定・素因数分解プログラムは非常に遅いことを利用して，CPU のベンチマークにも使っている。以下は素数 $6347156972521$ の判定に要した時間である。

code name	processor	base clock	max clock	time
Arrandale	Core i5-540M	2.53GHz	3.07GHz	30s
Ivy Bridge	Core i7-3770	3.40GHz	3.90GHz	20s
Kaby Lake R	Core i7-8550U	1.80GHz	4.00GHz	12s
Comet Lake	Core i5-10400	2.90GHz	4.30GHz	11s
Tiger Lake	Core i5-1135G7	2.40GHz	4.20GHz	9s
Alder Lake	Core i5-12500	3.00GHz	4.60GHz	6s
Raptor Lake	Core i7-13700	2.10GHz	5.10GHz	6s

Sandy おじさんも Ivy おじさんもそろそろ卒業しなくてはならない。