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

6. 
   
   $\begin{array}{}{\left(a_1+\dots \; <!--\; horizontal\; ellipsis\; -->+a_n\right)}^p\\ ={\left(\left(a_1+\dots \; <!--\; horizontal\; ellipsis\; -->+a_{n-1}\right)+a_n\right)}^p\\ \equiv \; <!--\; identical\; to\; -->{\left(a_1+\dots \; <!--\; horizontal\; ellipsis\; -->+a_{n-1}\right)}^p+a_n^p\left(modp\right)\end{array}$

   よって、帰納法により、任意の正の整数n に対して成り立つ。

   （証明終）

コード(Emacs)

Python 3

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

for p in [randprime(2, 100) for _ in range(10)]:
    n = random.randrange(2, 100)
    nums = [random.randrange(100) for _ in range(n)]
    nums1 = [n0 ** p for n0 in nums]
    print(nums)
    print((sum(nums) ** p - sum(nums1)) % p == 0)

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

$ ./sample6.py
[70, 44]
True
[59, 72, 44, 11, 34, 83, 21, 36, 38, 67, 85, 47, 85, 68]
True
[30, 69, 18, 87, 42, 85, 41, 75, 75, 30, 30, 89, 15, 74, 47, 2, 75, 86, 65, 60, 50, 39, 6, 12, 10, 16, 44, 86, 97, 4, 78, 82, 48, 8, 1, 88, 29, 48, 24, 35, 8, 11, 94, 14, 44, 8, 26, 78, 60, 68, 35, 29, 78, 71, 94, 96, 11, 67, 94, 45, 63, 95, 69]
True
[66, 50, 34, 48, 74, 15, 38, 90, 81, 65, 40, 0, 37, 42, 72, 8, 39, 33, 92, 90, 99, 11, 72, 95, 79, 33, 12, 51, 66, 1, 86, 69, 72, 45, 87, 88, 46, 5, 4, 24, 33, 15, 96, 34, 85, 92, 11, 13, 11, 70, 69, 26, 36, 21, 24, 66, 37, 60, 39, 18, 61, 22, 50, 8, 21, 43, 85, 32, 10, 47, 79, 6, 88, 88, 10, 30, 6, 93, 63, 74, 46, 29, 73, 50, 75, 77, 62, 80, 30, 91, 15, 15, 40, 5, 43, 64, 65, 22, 89]
True
[55, 1, 65, 1, 25, 72, 71, 38, 51, 55, 11, 44, 75, 17, 51, 20, 77, 96, 28, 2, 88, 2, 48, 90, 15, 61, 22, 65, 17, 56, 19, 30, 56, 30, 79, 85, 25, 49, 55, 57, 9, 74, 57, 11, 55, 74, 68, 45, 88, 55, 94, 88, 18, 11, 25, 47, 74, 72, 11, 21, 75, 79, 94, 14, 66]
True
[60, 96, 7, 30, 76, 53, 47, 92, 20, 85, 20, 79, 15, 92, 53, 86, 10, 78, 62, 48, 51, 16, 52, 29, 50, 32, 16, 0, 56, 28, 29, 62, 43, 24, 85, 16, 98, 23, 22, 56, 93, 17, 61, 29, 23, 45, 17, 17, 21, 42, 9, 40]
True
[3, 46, 5, 30, 47, 28, 57, 65, 21, 81, 2, 64, 82, 29, 41, 93, 27, 41, 93, 58, 54, 78, 64, 30, 55, 72, 50, 70, 9, 86, 69, 11, 17, 96, 73, 60, 84, 8, 11, 34, 94, 48]
True
[93, 58, 35, 3, 64, 76, 49, 43, 41, 59, 36, 80, 68, 92, 37, 52, 95, 9, 99, 7, 29, 83, 89, 95, 43, 67, 18, 67, 40, 65, 6, 26, 55, 81, 1, 70, 43, 94, 20, 16, 82, 49, 54, 33, 7, 16, 81, 9, 30, 42, 65, 93, 43, 49, 57, 91, 49, 36, 70, 65, 71, 80, 98, 60, 28, 85, 52, 9, 35, 10, 50, 36, 51, 94, 39, 40, 28, 34, 36, 39, 75, 25, 23, 47, 29, 64]
True
[49, 9, 0, 81, 67, 14, 79, 7, 54, 11, 68, 82, 45, 72, 12, 77, 24, 34, 1, 69, 18, 42, 3, 16, 68, 32, 62, 49, 47, 75, 89, 66, 83, 35, 94, 17, 9, 6, 55, 82, 24, 15, 99, 3, 40, 15, 14, 29, 74, 61, 13, 34, 61, 1, 36, 35, 13, 68, 78, 3, 75, 75, 63, 75, 83, 64, 56, 42, 28, 80, 57, 63, 12, 60, 97, 9, 65, 74, 73, 90, 99, 60, 63, 89, 61, 47, 11]
True
[0, 9, 31, 41, 43, 6, 58, 53, 49, 50, 27, 96, 50, 26, 56, 18, 96, 73, 55, 11, 81, 83, 6, 47, 92, 64, 37, 47, 24, 36, 56, 16, 70, 44, 72, 12, 59, 52, 62, 28, 82, 53, 25, 7, 12, 10, 63, 88, 45, 29, 36, 93, 36, 1, 13, 51, 11, 4, 99]
True
$

HTML5

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

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

<script src="sample6.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),
    f = (p, a, b) => {
        let m = ((a + b) ** p - (a ** p + b ** p)) % p;

        return [m, m === 0];
    };

let output = () => {
    let p0 = parseInt(input_p.value, 10),
        n0 = parseInt(input_n.value, 10);        
    
    if (!is_prime(p0)) {
        return;
    }
    let nums = range(0, n0).map(() => Math.floor(Math.random() * 10)),
        nums1 = nums.map((n) => n ** p0),
        l = nums.reduce((x, y) => x + y, 0) ** p0,
        r = nums1.reduce((x, y) => x + y, 0);

    p(nums);
    p(nums1);
    p(l);
    p(r);
    p((l - r) % p0);
};

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

p = n =