Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@TETSURO1999

【京大2021】3ⁿ－2ⁿが素数ならnも素数になることを示せ

Last updated at Posted at 2023-08-28

問題

$3^n - 2^n$ が素数ならば $n$ も素数であることを示せ。

京都大学2021年理系第6問より

ホンマか？

試しに確認してみたが，確かに正しいようだ。ただし $n$ が素数だからといって $3^n - 2^n$ も素数になるという訳ではない。

$n$ $3^n - 2^n$ 素因数 判定
$0$ $0$ $0$ $×$
$1$ $1$ $1$ $×$
$2$ $5$ $5$ ○
$3$ $19$ $19$ ○
$4$ $65$ $5\times13$ $×$
$5$ $211$ $211$ ○
$6$ $665$ $5\times7\times19$ $×$
$7$ $2059$ $29\times71$ $×$
$8$ $6305$ $5\times13\times97$ $×$
$9$ $19171$ $19\times1009$ $×$
$10$ $58025$ $5^2\times11\times211$ $×$
$11$ $175099$ $23^2\times331$ $×$
$12$ $527345$ $5\times7\times13\times19\times61$ $×$
$13$ $1586131$ $53\times29927$ $×$
$14$ $4766585$ $5\times29\times71\times463$ $×$
$15$ $14316139$ $19\times211\times3571$ $×$
$16$ $42981185$ $5\times13\times17\times97\times401$ $×$
$17$ $129009091$ $129009091$ ○
$18$ $387158345$ $5\times7\times19\times577\times1009$ $×$
$19$ $1161737179$ $1559\times745181$ $×$
$20$ $3485735825$ $5^2\times11\times13\times211\times4621$ $×$
$21$ $10458256051$ $19\times29\times43\times71\times6217$ $×$
$22$ $31376865305$ $5\times23^2\times331\times35839$ $×$
$23$ $94134790219$ $47\times2002867877$ $×$
$24$ $282412759265$ $5\times7\times13\times19\times61\times97\times5521$ $×$
$25$ $847255055011$ $101\times211\times39756701$ $×$
$26$ $2541798719465$ $5\times53\times79\times4057\times29927$ $×$
$27$ $7625463267259$ $19\times1009\times397760329$ $×$
$28$ $22876524019505$ $5\times13\times29\times71\times463\times369181$ $×$
$29$ $68629840493971$ $68629840493971$ ○
$30$ $205890058352825$ $5^2\times7\times11\times19\times31\times211\times241\times3571$ $×$
$31$ $617671248800299$ $617671248800299$ ○

このあと少なくとも $31 < n < 48$ までは $3^n - 2^n$ は素数にならないことを確認した。おそらくベン図を描くとこんな感じになるのだろう。すなわち $n$ が素数である条件に対して，$3^n - 2^n$ が素数になる条件はそのうちのほんの一部であると考えられる。

証明

対偶の証明，すなわち $n$ が合成数なら $3^n - 2^n$ も合成数になることを証明すればよい。

$n$ が合成数ならば $1$ より大きい自然数 $a,b$ を用いて $n = a \cdot b$ と表せる。このとき

\begin{align}
3^n - 2^n &= (3^a)^b - (2^a)^b \\
&= ( 3^a - 2^a ) \left( (3^a)^{b-1} + (3^a)^{b-2}\cdot(2^a) + \cdots + (3^a)\cdot(2^a)^{b-2} + (2^a)^{b-1} \right)
\end{align}

と因数分解できる。$a,b> 1$ より

1 < 3^a - 2^a < (3^a)^{b-1} + (3^a)^{b-2}\cdot(2^a) + \cdots + (3^a)\cdot(2^a)^{b-2} + (2^a)^{b-1}

であるから $3^n - 2^n$ も合成数になることを示せた。

確認のために作った javascript プログラム

javascript では数値を double で内部表現する。double で精度を保持できる整数の上限は $2^{53} \approx 9.0 \times 10^{15}$ である。$n$ が十分大きいと $3^n - 2^n \approx 3^n$ であり，$3^{32} \approx 1.9 \times 10^{15}$ であることから $n < 32$ まで計算するようにした。

WSH（Windows Script Host）版のソースコードを以下に示す。

test.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 prime_factor( n ) {
	var a = [];
	for( var p = n; ( q = check_prime( p ) ) > 1; p = p / q )
		a.push( q );
	a.push( p );
	return( a );
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
function main() {
	for( var n = 0, x = 1, y = 1; n < 32; n++, x*=3, y*=2 ) {
		var z = x - y;
		var	a = prime_factor( z );
		var	s = ( a.length == 1 && a[0] > 1 ) ? "○" : "×";
		WScript.Echo( [n, z, a.join(","), s].join("\t") );
	}
}
//------------------------------------------------------------------------------
// メイン関数の呼び出し　※Chakra は返値を返せないのでこのまま
//------------------------------------------------------------------------------
main();

なお，上記のプログラムを WSH の javascript エンジンで実行させると途方もない時間がかかるので，旧 Microsoft Edge のエンジン，通称 Chakra で計算させた。Chakra を使う場合は下記のようにエンジンを CLSID で指定する。

C:\>cscript //E:{1B7CD997-E5FF-4932-A7A6-2A9E636DA385} test.js

IE9 のエンジン，通称 JScript9 で実行する場合はコチラ。

C:\>cscript //E:{16d51579-a30b-4c8b-a276-0ff4dc41e755} test.js

比較のため WEBブラウザで動作する html + javascript 版も作った。当たり前だが WSH 版と大半は共通コードになっている。

html + javascript 版のソースコードはコチラ
test.html
<html>
<head>
<title>TEST</title>
<script language=javascript>
//------------------------------------------------------------------------------
// 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 prime_factor( n ) {
    var a = [];
    for( var p = n; ( q = check_prime( p ) ) > 1; p = p / q )
        a.push( q );
    a.push( p );
    return( a );
}
//------------------------------------------------------------------------------
// メイン関数
//------------------------------------------------------------------------------
function main() {
    var start = performance.now(); // 開始時間を計測
    var data = [];
    for( var n = 0, x = 1, y = 1; n < 32; n++, x*=3, y*=2 ) {
        var z = x - y;
        var a = prime_factor( z );
        var s = ( a.length == 1 && a[0] > 1 ) ? "○" : "×";
        data.push( [n, z, a.join(","), s] );
    }
    var end = performance.now();  // 終了時間を計測
    // 計算結果をテーブルに追加する
    var table = document.getElementById("table");
    for( var i = 0; i < data.length; i++ ) {
        var tr  = document.createElement("tr");
        var td1 = document.createElement("td");
        var td2 = document.createElement("td");
        var td3 = document.createElement("td");
        var td4 = document.createElement("td");
        td1.innerText = data[i][0];
        td2.innerText = data[i][1];
        td3.innerText = data[i][2];
        td4.innerText = data[i][3];
        tr.appendChild( td1 );
        tr.appendChild( td2 );
        tr.appendChild( td3 );
        tr.appendChild( td4 );
        table.appendChild( tr );
    }
    // 計算時間を書き込む
    var div = document.getElementById("div");
    div.innerText = ( end - start ).toFixed(0) + "[ms]";
}
window.onload = main;
</script>
</head>
<body>
<table id=table cellspacing=0 border=1>
<tr><th>n</th><th>3&#x207F; - 2&#x207F</th><th>prime factor</th><th>judge</th></tr>
</table>
<div id=div></div>
</body>
</html>

計算時間は下記のようになった。Chakra もかなり優秀である。言語仕様はちょっと古いけど。

エンジン 計算時間
JScript 267s
JScript9 14s
Chakra 9s
FireFox 116.0.3 14s
Edge 116.0.1938.62 8s

今後の課題

ちなみに今回，下記の記事を読んで BigInt 型を勉強したのだが，BigInt 型が必要な桁数に達する前に計算時間が膨大になってしまい断念した。また BigInt 型は Chakra エンジンもサポートしておらず，Chrome の V8 エンジンなど最新ブラウザのエンジンを使用する必要がある。今回 html + javascript 版を用意したのは BigInt 型を使いたかったからである。

謝辞

以下の記事が大変参考になりました。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?