数学 - Python - JavaScript - 数学の中の女王 - 数論へのプレリュード – 合同式 - nを法とする既約剰余類、オイラーの関数(最大公約数、互いに素)

数学読本〈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(合同式)、nを法とする既約剰余類、オイラーの関数、問9.を取り組んでみる。

9. 
   
   $\begin{array}{}1\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(2\right)=1\end{array}$
   $\begin{array}{}1,2\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(3\right)=2\end{array}$
   $\begin{array}{}1,3\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(4\right)=2\end{array}$
   $\begin{array}{}1,2,3,4\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(5\right)=4\end{array}$
   $\begin{array}{}1,5\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(6\right)=2\end{array}$
   $\mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(7\right)=6$
   $\begin{array}{}1,3,5,7\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(8\right)=4\end{array}$
   $\begin{array}{}1,2,4,5,7,8\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(9\right)=6\end{array}$
   $\begin{array}{}1,3,7,9\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(10\right)=4\end{array}$
   $\mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(11\right)=10$
   $\begin{array}{}1,5,7,11\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(12\right)=4\end{array}$
   $\mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(13\right)=12$
   $\begin{array}{}1,3,5,9,11,13\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(14\right)=6\end{array}$
   $\begin{array}{}1,2,4,7,8,11,13,14\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(15\right)=8\end{array}$
   $\begin{array}{}1,3,5,7,9,11,13,15\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(16\right)=8\end{array}$
   $\mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(17\right)=16$
   $\begin{array}{}1,5,7,11,13,17\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(18\right)=6\end{array}$
   $\mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(19\right)=18$
   $\begin{array}{}1,3,7,9,11,13,17,19\\ \mathrm{\phi \; <!--\; greek\; small\; letter\; phi\; -->}\left(20\right)=8\end{array}$

コード(Emacs)

Python 3

#!/usr/bin/env python3

from sympy import gcd

for n in range(2, 21):
    count = 0
    for m in range(1, n):
        if gcd(n, m) == 1:
            count += 1
    print(f'φ({n}) = {count}')

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

$ ./sample9.py
φ(2) = 1
φ(3) = 2
φ(4) = 2
φ(5) = 4
φ(6) = 2
φ(7) = 6
φ(8) = 4
φ(9) = 6
φ(10) = 4
φ(11) = 10
φ(12) = 4
φ(13) = 12
φ(14) = 6
φ(15) = 8
φ(16) = 8
φ(17) = 16
φ(18) = 6
φ(19) = 18
φ(20) = 8
$

HTML5

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

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

JavaScript

let pre0 = document.querySelector('#output0'),
    btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    p = (x) => pre0.textContent += x + '\n',
    is_prime = (n) => {
        for (let i = 2; i <= Math.sqrt(n); i += 1) {
            if (n % i === 0) {
                return false;
            }
        }
        return true;
    },
    gcd = (n, m) => {
        let t = 1,
            l = Math.min(n, m);

        for (let i = 2; i <= l; i += 1) {
            if (n % i === 0 && m % i === 0) {
                t = i;
            }
        }
        return t;
    }

let output = () => {
    for (let n = 2; n <= 20; n += 1) {
        let count = 0;
        for (let m = 1; m <= n - 1; m += 1) {
            if (gcd(n, m) === 1) {
                count += 1;
            }
        }
        p(`φ(${n}) = ${count}`);
    }
};

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