数学 - 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(同値関係、合同式)、問題7.を取り組んでみる。

7. 
   
   $\begin{array}{}{\left(x+y\right)}^p-\left(x^p+y^p\right)\\ =\underset{s=0}{\overset{p}{\sum \; <!--\; n-ary\; summation\; -->}}(\begin{array}{c}p\\ s\end{array})\end{array}{x}^s{y}^{p-s}-x^p-y^p=\underset{s=1}{\overset{p-1}{\sum \; <!--\; n-ary\; summation\; -->}}(\begin{array}{c}p\\ s\end{array})x^s{y}^{p-s}$

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

   $p|{\left(x+y\right)}^p-\left(x^p+y^p\right)$

   ゆえに

   ${\left(x+y\right)}^p\equiv \; <!--\; identical\; to\; -->x^p+y^p\left(mod\left(p\right)\right)$

コード(Emacs)

Python 3

#!/usr/bin/env python3
import random


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


ps = [2, 3, 5, 7, 11]
for p in ps:
    for _ in range(10):
        x = random.randrange(100)
        y = random.randrange(100)
        print(f'({x} + {y})^{p} ≡ x^{p} + y^{p} (mod {p}):',
              mod((x + y) ** p, x ** p + y ** p, p))

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

$ ./sample7.py
(22 + 1)^2 ≡ x^2 + y^2 (mod 2): True
(99 + 19)^2 ≡ x^2 + y^2 (mod 2): True
(79 + 78)^2 ≡ x^2 + y^2 (mod 2): True
(55 + 69)^2 ≡ x^2 + y^2 (mod 2): True
(59 + 53)^2 ≡ x^2 + y^2 (mod 2): True
(11 + 0)^2 ≡ x^2 + y^2 (mod 2): True
(41 + 51)^2 ≡ x^2 + y^2 (mod 2): True
(90 + 95)^2 ≡ x^2 + y^2 (mod 2): True
(22 + 40)^2 ≡ x^2 + y^2 (mod 2): True
(92 + 75)^2 ≡ x^2 + y^2 (mod 2): True
(98 + 77)^3 ≡ x^3 + y^3 (mod 3): True
(38 + 50)^3 ≡ x^3 + y^3 (mod 3): True
(99 + 66)^3 ≡ x^3 + y^3 (mod 3): True
(21 + 76)^3 ≡ x^3 + y^3 (mod 3): True
(33 + 1)^3 ≡ x^3 + y^3 (mod 3): True
(48 + 37)^3 ≡ x^3 + y^3 (mod 3): True
(29 + 31)^3 ≡ x^3 + y^3 (mod 3): True
(77 + 96)^3 ≡ x^3 + y^3 (mod 3): True
(12 + 85)^3 ≡ x^3 + y^3 (mod 3): True
(29 + 54)^3 ≡ x^3 + y^3 (mod 3): True
(62 + 66)^5 ≡ x^5 + y^5 (mod 5): True
(13 + 42)^5 ≡ x^5 + y^5 (mod 5): True
(42 + 27)^5 ≡ x^5 + y^5 (mod 5): True
(69 + 86)^5 ≡ x^5 + y^5 (mod 5): True
(43 + 45)^5 ≡ x^5 + y^5 (mod 5): True
(64 + 87)^5 ≡ x^5 + y^5 (mod 5): True
(2 + 49)^5 ≡ x^5 + y^5 (mod 5): True
(86 + 13)^5 ≡ x^5 + y^5 (mod 5): True
(69 + 92)^5 ≡ x^5 + y^5 (mod 5): True
(32 + 22)^5 ≡ x^5 + y^5 (mod 5): True
(22 + 13)^7 ≡ x^7 + y^7 (mod 7): True
(41 + 33)^7 ≡ x^7 + y^7 (mod 7): True
(86 + 77)^7 ≡ x^7 + y^7 (mod 7): True
(66 + 44)^7 ≡ x^7 + y^7 (mod 7): True
(14 + 32)^7 ≡ x^7 + y^7 (mod 7): True
(15 + 74)^7 ≡ x^7 + y^7 (mod 7): True
(88 + 65)^7 ≡ x^7 + y^7 (mod 7): True
(52 + 43)^7 ≡ x^7 + y^7 (mod 7): True
(40 + 57)^7 ≡ x^7 + y^7 (mod 7): True
(68 + 71)^7 ≡ x^7 + y^7 (mod 7): True
(26 + 29)^11 ≡ x^11 + y^11 (mod 11): True
(96 + 99)^11 ≡ x^11 + y^11 (mod 11): True
(48 + 32)^11 ≡ x^11 + y^11 (mod 11): True
(19 + 75)^11 ≡ x^11 + y^11 (mod 11): True
(58 + 91)^11 ≡ x^11 + y^11 (mod 11): True
(25 + 60)^11 ≡ x^11 + y^11 (mod 11): True
(11 + 62)^11 ≡ x^11 + y^11 (mod 11): True
(83 + 69)^11 ≡ x^11 + y^11 (mod 11): True
(67 + 16)^11 ≡ x^11 + y^11 (mod 11): True
(62 + 18)^11 ≡ x^11 + y^11 (mod 11): True
$

HTML5

<pre id="output0"></pre>

(<input id="x0" type="number" step="1" value="10"> +
<input id="y0" type="number" step="1" value="15">)^
<input id="p0" type="number" step="1" value="2">
≡ 
<span id="x1"></span>^<span class="p0"></span> +
<span id="y1"></span>^<span class="p0"></span>
(mod <span class="p0"></span>)
<button id="run0">run</button>
<button id="clear0">clear</button>
<script src="sample7.js"></script>

JavaScript

let pre0 = document.querySelector('#output0'),
    run0 = document.querySelector('#run0'),
    clear0 = document.querySelector('#clear0'),
    input_x0 = document.querySelector('#x0'),
    input_y0 = document.querySelector('#y0'),
    input_p0 = document.querySelector('#p0'),
    span_x1 = document.querySelector('#x1'),
    span_y1 = document.querySelector('#y1'),
    span_p0 = document.querySelectorAll('.p0'),
    inputs = [input_x0, input_y0, 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;
    },
    output = () => {
        let x = parseInt(input_x0.value, 10),
            y = parseInt(input_y0.value, 10),
            p0 = parseInt(input_p0.value, 10);

        span_x1.textContent = x;
        span_y1.textContent = y;
        span_p0.forEach((cls) => cls.textContent = p0)
        
        if (isPrime(p0)) {
            p(mod((x + y) ** p0, x ** p0 + y ** p0, p0));
        } else {
            p(`仮定を満たしていない(${p0}は素数ではない)`);
        }
    };

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

( + )^ ≡ ^ + ^ (mod )