数学 - Python - JavaScript - 代数学 - 整数 - 同値関係、合同式(素数、和の累乗(べき乗)と累乗の和、一般化、数学的帰納法)

学習環境

Surface 3 (4G LTE)、Surface 3 タイプカバー、Surface ペン(端末)
Windows 10 Pro (OS)
Nebo(Windows アプリ)
iPad Pro + Apple Pencil
MyScript Nebo(iPad アプリ)
参考書籍

代数系入門 (松坂和夫(著)、岩波書店)の第1章(整数)、6(同値関係、合同式)、問題8.を取り組んでみる。

$\begin{array}{l} {(x_{1} + \dots + x_{n - 1} + x_{n})}^{p} - (x_{1}^{p} + \dots + x_{n - 1}^{p} + x_{n}^{p}) \\ = {(x_{1} + \dots + x_{n - 1})}^{p} - (x_{1}^{p} + \dots + x_{n - 1}^{p}) + \sum_{k = 0}^{p - 1} (\begin{matrix} p \\ k \end{matrix}) \end{array} {(\sum_{i = 1}^{n - 1} x_{i})}^{k} x_{n}^{p - k} - x_{n}^{p} = {(\sum_{i = 1}^{n - 1} x_{i})}^{p} - (\sum_{i = 1}^{n - 1} x_{i}^{p}) + \sum_{k = 1}^{p - 1} (\begin{matrix} p \\ k \end{matrix}) {(\sum_{i = 1}^{n - 1} x_{i})}^{k}$

よって、帰納法により、

${(\sum_{i = 1}^{n} x_{i})}^{p} \equiv \sum_{i = 1}^{n} x_{i}^{p} (m o d (p))$

が成り立つ。

コード(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):
        n = random.randrange(1, 11)
        xs = [random.randrange(100) for _ in range(n)]
        print(f'({"+".join([str(x) for x in xs])})^{p} ≡',
              '+'.join([f'{x}^{p}' for x in xs]),
              f'(mod {p}): {mod(sum(xs) ** p, sum([x ** p for x in xs]), p)}')
        print()
    print()

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

$ ./sample8.py
(82)^2 ≡ 82^2 (mod 2): True

(24+71)^2 ≡ 24^2+71^2 (mod 2): True

(5+70+57+81)^2 ≡ 5^2+70^2+57^2+81^2 (mod 2): True

(40+19+47+61+97)^2 ≡ 40^2+19^2+47^2+61^2+97^2 (mod 2): True

(78+1+93+70+94+68+66)^2 ≡ 78^2+1^2+93^2+70^2+94^2+68^2+66^2 (mod 2): True

(28+8+80+16+36+70+44+67)^2 ≡ 28^2+8^2+80^2+16^2+36^2+70^2+44^2+67^2 (mod 2): True

(93+86)^2 ≡ 93^2+86^2 (mod 2): True

(16+54)^2 ≡ 16^2+54^2 (mod 2): True

(38+49+89+30+80+86+50+18)^2 ≡ 38^2+49^2+89^2+30^2+80^2+86^2+50^2+18^2 (mod 2): True

(91+74+63+83+77)^2 ≡ 91^2+74^2+63^2+83^2+77^2 (mod 2): True


(14+43+61+54+29+27+59+36+55+32)^3 ≡ 14^3+43^3+61^3+54^3+29^3+27^3+59^3+36^3+55^3+32^3 (mod 3): True

(21+13+5+47+90+9+75)^3 ≡ 21^3+13^3+5^3+47^3+90^3+9^3+75^3 (mod 3): True

(33+54+45+14+58+20)^3 ≡ 33^3+54^3+45^3+14^3+58^3+20^3 (mod 3): True

(42+28+77)^3 ≡ 42^3+28^3+77^3 (mod 3): True

(64+66+44+42+95+4+10+39+69)^3 ≡ 64^3+66^3+44^3+42^3+95^3+4^3+10^3+39^3+69^3 (mod 3): True

(33)^3 ≡ 33^3 (mod 3): True

(73+91+36+69+52+51+40+17+45)^3 ≡ 73^3+91^3+36^3+69^3+52^3+51^3+40^3+17^3+45^3 (mod 3): True

(45+92+68+77+56+85+70)^3 ≡ 45^3+92^3+68^3+77^3+56^3+85^3+70^3 (mod 3): True

(90+7+37+9+18+52)^3 ≡ 90^3+7^3+37^3+9^3+18^3+52^3 (mod 3): True

(22+57+56+78+96)^3 ≡ 22^3+57^3+56^3+78^3+96^3 (mod 3): True


(78+26+21+10+84+41)^5 ≡ 78^5+26^5+21^5+10^5+84^5+41^5 (mod 5): True

(59+44+99+81+52+54+44)^5 ≡ 59^5+44^5+99^5+81^5+52^5+54^5+44^5 (mod 5): True

(36+62+74+31+85+9+71+16)^5 ≡ 36^5+62^5+74^5+31^5+85^5+9^5+71^5+16^5 (mod 5): True

(44+26+49+77+10+13+40+41+7)^5 ≡ 44^5+26^5+49^5+77^5+10^5+13^5+40^5+41^5+7^5 (mod 5): True

(9+11)^5 ≡ 9^5+11^5 (mod 5): True

(53+81+36)^5 ≡ 53^5+81^5+36^5 (mod 5): True

(33+63+91+52+87+50+17+46)^5 ≡ 33^5+63^5+91^5+52^5+87^5+50^5+17^5+46^5 (mod 5): True

(10)^5 ≡ 10^5 (mod 5): True

(33+88+12+36+24+89+92+95+35)^5 ≡ 33^5+88^5+12^5+36^5+24^5+89^5+92^5+95^5+35^5 (mod 5): True

(40+26+85+28)^5 ≡ 40^5+26^5+85^5+28^5 (mod 5): True


(55)^7 ≡ 55^7 (mod 7): True

(76+30+55+88+37+93+18+71+72+62)^7 ≡ 76^7+30^7+55^7+88^7+37^7+93^7+18^7+71^7+72^7+62^7 (mod 7): True

(84+69+8+69+40)^7 ≡ 84^7+69^7+8^7+69^7+40^7 (mod 7): True

(97+9+44+64+82+90)^7 ≡ 97^7+9^7+44^7+64^7+82^7+90^7 (mod 7): True

(93+71+26+4+70+99+17+4)^7 ≡ 93^7+71^7+26^7+4^7+70^7+99^7+17^7+4^7 (mod 7): True

(89+6)^7 ≡ 89^7+6^7 (mod 7): True

(44+18+52+4+85+92+24+48+14)^7 ≡ 44^7+18^7+52^7+4^7+85^7+92^7+24^7+48^7+14^7 (mod 7): True

(32+79+80+90+41+92)^7 ≡ 32^7+79^7+80^7+90^7+41^7+92^7 (mod 7): True

(79+12+95+94+31+44+75)^7 ≡ 79^7+12^7+95^7+94^7+31^7+44^7+75^7 (mod 7): True

(74+34+3+5+9+97+86+78)^7 ≡ 74^7+34^7+3^7+5^7+9^7+97^7+86^7+78^7 (mod 7): True


(26+12+74+41+60)^11 ≡ 26^11+12^11+74^11+41^11+60^11 (mod 11): True

(85+32+33)^11 ≡ 85^11+32^11+33^11 (mod 11): True

(22+99+36+43+76+1+19+65)^11 ≡ 22^11+99^11+36^11+43^11+76^11+1^11+19^11+65^11 (mod 11): True

(13+42+0+46+82+68+40)^11 ≡ 13^11+42^11+0^11+46^11+82^11+68^11+40^11 (mod 11): True

(23)^11 ≡ 23^11 (mod 11): True

(90+8+83+92+99+12+56+1+26)^11 ≡ 90^11+8^11+83^11+92^11+99^11+12^11+56^11+1^11+26^11 (mod 11): True

(49+60+45+96+85+35)^11 ≡ 49^11+60^11+45^11+96^11+85^11+35^11 (mod 11): True

(87+72+25+61)^11 ≡ 87^11+72^11+25^11+61^11 (mod 11): True

(91+3+63+96+88+82+19+44+6)^11 ≡ 91^11+3^11+63^11+96^11+88^11+82^11+19^11+44^11+6^11 (mod 11): True

(96+36+17+30+24+68+42+51)^11 ≡ 96^11+36^11+17^11+30^11+24^11+68^11+42^11+51^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="sample8.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 )

Kamimura's blog

2018年1月9日火曜日

数学 - Python - JavaScript - 代数学 - 整数 - 同値関係、合同式(素数、和の累乗(べき乗)と累乗の和、一般化、数学的帰納法)

0 コメント:

コメントを投稿