## 2018年1月23日火曜日

### 数学 - Python - JavaScript - 代数学 - 整数 - 同値関係、合同式(累乗(べき乗)、剰余を求める)

1. $\begin{array}{}{2}^{100}={\left({2}^{10}\right)}^{10}\\ {2}^{10}=1024\equiv 24\left(mod100\right)\\ {\left({2}^{100}-1\right)}^{99}\equiv {\left(2{4}^{10}-1\right)}^{99}\left(mod100\right)\\ 2{4}^{2}=576\equiv -24\left(mod|00\right)\\ 2{4}^{10}\equiv {\left(-24\right)}^{5}\left(mod100\right)\\ 2{4}^{10}\equiv -2{4}^{5}\equiv 2{4}^{2}\equiv -24\left(mod100\right)\\ {\left(2{4}^{10}-1\right)}^{99}\equiv {\left(-24-1\right)}^{99}\equiv {\left(-25\right)}^{99}\left(mod100\right)\\ 2{5}^{2}\equiv 25\left(mod100\right)\\ {\left(-25\right)}^{99}\equiv -2{5}^{99}\equiv -25\equiv 75\left(mod100\right)\\ {\left({2}^{100}-1\right)}^{99}\equiv 75\left(mod100\right)\end{array}$

よって、求める余りは75。

コード(Emacs)

Python 3

#!/usr/bin/env python3

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

print(mod((2 ** 100 - 1) ** 99, 75, 100))


$./sample10.py True$


HTML5

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

<script src="sample10.js"></script>


JavaScript

let pre0 = document.querySelector('#output0'),
run0 = document.querySelector('#run0'),
clear0 = document.querySelector('#clear0'),
p = (text) => pre0.textContent += text + '\n',
clear = () => pre0.textContent = '',
mod = (a, b, m) => (a - b) % m === 0,
output = () => {
p(mod((2 ** 100 - 1) ** 99, 75, 100));
p((2 ** 100 - 1) ** 99);
};

run0.onclick = output;
clear0.onclick = clear;
output();