## 2017年12月31日日曜日

### 数学 - Python - JavaScript - 代数学 - 整数 - 同値関係、合同式(素数、和の累乗(べき乗)と累乗の和)

1. $\begin{array}{}{\left(x+y\right)}^{p}-\left({x}^{p}+{y}^{p}\right)\\ =\sum _{s=0}^{p}\left(\begin{array}{c}p\\ s\end{array}\right)\end{array}{x}^{s}{y}^{p-s}-{x}^{p}-{y}^{p}=\sum _{s=1}^{p-1}\left(\begin{array}{c}p\\ s\end{array}\right){x}^{s}{y}^{p-s}$

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

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

ゆえに

${\left(x+y\right)}^{p}\equiv {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))

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