数学 - Python - JavaScript - 数学の中の女王 - 数論へのプレリュード – 合同式 - 合同式の除法(剰余、2の累乗(べき乗)、簡略化)

数学読本〈6〉

学習環境

• Surface 3 (4G LTE)、Surface 3 タイプ カバー、Surface ペン(端末)
• Windows 10 Pro (OS)
• Nebo(Windows アプリ)
• iPad Pro + Apple Pencil
• MyScript Nebo(iPad アプリ)
• 参考書籍
  • Pythonからはじめる数学入門
  • JavaScriptリファレンス 第6版
  • インタラクティブ・データビジュアライゼーション

数学読本〈6〉線形写像・1次変換/数論へのプレリュード/集合論へのプレリュード/εとδ/落ち穂拾い など(松坂 和夫(著)、岩波書店)の第23章(数学の中の女王 - 数論へのプレリュード)、23.2(合同式)、合同式の除法、問8.を取り組んでみる。

8. 
   
   $\begin{array}{}{2}^{10}\\ =1024\\ \equiv \; <!--\; identical\; to\; -->24\left(mod100\right)\end{array}$

   よって求める余りは24。

   $\begin{array}{}{2}^{20}\\ ={\left(2^{10}\right)}^2\\ \equiv \; <!--\; identical\; to\; -->24^2\\ \equiv \; <!--\; identical\; to\; -->-24\\ \equiv \; <!--\; identical\; to\; -->76\left(mod100\right)\end{array}$

   よって求める余りは76。

   $\begin{array}{}{2}^{100}\\ ={\left(2^{10}\right)}^{10}\\ \equiv \; <!--\; identical\; to\; -->24^{10}\\ ={\left(24^2\right)}^5\\ \equiv \; <!--\; identical\; to\; -->{\left(-24\right)}^5\\ =-24^5\\ =-24{\left(24^2\right)}^2\\ \equiv \; <!--\; identical\; to\; -->-24{\left(-24\right)}^2\\ =-24·\; <!--\; middle\; dot\; -->24^2\\ \equiv \; <!--\; identical\; to\; -->24^2\\ \equiv \; <!--\; identical\; to\; -->-24\\ \equiv \; <!--\; identical\; to\; -->76\left(mod100\right)\end{array}$

   よって求める余りは76。

   $\begin{array}{}{2}^{100}-1\\ \equiv \; <!--\; identical\; to\; -->-24-1\\ =-25\\ \equiv \; <!--\; identical\; to\; -->75\left(mod100\right)\end{array}$

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

   $\begin{array}{}{\left(2^{100}-1\right)}^{99}\\ \equiv \; <!--\; identical\; to\; -->{\left(-25\right)}^{99}\\ =-25^{99}\\ \equiv \; <!--\; identical\; to\; -->-25\\ \equiv \; <!--\; identical\; to\; -->75\left(mod100\right)\end{array}$

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

   $\begin{array}{}{\left(2^{100}-1\right)}^{100}\\ \equiv \; <!--\; identical\; to\; -->75·\; <!--\; middle\; dot\; -->75\\ =9·\; <!--\; middle\; dot\; -->25^2\\ \equiv \; <!--\; identical\; to\; -->9·\; <!--\; middle\; dot\; -->25\\ =225\\ \equiv \; <!--\; identical\; to\; -->25\left(mod100\right)\end{array}$

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

コード(Emacs)

Python 3

#!/usr/bin/env python3

nums = [2 ** 10, 2 ** 20, 2 ** 100, 2 ** 100 - 1,
        (2 ** 100 - 1) ** 99, (2 ** 100 - 1) ** 100]
for n in nums:
    print(n % 100)

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

$ ./sample8.py
24
76
76
75
75
25
$

HTML5

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

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

JavaScript

let pre0 = document.querySelector('#output0'),
    btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    p = (x) => pre0.textContent += x + '\n';

let nums = [2 ** 10, 2 ** 20, 2 ** 100, 2 ** 100 - 1,
            (2 ** 100 - 1) ** 99, (2 ** 100 - 1) ** 100];

let output = () => {
    p(nums.map((n) => n % 100).join('\n'));
};

btn0.onclick = output;
btn1.onclick = () => pre0.textContent = '';
output();

24
76
76
76
NaN
NaN