## 2018年3月30日金曜日

### 数学 - Python - JavaScript - 数学の中の女王 - 数論へのプレリュード – 合同式 - 合同式の除法(組み合わせ、階乗、掛け算、素数)

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

が成り立つので、

$\left(p-1\right)\dots \left(p-a\right)\equiv {\left(-1\right)}^{a}a!\left(modp\right)$

よって、

$\left(\begin{array}{c}p-1\\ a\end{array}\right)a!\equiv {\left(-1\right)}^{\alpha }a!\left(modp\right)$

また、問題の仮定より、

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

ゆえに、

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

が成り立つ。

（証明終）

コード(Emacs)

Python 3

#!/usr/bin/env python3
from sympy import pprint, randprime, combinatorial
import random

for p in [randprime(2, 100) for _ in range(10)]:
print(f'素数: {p}')
for _ in range(2):
a = random.randrange(p)
l = combinatorial.numbers.nC(p - 1, a)
r = (-1) ** a
print(f'a = {a}: {(l - r) % p == 0}')


$./sample7.py 素数: 47 a = 1: True a = 22: True 素数: 37 a = 32: True a = 8: True 素数: 67 a = 30: True a = 54: True 素数: 5 a = 4: True a = 3: True 素数: 53 a = 34: True a = 16: True 素数: 59 a = 22: True a = 44: True 素数: 53 a = 52: True a = 23: True 素数: 71 a = 66: True a = 46: True 素数: 5 a = 0: True a = 0: True 素数: 79 a = 26: True a = 71: True$


HTML5

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

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

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


JavaScript

let pre0 = document.querySelector('#output0'),
btn0 = document.querySelector('#run0'),
btn1 = document.querySelector('#clear0'),
input_p = document.querySelector('#p0'),
input_a = document.querySelector('#a0'),
inputs = [input_p, input_a],
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 factorial = (n) => range(1, n + 1).reduce((x, y) => x * y, 1),
comb = (n, m) => factorial(n) / (factorial(n - m) * factorial(m)),
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),
a0 = parseInt(input_a.value, 10);

if (!(is_prime(p0) && a0 <= p0 - 1)) {
return;
}

let l = comb(p0 - 1, a0),
r = (-1) ** a0;

p((l - r) % p0 === 0);
};

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