Difference between revisions of "Definition:수의 합동"
| (One intermediate revision by the same user not shown) | |||
| Line 31: | Line 31: | ||
* 각 $n$에 대해서 $\{0,\ 1,\ \cdots,\ n-1\}$을 '''least residue system'''(표준 잉여계)이라 하고, 표준 잉여계의 원소와 합동인 원소가 하나씩 있는 집합을 '''complete residue system'''(완전 잉여계)이라고 한다. 모든 원소가 곱셈의 역원을 가지는, 각 원소가 서로 합동이 아닌 집합을 '''reduced residue system'''(기약 잉여계)라고 한다.<ref>https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems</ref> 유클리드 호제법에 따라서 $a'=bq+a$이면 $(a,\ b)=(a',\ b)$이므로 완전 잉여계에서 $n$과 서로소인 정수들만 남겨 놓은 집합은 기약 잉여계이다. 각 원소가 coset인 경우와 다르게, 각 원소가 정수인 residue system들은 유일하지 않다.<ref>https://math.stackexchange.com/questions/2288438/difference-between-mathbbz-n-mathbbz-and-mathbbz-n</ref> | * 각 $n$에 대해서 $\{0,\ 1,\ \cdots,\ n-1\}$을 '''least residue system'''(표준 잉여계)이라 하고, 표준 잉여계의 원소와 합동인 원소가 하나씩 있는 집합을 '''complete residue system'''(완전 잉여계)이라고 한다. 모든 원소가 곱셈의 역원을 가지는, 각 원소가 서로 합동이 아닌 집합을 '''reduced residue system'''(기약 잉여계)라고 한다.<ref>https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems</ref> 유클리드 호제법에 따라서 $a'=bq+a$이면 $(a,\ b)=(a',\ b)$이므로 완전 잉여계에서 $n$과 서로소인 정수들만 남겨 놓은 집합은 기약 잉여계이다. 각 원소가 coset인 경우와 다르게, 각 원소가 정수인 residue system들은 유일하지 않다.<ref>https://math.stackexchange.com/questions/2288438/difference-between-mathbbz-n-mathbbz-and-mathbbz-n</ref> | ||
* $(\Z/n\Z,\ +)$는 항등원이 $\overline{0}$인 quotient group이며 $n$과 서로소인 한 원소가 generate할 수 있는 cyclic group이다. | * $(\Z/n\Z,\ +)$는 항등원이 $\overline{0}$인 quotient group이며 $n$과 서로소인 한 원소가 generate할 수 있는 cyclic group이다. | ||
| − | * $((\Z/n\Z)^{\times},\ \cdot)$는 | + | * $((\Z/n\Z)^{\times},\ \cdot)$는 항등원이 $\overline{1}$인 group of units이다. 즉 $\Z/n\Z$에서 modular multiplicative inverse를 가지는 원소들을 모아 놓은 것이며, 이 군의 원소를 계량하는 함수 $\phi(n)=|(\Z/n\Z)^{\times}|$를 '''Euler's totient function'''(오일러 토션트 함수, 오일러 피 함수)라 한다. $n$이 소수 $p$이면 덧셈의 항등원이 아닌 모든 원소가 곱셈의 역원을 가지므로 $(\Z/n\Z,\ +,\ \cdot)$는 finite field $\F_p$와 동형이다. |
== 산술적 성질들 == | == 산술적 성질들 == | ||
Latest revision as of 13:31, 4 January 2023
$a-b$가 자연수 $n$으로 나누어떨어질 때 두 정수 $a,\ b$를 congruent modulo $n$(법 $n$에 대해서 합동)이라고 하고
- $a\equiv b\pmod n$
로 쓴다. congruence relation은 equivalence relation이기 때문에 residue class는 equivalence class이다. 예를 들어 $n=3$에서 나머지 집합은 각각 동치류이다.
- $\overline{0}=\{\cdots,\ -6,\ -3,\ 0,\ 3,\ 6,\ \cdots\},\ \overline{1}=\{\cdots,\ -5,\ -2,\ 1,\ 4,\ 7,\ \cdots\},\ \overline{2}=\{\cdots,\ -4,\ -1,\ 2,\ 5,\ 8,\ \cdots\}$
따라서 정수 전체를 분할하는 quotient set $\Z/3\Z=\{\overline{0},\ \overline{1},\ \overline{2}\}$를 구성할 수 있다. modulo $n$에서 이를 ring of integers modulo $n$이라고 하고 $\Z/n\Z$으로 쓴다. 이 위에서의 사칙연산을 modular arithmetic(합동 산술, 모듈러 산술)이라 하고 $n$은 modulus가 된다.
Euclidean algorithm
$a\equiv r\pmod b$이고 $0\leq r<b$이면 $a,\ b$의 최대공약수와 $r,\ b$의 최대공약수는 같다. 즉 $a=bq+r$로 나타낼 수 있다면 두 수의 최대공약수를 $g=(a,\ b)$로 쓸 때 $g=(b,\ r)$이다. 이를 Euclidean algorithm(유클리드 호제법, 유클리드 알고리즘)이라 하며, 증명은 다음과 같다: $ga'=gb'q+r$이기 때문에 $r=gr'$이어야 한다. 따라서 $g=(a,\ b)$는 $(b,\ r)$의 약수이다. $h=(b,\ r)$라 쓰면 $a=hb''q+hr''$이기 때문에 $a=ha''$이어야 한다. 따라서 $h=(b,\ r)$는 $(a,\ b)$의 약수이고, $g=h$이다. 이 결과를 재귀적으로 적용하다 보면 $r=0$이 되며, 이때 $b$가 두 수의 최대공약수이다.
$ax\equiv r\pmod b$를 만족하는 $x$는 $r$이 $g=(a,\ b)$의 배수일 때에만 찾을 수 있다. 즉 $y$를 도입하여 $ax+by=r$로 나타낼 수 있다면 $r=g$인 경우에 각 $q$를 공유하여 $x,\ y$를 계산할 수 있다:
- $\begin{cases} a&=bq_1&+r_1\\ b&=r_1q_2&+r_2\\ r_1&=r_2q_3&+r_3\\ &\cdots&\\ r_{n-2}&=r_{n-1}q_n&+r_n=(a,\ b)q_n+0\end{cases},\ \begin{cases} 1&=0q_1&+x_1\\ 0&=x_1q_2&+x_2\\ x_1&=x_2q_3&+x_3\\ &\cdots&\\ x_{n-2}&=x_{n-1}q_n&+x_n=xq_n+x_n\end{cases},\ \begin{cases} 0&=1q_1&+y_1\\ 1&=y_1q_2&+y_2\\ y_1&=y_2q_3&+y_3\\ &\cdots&\\ y_{n-2}&=y_{n-1}q_n&+y_n=yq_n+y_n\end{cases}$
모든 $r_i$에 대해서 $r_1=1a+(-q_1)b,\ r_2=(-q_2)a+(1+q_1q_2)b,\ r_3=(1+q_2q_3)a+(-q_1-q_3-q_1q_2q_3)b,\ \cdots,\ r_i=x_ia+y_ib$가 성립한다. 이를 extended Euclidean algorithm(확장 유클리드 알고리즘)이라고 하며, 식 $ax+by=(a,\ b)$을 만족하는 $x,\ y$가 존재한다는 사실을 Bézout's identity(베주 항등식)라고 한다. 확장 유클리드 알고리즘은 원점에 가장 가까운 coefficients $(x,\ y)$를 알려 주고, 나머지 coefficients들은 $\displaystyle \left(x-\frac{b}{(a,\ b)}n,\ y+\frac{a}{(a,\ b)}n\right)$로 쓸 수 있다.[1]
Chinese remainder theorem
linear Diophantine systems of equations
- $x\equiv a_1\pmod {n_1},\ x\equiv a_2\pmod {n_2},\ \cdots,\ x\equiv a_k\pmod {n_k}$
를 만족하는 해는 각 $n_i$들이 서로소일 때 modulo $n_1n_2\cdots n_k$에서 유일하게 존재한다. $n_i$로 나눈 나머지가 $1$이면서 다른 modulo들로는 모두 나누어떨어지는 수 $b_i$를 각 modulo마다 구해 놓으면 $x\equiv a_1b_1+\cdots+a_kb_k\pmod {n_1\cdots n_k}$이다. 따라서 $n$의 소인수 분해 $p^a\cdots q^b$에 대해서 isomorphism $\Z/n\Z\cong (\Z/p^a\Z)\times\cdots\times(\Z/q^b\Z)$를 정의할 수 있고, 이를 Chinese remainder theorem, CRT(중국인의 나머지 정리)이라고 한다.
알고리즘으로 만드는 방법
$(n_1,\ n_2)=1$이므로 Bézout's identity가 $n_1n_1^{-1}+n_2n_2^{-1}=1$이다. extended Euclidean algorithm을 써서 arithmethic inverse
- $n_1^{-1}\pmod{n_2},\ n_2^{-1}\pmod{n_1}$
를 계산하면 이 항등식을 $N_1+N_2=1$로 쓸 때 $N_1$은 $n_1$로 나누어떨어지지만 $n_2$로 나눈 나머지가 $1$이고, $N_2$는 $n_2$로 나누어떨어지지만 $n_1$로 나눈 나머지가 $1$이다. 따라서
- $x\equiv a_1N_2+a_2N_1\pmod{n_1n_2}$
는 처음의 두 식에 대한 해이고, 그 다음 식과 같은 과정을 반복할 수 있다. 이렇게 $n$과 서로소인 $a$에 대해서 $aa^{-1}\equiv 1\pmod n$인 $a^{-1}$를 $n$에 대한 $a$의 modular multiplicative inverse라고 한다.
대수적 성질들
- 각 $n$에 대해서 $\{0,\ 1,\ \cdots,\ n-1\}$을 least residue system(표준 잉여계)이라 하고, 표준 잉여계의 원소와 합동인 원소가 하나씩 있는 집합을 complete residue system(완전 잉여계)이라고 한다. 모든 원소가 곱셈의 역원을 가지는, 각 원소가 서로 합동이 아닌 집합을 reduced residue system(기약 잉여계)라고 한다.[2] 유클리드 호제법에 따라서 $a'=bq+a$이면 $(a,\ b)=(a',\ b)$이므로 완전 잉여계에서 $n$과 서로소인 정수들만 남겨 놓은 집합은 기약 잉여계이다. 각 원소가 coset인 경우와 다르게, 각 원소가 정수인 residue system들은 유일하지 않다.[3]
- $(\Z/n\Z,\ +)$는 항등원이 $\overline{0}$인 quotient group이며 $n$과 서로소인 한 원소가 generate할 수 있는 cyclic group이다.
- $((\Z/n\Z)^{\times},\ \cdot)$는 항등원이 $\overline{1}$인 group of units이다. 즉 $\Z/n\Z$에서 modular multiplicative inverse를 가지는 원소들을 모아 놓은 것이며, 이 군의 원소를 계량하는 함수 $\phi(n)=|(\Z/n\Z)^{\times}|$를 Euler's totient function(오일러 토션트 함수, 오일러 피 함수)라 한다. $n$이 소수 $p$이면 덧셈의 항등원이 아닌 모든 원소가 곱셈의 역원을 가지므로 $(\Z/n\Z,\ +,\ \cdot)$는 finite field $\F_p$와 동형이다.
산술적 성질들
$a\equiv b\pmod n$일 때 다음이 성립한다.
- $a+k\equiv b+k\pmod n,\ ka\equiv kb\pmod n,\ a_1a_2\equiv b_1b_2\pmod n$
- 음이 아닌 정수 $k$에 대해서 $a^k\equiv b^k\pmod n$이다.
$\gcd(a,\ n)=1$일 때 다음이 성립한다.
- $a^{\phi(n)}\equiv 1\pmod n$이다. 이를 Euler's theorem(오일러의 정리)이라고 한다.
- $a\equiv b\pmod n$이면 $a^{-1}\equiv b^{-1}\pmod n$이다.
- $a^{-1}\equiv a^{\phi(n)-1}\pmod n$
- $ax\equiv b\pmod n$이면 $x\equiv a^{-1}b\pmod n$이다.
$\gcd(k,\ n)=1$일 때 다음이 성립한다.
- $ka\equiv kb\pmod n$이면 $a\equiv b\pmod n$이다.
- $a\equiv b\pmod{\phi(n)}$이면 $k^a\equiv k^b\pmod n$이다.
$p$가 소수일 때 다음이 성립한다.
- $p$가 소수라는 것은 $(p-1)!\equiv -1\pmod p$와 동치이다. 이를 Wilson's theorem(윌슨의 정리)이라고 한다.
- $a^p\equiv a\pmod p$이다. 이를 Fermat's little theorem(페르마의 소정리)이라고 한다.
- $a_0\not\equiv 0\pmod p$이면 $a_0x^n+a_1x^{n-1}+\cdots+a_n\equiv 0\pmod p$의 해의 개수는 $n$ 이하이다. 이를 수론에서의 Lagrange's theorem(라그랑주의 정리)이라고 한다.
