## 2018年1月12日金曜日

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

1. $a=0$

のとき、

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

よって、

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

の場合。

$\begin{array}{}p-1\equiv -1\left(mod\left(p\right)\right)\\ p-2\equiv -2\left(mod\left(p\right)\right)\\ ⋮\\ p-a\equiv -a\left(mod\left(p\right)\right)\end{array}$

より、

$\begin{array}{}\left(p-1\right)\left(p-2\right)\dots \left(p-a\right)\equiv {\left(-1\right)}^{a}a!\left(mod\left(p\right)\right)\\ \left(\begin{array}{c}p-1\\ a\end{array}\right)\end{array}a!\equiv {\left(-1\right)}^{a}a!\left(mod\left(p\right)\right)$
$\begin{array}{}\left(\begin{array}{c}p-1\\ a\end{array}\right)\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}{}\left(\begin{array}{c}p-1\\ a\end{array}\right)\end{array}-{\left(-1\right)}^{a}\equiv 0\left(mod\left(p\right)\right)\left(\begin{array}{c}p-1\\ a\end{array}\right)\equiv {\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()


$./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();