合同式、オイラーの定理 - kanetaiの二次記憶装置

リポジトリ
TODO:
連立線形合同
中国剰余定理
mod_fact
cCk mod p
...

合同式(modular equality)

二つの整数 $a,b$ , 自然数 $n$ について、
$(a-b) \bmod n = 0$ なら、
$a \equiv b \pmod{n}$ ,
( $a \bmod n = b \bmod n$ )
と書き、 $a,b$ が $n$ を法(modulus)として合同(congruent)という。
$0\leq a\bmod n < n$

${ \begin{cases} a \equiv b \pmod{n} \\ a' \equiv b' \pmod{n} \end{cases} \Rightarrow \begin{cases} a \pm a' \equiv b \pm b' \pmod{n} \\ aa' \equiv bb' \pmod{n} \end{cases} }$
$a \bmod b = a - \lfloor \frac{a}{b} \rfloor b$

上の性質より、加減乗除を組み合わせた合同演算では、途中に $\bmod n$ を自由に入れて良い。
実数の範囲では、除算(逆元)について閉じているが、合同演算では閉じていない。
例：
$a^5 \bmod n = (((a^2 \bmod n)^2 \bmod n)a)\bmod n$

a	:整数aを2進数で表現したときのビット長

とすると、上の例の左辺は5|a|の表現長だが、右辺は高々2|a|長の数しか出ない。

法mの下での逆元(inverse element)

法 $m$ の下での逆元 $a^{-1}$ は、拡張ユークリッドの互除法を用いて求めることができる。
$ax \equiv 1(\bmod m)$ は $ax = 1+mk$ となる $k$ が存在することと同値。
すなわち、 $ax - mk = 1$ となる $x$ が $a^{-1}$ .
$ax -mk \equiv 1 = gcd(a,m)$ $(\bmod m)$
$ax \equiv 1 = gcd(a,m)$ $(\bmod m)$
( $gcd(a,m)=1$ すなわち、 $a, m$ が互いに素なら逆元 $a^{-1}$ が存在する)

/**
 * Calculates modular multiplicative inverse(a^-1 mod m).
 * If a^-1 mod m doesn't exist(i.e. a is coprime to m), returns 0.<br>
 * O( log max(a,m) )<br>
 * @param a positive integer
 * @param m modulus
 * @return	a^-1 mod m.  0 -> a^-1 mod m doesn't exist.
 */
public static final int modInverse(int a, int m){
	int[] x = new int[2];
	return (extGCD(a, m, x) == 1) ? (x[0] + m) % m : 0;
}

オイラー(Euler)関数

自然数 $n$ に対して、
$Z_n ={ 0,1,2,\cdots , n-1 }$
$Z_n^*$ ={a:aとnは互いに素}
とする。
ここで、 $\phi (n) = |Z_n^*|$ をオイラーのトーシェント関数（Euler's totient function）(オイラーのφ関数、オイラー関数)という。
相異なる素数 $p,q$ に対して、
$\phi (p)=p-1$
$\phi (p^e)=p^{e-1}(p-1)$
$\phi (pq) = (p-1)(q-1)$
である。

nの素因数分解を使って、
$\phi (n = \prod_{i=1}^d p_i^{e_i}) = \prod_{i=1}^d \frac{p_i^{e_i}(p_i -1)}{p_i} = n \prod_{i=1}^d \frac{p_i -1}{p_i} \left (= \prod_{i=1}^{d} \phi (p_i^{e_i})\right )$
と表現できるため、
素数が見つかるたび(p-1)/pをかけるだけでオイラー関数の値が求まる。
nの素因数分解は $O(\sqrt{n})$ でできるので、 $\phi (n)$ も同じオーダーで求められる。
また、エラトステネスの篩の応用でオイラー関数の値のテーブルを作成できる。

//※C++
//オイラーのφ(n)を求める O(√n)
//n>0
int euler_phi(int n)
{
	int res = n;
	for(int i = 2; i*i <= n; ++i){
		if(n % i == 0){
			res = res / i * (i-1);
			while(n % i == 0) n/=i;
		}
	}
	if(n != 1) res = res / n * (n-1);
	return res;
}

//オイラーのφ(n)の値をテーブルeuler[n]で作成　O(n log log n)
//n>0 ※euler.size() == max_n + 1
void euler_phi_table(std::vector<int> &euler, int max_n)
{
	euler.resize(max_n+1);
	for(int i = 0; i < max_n+1; ++i) euler[i]=i;
	for(int i = 2; i < max_n+1; ++i){ 
		if(euler[i] == i){ //iは素数
			for(int j = i; j < max_n+1; j += i) //jは素数iの倍数
				euler[j]=euler[j]/i * (i-1);
		}
	}
}

オイラーの定理（Euler's theorem）(数論)

自然数 $n$ と $n$ に互いに素な自然数 $a$ に対し、
$a^{\phi (n)}\equiv 1\pmod{n}$
(証明)
１からｎまでの整数でｎと互いに素な数を $r_1, r_2, \cdots ,r_{\phi(n)}$ と表して、
更にこれらの数にそれぞれａを掛けたもの $ar_1, ar_2, \cdots, ar_{\phi (n)}$ を考える。
ａと $r_i$ がｎと互いに素なので， $ar_i$ とｎは互いに素。

$ar_i \equiv ar_j \pmod{n}$ ならば，ａのｎを法とする逆元をこの式の両辺に乗じて，
$r_i \equiv r_j \pmod{n}$ すなわち、 $i=j$ 。
したがって、 $ar_1, ar_2, \cdots, ar_{\phi (n)}$ は、それぞれ、nを法に合同ではない。

ｎと互いに素となる数は $r_1, r_2, \cdots, r_{\phi (n)}$ のどれか１つと合同になるので、
それを適当に順序を入れ替えたものが $ar_1, ar_2, \cdots, ar_{\phi (n)}$ とそれぞれ合同になる。
$\therefore ar_1 ar_2 \cdots ar_{\phi (n)} \equiv r_1 r_2 \cdots r_{\phi (n)} \pmod{n}$