## 2018年4月1日日曜日

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

1. $\begin{array}{}1\\ \phi \left(2\right)=1\end{array}$
$\begin{array}{}1,2\\ \phi \left(3\right)=2\end{array}$
$\begin{array}{}1,3\\ \phi \left(4\right)=2\end{array}$
$\begin{array}{}1,2,3,4\\ \phi \left(5\right)=4\end{array}$
$\begin{array}{}1,5\\ \phi \left(6\right)=2\end{array}$
$\phi \left(7\right)=6$
$\begin{array}{}1,3,5,7\\ \phi \left(8\right)=4\end{array}$
$\begin{array}{}1,2,4,5,7,8\\ \phi \left(9\right)=6\end{array}$
$\begin{array}{}1,3,7,9\\ \phi \left(10\right)=4\end{array}$
$\phi \left(11\right)=10$
$\begin{array}{}1,5,7,11\\ \phi \left(12\right)=4\end{array}$
$\phi \left(13\right)=12$
$\begin{array}{}1,3,5,9,11,13\\ \phi \left(14\right)=6\end{array}$
$\begin{array}{}1,2,4,7,8,11,13,14\\ \phi \left(15\right)=8\end{array}$
$\begin{array}{}1,3,5,7,9,11,13,15\\ \phi \left(16\right)=8\end{array}$
$\phi \left(17\right)=16$
$\begin{array}{}1,5,7,11,13,17\\ \phi \left(18\right)=6\end{array}$
$\phi \left(19\right)=18$
$\begin{array}{}1,3,7,9,11,13,17,19\\ \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}')


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