整数論的関数

数論的な関数を中心に関数の使用法をまとめます。

基本的な関数

関数名 意味
binomial(a,b) 二項係数
totient(n) オイラーのトーシェント関数

binomial(a,b) は二項係数です。

binomial(6,2);
実行結果. 15

totient(n) はオイラーの$\varphi(n)$関数です。つまり$n$以下の自然数で、$n$と互いに素な数の個数を表します。

totient(7);
実行結果. 6

素数

関数名 意味
primep 素数テスト
next_prime (n) n の次の素数
primes(a, b) a 以上 b 以下の素数を取得.

primep(n) で n が素数かどうか判定できます。

primep(13);
実行結果. true

next_prime(n) は n より大きい最も n に近い素数を返します。

next_prime(12);
実行結果. 13

primes(a,b) は a 以上 b 以下にある素数のリストを返します。

primes(1,100);
実行結果. [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

合同式

関数名 意味
mod(a,b) a mod b
power_mod(a,b,n) a^b mod n
inv_mod(a,n) a のmod n における逆数.
chinese 1次の連立合同式の解を求める
zn_nth_root(a,n,m) mod m の世界の a の n 乗根.

mod(a,b) で a を b で割った余りが求められます。

mod(12,7);
実行結果. 5

これは \[ 12 \equiv 5 \mod 7 \] を意味します。

power_mod(a,b,n) は a^b mod n を計算します。

power_mod(2,3,5);
実行結果. 3

これは \[ 2^3 \equiv 3 \mod 5 \] を意味します。

inv_mod(a,b) は mod b の世界での a の逆数を意味します。

inv_mod(2,5);
実行結果. 3

これは \[ 2^{-1} \equiv 3 \mod 5 \] を意味します。あるいは同じことですが、 \[ 2x \equiv 1 \mod 5 \] の解が $x \equiv 3$ であることを表しています。

10進数の割り算 で1/7 を筆算で求めました。 ここで、この結果が正しいことを確認します。

inv_mod(7,10^30);
実行結果. 857142857142857142857142857143

これは \[ 7^{-1} \equiv 857142857142857142857142857143 \mod 10^{30} \] を意味し、たしかに「285714」が循環していく様子が見て取れます。

chinese([a,b],[n,m]) は次の連立合同式の解を返します。 \[ \begin{cases} x = a \mod n \\ x = b \mod m \end{cases} \]

chinese([1,2],[3,5]);
実行結果. 7

これは \[ \begin{cases} x = 1 \mod 3 \\ x = 2 \mod 5 \end{cases} \] の解が $x\equiv 7 \mod 15 $ であることを意味します。

zn_nth_root(a,b,n) は mod n における a の b 乗根のリストを返します。すなわち \[ x^b \equiv a \mod n \] をみたす $x$ 全体のリストです。

zn_nth_root(1,2,5);
実行結果. [1,4]

これは \[ x^2 \equiv 1 \mod 5 \] をみたす $x$ が $x \equiv 1,4$ であることを意味します。

連分数

関数名 意味
cf(数) 連分数展開のリストを得る.
cfdisrep(リスト) リストを連分数表示.
cfexpand(リスト) 連分数展開の行列表示.

cf(a) で a の連分数展開の結果をリストで取得できます。

cf(7/5);
実行結果. [1,2,2]

これは \[ \frac{7}{5} = 1+\frac{1}{2+\cfrac{1}{2}} \] を意味します。

cfdisrep(リスト) でリストから得られる連分数表示を得ます。

cfdisrep([1,2,2]);
実行結果. \[1+\frac{1}{2+\cfrac{1}{2}}\]

cfexpand(リスト) でリストから連分数表示に対応する行列を得ます。

cfexpand([1,2,2]);
実行結果. \[\begin{pmatrix}7 & 3\\ 5 & 2\end{pmatrix}\]

この行列の1列目に並ぶのが \[ \frac{7}{5} = [1,2,2] =1+\frac{1}{2+\cfrac{1}{2}} \] であり、2列目に並ぶのが \[ \frac{3}{2} = [1,2] = 1+\frac{1}{2} \] となっています。この行列の意味はこちらをご覧ください。

Note. 平方根も連分数展開できます。