1. 합동식
1-1. 합동과 나머지
가약성은 수론에서 엄청나게 강력한 도구이다. 이러한 가약성을 다르게 설명하는 방법이 있다. 바로 합동이다.
$m$이 $a-b$를 나눌 때, 즉 $m|(a-b)$ 일때, $a$와 $b$가 법 $m$에대해 합동이다 라고 한다. 그리고 이를
로 표기한다.
예를 들어, $a$를 $m$으로 나눈 나머지가 $r$이면, $a \equiv r\pmod{m}$가 성립한다. 즉 합동을 통해 가약성 이론을 방정식 처럼 표현할 수 있게되는 것이다.
1-2. 합동의 성질
- $a \equiv b \pmod{m}$이면, $a \pm c\equiv b\pm c \pmod{m}$이다.
- $a \equiv b \pmod{m}$이면, $ac \equiv bc \pmod{m}$이다.
- $(a,m)=1$인 경우에만, $ac \equiv bc \pmod{m}$ 이면 $a \equiv b \pmod{m}$이다.
1, 2, 3 모두, 합동이면 $m|(a-b)$라는 성질을 활용하면 쉽게 증명할 수 있다.
1-3. 일차 합동방정식의 풀이
합동방정식의 풀이도 일반 방정식과 크게 다르지 않다. 덧셈과 뺄셈, 곱셈, 그리고 조건에 따라 나눗셈도 허용이 되기 때문에, 이를 잘 활용하여 풀면 된다.
그러나 해가 언제나 존재하는 것은 아니다. 합동방정식 $ax \equiv c \pmod{m}$이 있을 때, 해가 존재할 조건은 $(a,m)|c$이다. 이는 선형 방정식 $ax + by = c$의 해가 존재할 조건이 $(a,b)|c$임과 동치이다.
해를 구하는 방법은 크게 두 가지 방법이 있다.
- 유클리드 호제법
- $ax \equiv c \pmod{m}$에서 $d=(a,m)$을 구한다.
- $a_1=a/d$, $c_1=c/d$, $m_1=m/d$를 계산한다.
- 유클리드 호제법으로 $a_1 x + m_1 y = c_1$의 특수해, $x_0$를 구한다.
- 법 $m_1$을 법 $m$으로 확장시키면, 일반해 $x \equiv x_0, \ x_0+m_1, \ ….\ \ x_0+(d-1)m_1$을 구할 수 있다.
- 역원을 사용해서
- 위와 동일하게, $a_1x \equiv c_1 \pmod{m_1}$으로 변형시킨다.
- 법 $m_1$에 대한 $a_1$의 역원 $a_1^* $을 구한다.
- $a_1^* \cdot a_1x \equiv x \equiv a_1^* \cdot c_1 \pmod {m_1}$을 통해 특수해를 구한다.
- 위와 동일하게 법 $m_1$을 법 $m$으로 확장시킨다.
2에서 역원이 존재함은 $(a_1,m_1)=1$이기 때문이다.
즉, 해는 $ (a,m) |c $ 일 때 존재하고, 해의 개수는 $(a,m)$이다.
2. 합동에 대한 정리들
2-1. 나머지 집합
$\mathbb{Z}/{n\mathbb{Z}}:= [0, 1, 2, 3, …. \ n-1]$을 나머지 환, 즉 $n$으로 나눈 나머지들만 모아 둔 집합이라고 정의하자.
이와 유사하게, $(\mathbb{Z}/{n\mathbb{Z}})^x := [k \in \mathbb{Z}: \ 0<k<n, (k,n)=1]$, 즉 역원이 존재하는 원소만 모아둔 나머지 환이라고 정의하고자 한다. 예를 들어 $(\mathbb{Z}/{6\mathbb{Z}})^x := [1, 5]$이다.
소수인 $p$의 경우, $\mathbb{Z}/{p\mathbb{Z}} = (\mathbb{Z}/{p\mathbb{Z}})^x$임을 생각해볼 수 있을 것이다.
이를 통해서 합동에 대한 몇가지 정리들을 증명하고자 한다.
2-2. 윌슨의 정리
윌슨의 정리:
\[(p-1)! \equiv -1\pmod p\]증명.
$a \in (\mathbb{Z}/{p\mathbb{Z}})^x$에 대해 $a=a^* $인 $a$를 생각해보자.
$a^2\equiv 1\pmod p$이므로, $(a-1)(a+1)\equiv 0 \pmod p$이고, $p|(a-1)(a+1)$이 성립한다.
$p$가 소수이므로, $p|a-1$ 또는 $p|a+1$이다. 즉, $a\equiv1 \pmod p$ 또는 $a \equiv -1 \pmod p$이다.
즉 $(\mathbb{Z}/{p\mathbb{Z}})^x$에서 $1$과 $p-1$를 제외하고는, 역수끼리 서로를 짝 지어줄 수 있다.
$(p-1)! = 1 \cdot (p-1) \cdot (b \cdot b^* ) \cdot (c \cdot c^* ) \cdot\cdot\cdot \equiv 1\cdot(-1)\cdot1\cdot1\cdot\cdot\cdot\equiv-1\pmod p$가 성립한다.
2-3 페르마의 소정리
페르마의 소정리:
\[a^{(p-1)}\equiv1\pmod p \ \ \ if \ p \ is \ prime \ and \ (a,p)=1\]증명.
$(\mathbb{Z}/{p\mathbb{Z}})^x$의 원소에 $a$를 모두 곱해주어도 결국 $(\mathbb{Z}/{p\mathbb{Z}})^x$와 같은 집합이다.
이는 만약 $1\leq k,j \leq p$ 일때, $ka \equiv ja\pmod p$이면, $k=j$임을 통해 증명할 수 있다. $p|a(k-j)$이면 $p|a$ 또는 $p|k-j$인데, $(a,p)=1$이고 $-1+p<k-j<p-1$이므로 $p\nmid a$ 이고 $p\nmid k-j$에 따라 $k=j$이 참이다.
따라서 $(p-1)! \equiv a\cdot 2a \cdot\cdot\cdot (p-1)a \pmod p$이 성립하고, $(p-1)!$의 역수가 존재하므로, 양변에 $(p-1)!$을 곱하면, $a^{(p-1)}\equiv1\pmod p$가 된다.
이 정리를 통해, 매우 효율적으로 어떤 수의 소수 여부를 판별할 수 있다. $n$이 어떤 $a$에 대해 $a^{(n-1)}\not\equiv 1\pmod n$라면, $n$은 반드시 합성수이다. 반면, 페르마의 소정리의 역은 성립하지 않으므로, $(a,n)=1$인 모든 $a$에 대해 $a^{(n-1)}\equiv 1\pmod n$ 가 성립한다고 하더라도, $n$은 높은 확률로 소수라고 말할 수 있을 뿐이지, 반드시 소수는 아니다. 이렇게 페르마의 소정리를 활용한 소수판정법을 뚫는 수를 카마이클 수라고 한다.
2-4 오일러 정리
오일러 정리:
\[a^{\phi(n)} \equiv 1 \pmod n \ \ \ if \ (a,n)=1, \ \ \phi(n)=\sharp[(\mathbb{Z}/{n\mathbb{Z}})^x]\]페르마의 소정리와 엄청 비슷하게 생겼다. 왜냐하면 페르마의 소정리를 소수 뿐만이 아닌 모든 정수로 확장시킨 것이 오일러 정리이기 때문. $n$에 소수를 대입해도 그대로 잘 작동한다. 증명과정도 거의 동일하므로 생략하고자 한다.
이 정리를 통해, $\phi(n)$의 값을 알고 있다면, modular exponention을 엄청 간단하게 바꿀 수 있다. 예를 들어, $3^{121}\pmod{10}$을 계산한다고 하자. $3^{4} \equiv 1\pmod{10}$이므로, $3^{121} \equiv 3^{4\cdot30\cdot1} \equiv 3\pmod{10}$임을 쉽게 계산할 수 있다. 문제는 $\phi(n)$의 값을 계산할 줄 알아야 한다는 점인데, 지금부터 알아보도록 한다.
3. 오일러함수 $\phi(n)$
3-1. $\phi(n)$
오일러 함수 $\phi(n)$를 어떻게 하면 쉽게 계산할 수 있을까?
우선 소수의 경우, $\phi(p)=p-1$임은 간단하다. 그리고 이를 활용하면, $\phi(p^r)$도 쉽게 구할 수 있다. $1\leq a \leq p^r$인 $a$에 대해 $(a,p)\neq1$인 $a$는 $p|a$를 만족한다. 즉 $p, \ 2p, \ 3p, … \ p^{r-1}\cdot p$ 이며 $p^{r-1}$개 존재한다. 따라서
이다.
그렇다면 일반적인 합성수, $m=p_1^{r_1}\cdot p_2^{r_2}\cdot p_3^{r_3}\cdot p_4^{r_4}\cdot\cdot\cdot p_k^{r_k}$에 대한 $\phi(m)$은 어떻게 계산할까.
3-2. 나머지 집합의 구조
위에서 나머지 집합 $(\mathbb{Z}/{n\mathbb{Z}})$을 정의하였다. 여기서 가장 중요한 포인트는,
\[(\mathbb{Z}/{mn\mathbb{Z}}) \simeq (\mathbb{Z}/{m\mathbb{Z}}) \times (\mathbb{Z}/{n\mathbb{Z}}) \ \ if \ (m,n)=1\]라는 것이다.
즉, $(\mathbb{Z}/{mn\mathbb{Z}})$의 원소를 $(\mathbb{Z}/{m\mathbb{Z}})\times (\mathbb{Z}/{n\mathbb{Z}})$의 원소로 일대일 대응이 존재한다는 것이다.
예를 들어 $m=3, \ n=5$일때, $7\rightarrow(1,2)$가 존재하고, $3\leftarrow (0,3)$이 존재한다.
만약 이것이 참이라면, 이를 통해 다음 식 또한 참임을 알 수 있다.
3-3 중국인의 나머지 정리
일대일 대응이 존재한다는 것은, 다음과 동치이다.
- 첫번째 집합에서 서로 다른 수를 고르면, 두번째 집합에서 서로 다른 순서쌍에 대응된다.
- 두번째 집합의 모든 순서쌍은 이에 대응되는 첫번째 집합의 수를 찾을 수 있다.
1번의 증명은 어렵지 않으니 생략하고자 한다.
2번의 증명은 중국인의 나머지 정리를 통해 증명할 수 있다.
중국인의 나머지 정리:
\[x\equiv b\pmod m \ and \ x\equiv c\pmod n \\ has \ unique \ solution \ \ if \ (m,n)=1\]이는
- $x=my+b$로 둔다.
- $my \equiv c-b \pmod n$의 유일 해를 구할 수 있다.
를 통해 쉽게 증명할 수 있다.
따라서 $\phi(mn) = \phi(m)\cdot\phi(n) \ \ if \ (m,n)=1$이 성립한다.
3-4 $\sum_{d|n}\phi(d) = n$의 증명
두 가지의 증명법이 있다.
- $n$이 소수일 때를 base case로서 증명하고, 이를 일반화하는 방법
- $\sum_{d|n}\phi(d) = \sum_{d|n}\phi(n/d)$임을 활용하는 방법
1번은 $\phi$의 곱셈 성질을 사용하면 간단하기 때문에, 2번의 방법을 설명하고자 한다.
$1 \sim n$까지의 정수를, n의 약수들, $d_1, \ d_2, \ …\ , \ d_r$의 배수들로 분류해보고자 한다. 즉, $(n,a)=1$인 a의 집합, $(n,a)=d_1$인 a의 집합, … $(n,a)=n$인 a의 집합, 즉 $n$의 약수 만큼의 집합으로 나눈다. 이들 집합은 교집합이 없고, 전부 합치면, 다시 $1 \sim n$의 수가 된다.
$(n,a)=d_i$인 a의 집합을 $A_{di}$라고 하자. 주장하고 싶은 것은, $\sharp A_{di} = \phi(n/d_i)$라는 것이다.
$A_{di} = [d_ik: \ 1\leq k \leq n/d_i]$라고 다시 표현할 수 있다. 이 집합은 $(d_i,n)=d(k,n/d_i)=d_i$, 즉 $(k,n/d_i)=1$를 만족해야하고, 이는 $\sharp A_{di} = \phi(n/d_i)$가 참임을 증명한다.
4. 원시근 정리
4-1 원시근
$(\mathbb{Z}/{p\mathbb{Z}})^x$의 흥미로운 점은, $(\mathbb{Z}/{p\mathbb{Z}})^x$의 어떤 원소 $a$를 제곱함을 통해 $(\mathbb{Z}/{p\mathbb{Z}})^x$의 모든 원소를 얻을 수 있다는 점이다. 예를 들어 $p=5$인 경우, $2^1, 2^2, 2^3, 2^4$를 통해 $(\mathbb{Z}/{p\mathbb{Z}})^x$의 모든 원소를 표현할 수 있다.
이런 원소 $a$를 원시근이라고 하고, $a^i \not \equiv1\pmod p \ \ if \ 1\leq i < p-1$이라고 정의한다. 이는 $i<p-1$ 일때 $a^i \equiv 1\pmod p$이면 순환이 생긴다는 점에서 자연스럽게 받아들일 수 있다.
4-2 위수의 성질
법 $p$에 대한 $a$의 위수를 $ord_p(a)$라고 표기하기로 약속하고, 다음과 같이 정의한다.
\[ord_p(a) = [a^i\equiv 1\pmod p를 만족하는 최소의 i]\]즉 $a$가 $p$의 원시근이 되기 위해서는, $ord_p(a)=p-1$이 되어야한다.
이와 같은 위수에는 성질이 있는데,
- $ord_p(a)\leq p-1$
- $ord_p(a)|n, \ \ if \ a^n \equiv \pmod p$
1번은 페르마의 소정리를 통해 쉽게 증명할 수 있다.
2번은 나눗셈 정리를 통해 증명할 수 있다. 특히, 이를 통해 $ord_p(a)|p-1$임을 알 수 있다.
4-3 원시근 정리와 증명
원시근 정리:
\[모든 \ 소수 \ p는 \ \phi(p-1)개의 \ 원시근을 \ 가진다.\]도움 정리. 법 $p$에 대한 다항식의 근의 정리
\[f(x)=a_0x^d + a_1x^{d-1} + \cdot\cdot\cdot +a_d에 \ 대하여 \ p\nmid a_0을 \ 만족하면 \\ f(x)\equiv0\pmod p은 \ 최대 \ d개의 \ 서로 \ 다른 \ 해를 \ 가짐\]이 도움 정리는 귀류법을 사용하면 어렵지 않게 증명할 수 있다.
이를 활용하여, 원시근 정리를 증명하고자 한다.
우선, $p-1 = nk$라고 하면, $X^{p-1}-1=X^{nk}-1=(X^n-1)((X^n)^{k-1} + (X^n)^{k-2} + \cdot\cdot\cdot+X^n + 1)$와 같이 인수분해 할 수 있다.
한편, 페르마의 소정리로 부터 $X^{p-1}-1\equiv 0\pmod p$은 정확히 $p-1$개의 해를 가짐을 알고있다. 따라서, 다음 주장은 참이 된다.
한편, $\psi(d) = \sharp[a: \ 1\leq a<p \ \ and \ \ ord_p(a) = d]$ 를 정의하고자 한다. 이를 통해 $ X^n-1\equiv 0\pmod p$의 근을 다른 방식을 세어보자.
만약 $X=a$가 근이라면, $a^n\equiv 1 \pmod p$가 성립하고, 위수의 2번째 성질에 따라 $ord_p(a)|n$이 성립한다. 따라서, 반대로 $n$의 모든 약수 $d_1, \ d_2, \ …\ , \ d_r$에 대해, $\psi(d_1) + \psi(d_2) + \cdot\cdot\cdot + \psi(d_r)$가 $ X^n-1\equiv 0\pmod p$의 근의 개수가 된다.
마지막으로, $\sum_{d|N}\phi(d) = N$임을 통해,
귀납적 가정을 사용하여 \(\phi = \psi\)를 증명하면, 원시근 정리의 증명은 끝이다.