数学 - 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(合同式)、合同式の除法、問4.を取り組んでみる。

4. 
   
   $r!(\begin{array}{c}p\\ r\end{array})=\frac{r!p!}{\left(p-r\right)!r!}=\frac{p!}{\left(p-r\right)!}=p\left(p-1\right)\dots \; <!--\; horizontal\; ellipsis\; -->\left(p-r+1\right)$

   よって、 p で割り切れる。

   $p|r!(\begin{array}{c}p\\ r\end{array})$

   また、問題の仮定より、

   $r!$

   は p では割り切れない。

   よって、命題3 より、

   $p\left|(\begin{array}{c}p\\ r\end{array}\right)$

   となる。

   （証明終）

コード(Emacs)

Python 3

#!/usr/bin/env python3
from sympy import pprint, randprime, combinatorial
import random
for p in [randprime(1, 100) for _ in range(10)]:
    r = random.randrange(1, p)
    c = combinatorial.numbers.nC(p, r)
    for t in [p, r, c, c % p]:
        pprint(t)
    print()

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

$ ./sample4.py
43
38
962598
0

67
3
47905
0

17
14
680
0

59
13
4047376351620
0

41
37
101270
0

37
2
666
0

59
15
39895566894540
0

79
3
79079
0

37
23
6107086800
0

73
66
1629348612
0

$

HTML5

<pre id="output0"></pre>
<label for="r0">r = </label>
<input id="r0" type="number" min="1" step="1" value="5">
<label for="p0">p0 = </label>
<input id="p0" type="number" min="0" step="1" value="11">

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

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

JavaScript

let pre0 = document.querySelector('#output0'),
    btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    input_p = document.querySelector('#p0'),
    input_r = document.querySelector('#r0'),
    inputs = [input_p, input_r],
    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),
    combination = (n, m) => factorial(n) / (factorial(n - m) * factorial(m)),
    is_prime = (n) =>
    range(2, Math.floor(Math.sqrt(n))).every((m) => n % m !== 0);

let output = () => {
    let p0 = parseInt(input_p.value, 10),
        r = parseFloat(input_r.value, 10);

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

    let c = combination(p0, r);
    
    p(`${c} ${c % p0}`);
};

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

r = p0 =