数学 - Python - JavaScript - 代数学 - 整数 - 同値関係、合同式(素数、組み合わせ、累乗、積)

代数系入門

学習環境

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

代数系入門 (松坂 和夫(著)、岩波書店)の第1章(整数)、6(同値関係、合同式)、問題9.を取り組んでみる。

9. 
   
   $a=0$

   のとき、

   $(\begin{array}{c}p-1\\ 0\end{array})-{\left(-1\right)}^0=1-1=0$

   よって、

   $(\begin{array}{c}p-1\\ a\end{array})\equiv \; <!--\; identical\; to\; -->{\left(-1\right)}^a\left(mod\left(p\right)\right)$
   $0<a\leqq \; <!--\; latex:\; \backslash leqq\; -->p-1$

   の場合。

   $\begin{array}{}p-1\equiv \; <!--\; identical\; to\; -->-1\left(mod\left(p\right)\right)\\ p-2\equiv \; <!--\; identical\; to\; -->-2\left(mod\left(p\right)\right)\\ ⋮\; <!--\; vertical\; ellipsis\; -->\\ p-a\equiv \; <!--\; identical\; to\; -->-a\left(mod\left(p\right)\right)\end{array}$

   より、

   $\begin{array}{}\left(p-1\right)\left(p-2\right)\dots \; <!--\; horizontal\; ellipsis\; -->\left(p-a\right)\equiv \; <!--\; identical\; to\; -->{\left(-1\right)}^{a}a!\left(mod\left(p\right)\right)\\ (\begin{array}{c}p-1\\ a\end{array})\end{array}a!\equiv \; <!--\; identical\; to\; -->{\left(-1\right)}^{a}a!\left(mod\left(p\right)\right)$
   $\begin{array}{}(\begin{array}{c}p-1\\ a\end{array})\end{array}a!-{\left(-1\right)}^{a}a!=\left(\left(p_a-1\right)-{\left(-1\right)}^a\right)a!$

   また、仮定より

   $\left(a,p\right)=1$

   よって

   $\begin{array}{}(\begin{array}{c}p-1\\ a\end{array})\end{array}-{\left(-1\right)}^a\equiv \; <!--\; identical\; to\; -->0\left(mod\left(p\right)\right)(\begin{array}{c}p-1\\ a\end{array})\equiv \; <!--\; identical\; to\; -->{\left(-1\right)}^a\left(mod\left(p\right)\right)$

コード(Emacs)

Python 3

#!/usr/bin/env python3
from sympy import factorial


def mod(a, b, m):
    return (a - b) % m == 0


def comb(a, b):
    return factorial(a) / (factorial(a - b) * factorial(b))

ps = [2, 3, 5, 7, 11]
for p in ps:
    print(f'素数: {p}')
    for a in range(p):
        print(f'{a}: {mod(comb(p - 1, a), (-1) ** a, p)}')
    print()

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

$ ./sample9.py
素数: 2
0: True
1: True

素数: 3
0: True
1: True
2: True

素数: 5
0: True
1: True
2: True
3: True
4: True

素数: 7
0: True
1: True
2: True
3: True
4: True
5: True
6: True

素数: 11
0: True
1: True
2: True
3: True
4: True
5: True
6: True
7: True
8: True
9: True
10: True

$

HTML5

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

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

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

JavaScript

let pre0 = document.querySelector('#output0'),
    run0 = document.querySelector('#run0'),
    clear0 = document.querySelector('#clear0'),
    input_p0 = document.querySelector('#p0'),
    inputs = [input_p0],
    range = (n) => {
        let result = [];

        for (let i = 0; i < n; i += 1) {
            result.push(i);
        }
        
        return result;
    },
    p = (text) => pre0.textContent += text + '\n',
    clear = () => pre0.textContent = '',
    mod = (a, b, m) => (a - b) % m === 0,
    isPrime = (n) => {
        for (let i = 2; i <= Math.sqrt(n); i += 1) {
            if (n % i === 0) {
                return false;
            }
        }
        return true;
    },
    factorial = (n) => range(n).reduce((x, y) => x * (y + 1), 1),
    combination = (a, b) => factorial(a) / (factorial(a - b) * factorial(b)),
    output = () => {
        let p0 = parseInt(input_p0.value, 10);
        
        if (isPrime(p0)) {
            p(`素数: ${p0}`);
            p(
                range(p0)
                    .map((a) =>
                         `${a}: ${mod(combination(p0 - 1, a), (-1) ** a, p0)}`)
                    .join('\n')
            );
        } else {
            p(`仮定を満たしていない(${p0}は素数ではない)`);
        }
    };

run0.onclick = output;
clear0.onclick = clear;
inputs.forEach((input) => input.onchange = output);
output();

p =