## 2018年1月9日火曜日

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

1. $\begin{array}{}{\left({x}_{1}+\dots +{x}_{n-1}+{x}_{n}\right)}^{p}-\left({x}_{1}^{p}+\dots +{x}_{n-1}^{p}+{x}_{n}^{p}\right)\\ ={\left({x}_{1}+\dots +{x}_{n-1}\right)}^{p}-\left({x}_{1}^{p}+\dots +{x}_{n-1}^{p}\right)+\sum _{k=0}^{p-1}\left(\begin{array}{c}p\\ k\end{array}\right)\end{array}{\left(\sum _{i=1}^{n-1}{x}_{i}\right)}^{k}{x}_{n}^{p-k}-{x}_{n}^{p}={\left(\sum _{i=1}^{n-1}{x}_{i}\right)}^{p}-\left(\sum _{i=1}^{n-1}{x}_{i}^{p}\right)+\sum _{k=1}^{p-1}\left(\begin{array}{c}p\\ k\end{array}\right){\left(\sum _{i=1}^{n-1}{x}_{i}\right)}^{k}$

よって、帰納法により、

${\left(\sum _{i=1}^{n}{x}_{i}\right)}^{p}\equiv \sum _{i=1}^{n}{x}_{i}^{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):
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()


$./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 )