数学 - Python - JavaScript - 数学の中の女王 - 数論へのプレリュード – 合同式 - オイラーの定理、フェルマーの定理(フェルマーの定理の証明)

数学読本〈6〉

学習環境

• Surface 3 (4G LTE)、Surface 3 タイプ カバー、Surface ペン(端末)
• Windows 10 Pro (OS)
• Nebo(Windows アプリ)
• iPad Pro + Apple Pencil
• MyScript Nebo(iPad アプリ)
• 参考書籍
  • Pythonからはじめる数学入門
  • JavaScriptリファレンス 第6版
  • インタラクティブ・データビジュアライゼーション

数学読本〈6〉線形写像・1次変換/数論へのプレリュード/集合論へのプレリュード/εとδ/落ち穂拾い など(松坂 和夫(著)、岩波書店)の第23章(数学の中の女王 - 数論へのプレリュード)、23.2(合同式)、オイラーの定理、フェルマーの定理、問10.を取り組んでみる。

10. 
    

    問題より、 n が正の整数のときは成り立つ。

    n が零のとき、

    $\begin{array}{}{0}^p-0=0\\ 0^p\equiv \; <!--\; identical\; to\; -->0\left(modp\right)\end{array}$

    よって、成り立つ。

    n が負の整数のとき。

    $n=-m$

    とおく。(m は正の整数）

    ${\left(-m\right)}^p\equiv \; <!--\; identical\; to\; -->\left(-m\right)$

    p が2の場合。

    $\begin{array}{}{m}^2+m\\ =m\left(m+1\right)\\ =2k\\ m^2\equiv \; <!--\; identical\; to\; -->m\left(mod2\right)\end{array}$

    p が2ではない場合、素数 p は奇数なので、

    $\begin{array}{}{\left(-m\right)}^p\equiv \; <!--\; identical\; to\; -->-m\left(modp\right)\\ -m^p\equiv \; <!--\; identical\; to\; -->-m\left(modp\right)\\ m^p\equiv \; <!--\; identical\; to\; -->m\left(modp\right)\end{array}$

    m は正の整数なので、この合同式は成り立つ。

    （証明終）

コード(Emacs)

Python 3

#!/usr/bin/env python3

from sympy import randprime
import random

for _ in range(10):
    p = randprime(1, 100)
    n = random.randrange(-100, 101)
    print((n ** p - n) % p == 0)

入出力結果(Terminal, Jupyter(IPython))

$ ./sample10.py
True
True
True
True
True
True
True
True
True
True
$

HTML5

<pre id="output0"></pre>
<label for="p0">p = </label>
<input id="p0" type="number" min="2" step="1" value="11">
<label for="n0">n = </label>
<input id="n0" type="number" min="0" step="1" value="5">

<button id="run0">run</button>
<button id="clear0">clear</button>

<script src="sample10.js"></script>

JavaScript

let pre0 = document.querySelector('#output0'),
    btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    input_p = document.querySelector('#p0'),
    input_n = document.querySelector('#n0'),
    inputs = [input_p, input_n],
    p = (x) => pre0.textContent += x + '\n',
    range = (start, end, step=1) => {
        let res = [];
        for (let i = start; i < end; i += step) {
            res.push(i);
        }
        return res;
    };

let is_prime = (n) =>
    range(2, Math.floor(Math.sqrt(n) + 1)).every((m) => n % m !== 0);

let output = () => {
    let p0 = parseInt(input_p.value, 10),
        n0 = parseInt(input_n.value, 10);

    if (!is_prime(p0)) {
        return;
    }
    
    p((n0 ** p0 - n0) % p0 === 0);
};

inputs.forEach((input) => input.onchange = output);
btn0.onclick = output;
btn1.onclick = () => pre0.textContent = '';
output();

p = n =