Number Theory 2 요약

Number Theory 2 요약 === <style> .reveal { font-size: 28px; } </style> --- ## 12장: 소수의 무한성과 분포 ### Theorem: 무한 소수 정리 $$ \text{소수는 무한히 많다.} $$ 증명: ![](https://i.imgur.com/Z0RnyOp.png)  ---- ### Theorem: 3 (mod 4) 소수 정리 $$ p \equiv 3 \bmod{4} \text{형태의 소수 p는 무한히 많다.} $$ 증명: ![](https://i.imgur.com/ujeNNIH.png)  ---- ### Theorem: 1 (mod 4) 소수 정리 $$ p \equiv 1 \bmod{4} \text{형태의 소수 p는 무한히 많다.} $$ 증명: 21장에서 ---- ### Theorem: 디리클레(Dirichlet)의 등차수열 속 소수 정리 $$ gcd(a,m)\ =\ 1\ 일\ 때,\ a \bmod{m}\ 꼴인\ 소수는\ 무한히\ 많다. $$ 증명: 어려우니 생략 주목:  - $3 \bmod{4}$ 인 경우는 위에서 증명함 - $5 \bmod{6}$ 인 경우는 연습문제 12.2 - $1 \bmod{4}$ 인 경우는 21장에서.  --- ## 13장: 소수 세기 ### Definition: The Number of Primes $$ \pi(x) = |\lbrace p\ |\ p\ \le\ x\ 인\ 소수\ p \rbrace| $$ ![](https://i.imgur.com/jNxvA4N.png)  ---- ### Theorem: 소수 정리 $$ \lim_{x \to \infty}{\pi(x) \over {x \over \ln{x}}}=1 $$ --- ## 16장: 연속 제곱법 ### 예시 ![](https://i.imgur.com/ApIMpTT.png) ---- ### 계산량 비교 1. 직접 계산할 경우 327 - 1 = 326번의 곱셈 2. 연속 제곱법  a) 표 만드는데 $log_2{327} \le 9$ 번의 곱셈  b) 표를 이용해서 4번의 곱셈  - $n=a^k$일 때, worst case인 경우 총 $2log_2{k}$ 번의 곱셈 (a + b) 필요  ---- ### Definition: 연속 제곱법 ($a^k \bmod {m}$ 계산) 1. $k$를 2진수로 표현한다. $k = \sum_{i=0}^{i=r}{u_i2^i},\ u_i \in \lbrace 0, 1 \rbrace$  2. 법 m에 대해 a의 거듭제곱을 계산하여 다음의 표를 만든다  $$ \begin{aligned} a^1 && \equiv A_0 \bmod{m} \\ a^2 & \equiv (a^1)^2 \equiv A_0^2 & \equiv A_1 \bmod{m} \\ a^4 & \equiv (a^2)^2 \equiv A_1^2 & \equiv A_2 \bmod{m} \\ ... \\ a^{2^r} & \equiv (a^{2^{r-1}})^2 \equiv A_{r-1}^2 & \equiv A_{r} \bmod{m} \\ \end{aligned} $$  3. $a^k \equiv \prod_{i=0}^{i=r}{A_i^{u_i}} \bmod{m}$  ---- 증명: ![](https://i.imgur.com/A8NVBzK.png) ---- ### Application: 소수 판정 연속제곱법과 페르마의 소정리를 이용하여 소수를 판정할 수 있다. ![](https://i.imgur.com/CbsZFf5.png) ---- ### Definition: 카마이클 수 (Carmichael Number) $$ gcd(a, m) = 1\ 인\ 모든\ a에\ 대해\ a^{m-1} \equiv 1 \bmod{m}\ 을\ 만족하는\ 모든\ 자연수\ m $$ 가장 작은 카마이클수는 561 --- ## 20장 법 p에 대해 제곱인 수 20장 목표: 주어진 $p$에 대해 $\left(\dfrac{a}{p}\right)$를 계산하자. ![](https://i.imgur.com/XJVWcOT.png) ---- ### Definition: 이차 잉여 / 이차 비잉여 (Quadratic (Non-)Residue) $$ \bf{어떤}\ a에\ 대하여\ a^2 \equiv \bf{c} \bmod{p}\ 이면\ c를\ 법\ p에\ 대한\ 이차잉여라\ 부른다.\\ \bf{모든}\ a에\ 대하여\ a^2 \not\equiv \bf{c} \bmod{p}\ 이면\ c를\ 법\ p에\ 대한\ 이차비잉여라\ 부른다. $$ - $QR$ = 이차잉여 - $NR$ = 이차비잉여 ---- ### Theorem: ?? QR 갯수 $$ p가\ 홀수인\ 소수일\ 때,\ 법\ p에\ 대한\ 이차잉여와\ 이차비잉여의\ 갯수는\ (p-1)/2\ 로\ 같다. $$ ### Theorem: 이차잉여 곱셈 법칙 (버전 1) $$ QR \times QR = QR \\ NR \times QR = NR \\ NR \times NR = QR $$ ---- ### Definition: 르장드르 기호(Legendre Synbol) $$ p가\ 홀수인\ 소수이고,\ a \not\equiv 0 \bmod{p}\ 일\ 때, \\ a의\ 법\ p에\ 대한\ 르장드르\ 기호는 $$ \begin{equation} \left(\dfrac{a}{p}\right)= \left \{ \begin{aligned} &1 && \text{if}\ a\ is\ QR \\ &-1 && \text{if}\ a\ is\ NR \end{aligned} \right. \end{equation} ### Theorem: 이차잉여 곱셈 법칙 (버전 2 - 르장드르 기호)  $$ p가\ 홀수인\ 소수이고,\ a,b \not\equiv 0 \bmod{p}\ 일\ 때, \\ \left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right) = \left(\dfrac{ab}{p}\right) $$  --- ## 21장: -1은 어떤 법 p에 대해 제곱수일까? 2는? 20장 목표: 주어진 $p$에 대해 $\left(\dfrac{a}{p}\right)$를 계산하자. 21장 목표: $a= -1\ or\ 2$일 때 $\left(\dfrac{a}{p}\right)$를 계산하자. 질문: $x^2 \equiv -1 \bmod {p}$ 를 만족하는 $x$가 존재하는 $p$는 무엇일까?  - -1이 QR이 되게하는 p는 무엇인가?  - 어떤 소수 p에 대해 $x^2 \equiv -1 \bmod {p}$ 이 해를 가지는가?  - $\left(\dfrac{-1}{p}\right)=1$ 이 성립하는 소수 p는 무엇인가?  ---- ### Theorem: 법 4에 대해 -1과 합동인 소수 정리 (?) $$ 홀수인\ 소수\ p에\ 대하여 \\ \begin{equation} \left(\dfrac{-1}{p}\right)= \left \{ \begin{aligned} &1 && \text{if}\ p \equiv 1 \bmod{4} \\ &-1 && \text{if}\ p \equiv 3 \bmod{4} \end{aligned} \right. \end{equation} $$ 증명: TBD (오일러의 판정법 이용) ---- ### Definition: 오일러 판정법 $$ p가\ 홀수인\ 소수이면, \\ a^{(p-1)/2} \equiv \left(\dfrac{a}{p}\right) \bmod{p} $$ 참고: $a^{p-1} \equiv 1 \bmod{p}$ (페르마 소정리) 증명: (간략히)  $$ a^{p-1} \equiv 1 \bmod{p} \\ (a^{(p-1) \over 2} - 1)(a^{(p-1) \over 2} + 1) \equiv 0 \bmod{p} \\ a^{(p-1) \over 2} \equiv \pm 1 \bmod{p} \\ a^{(p-1) \over 2}= \left \{ \begin{aligned} &1 \bmod{p} & \text{if}\ a\ is\ QR \\ -&1 \bmod{p} & \text{if}\ a\ is\ NR \end{aligned} \right. $$  ---- #### Lemma: 오일러 판정법 ~ 가우스 방법? $$ 2^{(p-1)/2} \equiv (-1)^{\text{(음수 기호 개수)}} \bmod {p} \\ 음수 기호 개수 = |\lbrace a\ |\ 2 \le a \le (p-1),\ 2|a,\ a > {(p-1)\over2} \rbrace| $$ 증명:  ![](https://i.imgur.com/L5UTxnj.png)  ---- ### Theorem: 법 4에 대해 2와 합동인 소수 정리 (?) $$ 홀수인\ 소수\ p에\ 대하여 \\ \begin{equation} \left(\dfrac{2}{p}\right)= \left \{ \begin{aligned} &1 && \text{if}\ p \equiv \pm{1} \bmod{8} \\ &-1 && \text{if}\ p \equiv \pm{3} \bmod{8} \end{aligned} \right. \end{equation} $$ 증명:  ![](https://i.imgur.com/7J4dJSR.png)  --- ## 22장: 이차 상호 법칙 20장 목표: 주어진 $p$에 대해 $\left(\dfrac{a}{p}\right)$를 계산하자.  21장 목표: $a= -1\ or\ 2$일 때 $\left(\dfrac{a}{p}\right)$를 계산하자.  22장 목표: 일반화된 $\left(\dfrac{a}{p}\right)$ 계산하기  - a를 소인수분해하여 곱셈법칙을 적용하자  - 모든 소수 $a$에 대해 $\left(\dfrac{a}{p}\right)$를 계산한다면, <br/> 모든 정수 $a$에 대해 $\left(\dfrac{a}{p}\right)$를 계산할 수 있다.  ---- ### Definition: 이차 상호 법칙(law of quadratic reciprocity) 서로 다른 홀수 p, q에 대해 다음이 성립한다. 1) 21장에서 증명  \begin{equation} \left(\dfrac{-1}{p}\right)= \left \{ \begin{aligned} &1 && \text{if}\ p \equiv 1 \bmod{4} \\ &-1 && \text{if}\ p \equiv 3 \bmod{4} \end{aligned} \right. \end{equation}  2) 21장에서 증명  \begin{equation} \left(\dfrac{2}{p}\right)= \left \{ \begin{aligned} &1 && \text{if}\ p \equiv \pm{1} \bmod{8} \\ &-1 && \text{if}\ p \equiv \pm{3} \bmod{8} \end{aligned} \right. \end{equation}  3) 새로운 내용  \begin{equation} \left(\dfrac{q}{p}\right)= \left \{ \begin{aligned} &\left(\dfrac{p}{q}\right) && \text{if}\ p \equiv 1 \bmod{4} \textbf{ OR } q \equiv 1 \bmod{4} \\ -&\left(\dfrac{p}{q}\right) && \text{otherwise} \end{aligned} \right. \end{equation}  ---- 참고: $p \bmod{4} \in \lbrace 1,3 \rbrace,\ q \bmod{4} \in \lbrace 1,3 \rbrace$이기에, 둘 다 3인 경우 $-$부호가 붙는다 3번 증명: TBD ---- ### 예시 ![](https://i.imgur.com/HPJ8Urz.png) 이차상호법칙을 사용할 경우, a의 소인수 분해가 필수. 야코비 기호를 이용하자. ---- ### Definition: 야코비 기호 (Jacobi symbol) ~ 일반화된 르장드르 기호 $$ 모든\ 자연수\ a,\ b와\ 소수\ p_i에\ 대하여\ b = \prod_{i=0}^{i=r}{p_i}\ 일\ 때, \\ \left(\dfrac{a}{b}\right) = \prod_{i=0}^{i=r}{\left(\dfrac{a}{p_i}\right)} $$ 르장드르 기호와 동일한 $\left(\dfrac{}{}\right)$ 를 사용하지만, a가 법 b에 대해 QR이란 의미는 아님.  단순한 계산 편의성을 위한 다른 기호  ---- ### Definition: 일반화된 이차 상호 법칙 **모든 홀수** a, b에 대해 다음이 성립한다. (르장드르 기호 대신 야코비 기호) 1) -1 \begin{equation} \left(\dfrac{-1}{b}\right)= \left \{ \begin{aligned} &1 && \text{if}\ b \equiv 1 \bmod{4} \\ &-1 && \text{if}\ b \equiv 3 \bmod{4} \end{aligned} \right. \end{equation} 2) 2 \begin{equation} \left(\dfrac{2}{b}\right)= \left \{ \begin{aligned} &1 && \text{if}\ b \equiv \pm{1} \bmod{8} \\ &-1 && \text{if}\ b \equiv \pm{3} \bmod{8} \end{aligned} \right. \end{equation} 3) a-b 뒤집기 \begin{equation} \left(\dfrac{a}{b}\right)= \left \{ \begin{aligned} &\left(\dfrac{b}{a}\right) && \text{if}\ b \equiv 1 \bmod{4} \textbf{ OR } b \equiv 1 \bmod{4} \\ -&\left(\dfrac{b}{a}\right) && \text{otherwise} \end{aligned} \right. \end{equation} --- ## 27장. 오일러의 $\phi$ 함수와 약수들의 합 ~ 28장 증명에 이용 복습: $\phi(n) = |\{a | 1 <= a < n, gcd(a,n)=1\}|$ ---- ### Theorem: 오일러의 $\phi$ 함수 합 공식 $$ n의\ 모든\ 약수\ d1, ..., d_r\ 에\ 대해 \\ \sum_{i=0}^r \phi(d_i) = n $$ 증명: TBD ---- ## 28장. 법 p에 대한 거듭제곱과 원시근 복습: - 페르마의 소정리: $소수\ p와\ gcd(a,p) = 1인\ 정수\ a에\ 대해서\ a^{p-1} \equiv 1 (\bmod{p})$ ---- ### Definition: 원소의 위수 (order of element modulo p) $$ 법\ p에\ 대한\ a의\ 위수를\ e_p(a) = (a^m \equiv 1 (\bmod{p})를\ 만족하는\ 가장\ 작은\ 자연수\ \bf{m}) $$ - 단, $gcd(a,p) = 1$ 이어야 함  - $|a|$ 로 표기 하기도..  - 관찰:  - $1 <= e_p(a) <= p-1$  - $a^{e_p(a)} \equiv a^{p-1} \equiv 1 (\bmod{p})$ 이기에 $e_p(a) | p-1$ ~ 아래 정리의 따름 정리  ---- ### Theorem: 위수의 나눔 성질(Order Divisibility Property) $$ 정수\ a가\ 소수\ p와\ 서로소이고,\ a^n \equiv 1 (\bmod p)\ 일\ 때,\ e_p(a) | n\ 이다. $$ 증명(나눗셈 정리): $$ n = e_p(a)q + r\ (0 <= r < e_p(a))\ 일\ 때 \\ 1 \equiv a^n \equiv a^{e_p(a)q + r} \equiv (a^{e_p(a)q}a^r) \equiv 1^q a^r \equiv a^r (\bmod{p}) \\ r < e_p(a)\ 이지만,\ e_p(a)\ 의\ 최소성에\ 의해\ r = 0 \\ \therefore\ \bf{n = e_p(a)q,\ e_p(a) | n} $$  ---- ### Definition: 원시근 (primitive root modulo p) $$ e_p(a) = p-1\ 인\ 수\ a $$ ### Theorem: 원시근 정리 $$ 모든\ 소수\ p는\ 원시근을\ 정확히\ \phi(p-1)개\ 가진다. $$  증명: TBD  ---- 그렇다면 모든 원시근을 찾는 방법은? 1. brute-force 로 $gcd(a, p) = 1, a^{p-1} \equiv 1 \bmod{p}$ 인 $a$를 찾자.  2. $a^m$ 은 오직 $gcd(m, p-1)=1$ 일 때 $e_p(a^m)=p-1$ 이다.  - 그렇지 않다면 적당한 수 $k, mk<p-1$에 대해 $a^{mk} \equiv 1$ 이 될 수 있다. 4. 따라서 $a$를 제외한 원시근들은 $\{a^m | gcd(m, p-1) = 1\}$ 들이다.  증명: TBD  --- ## 끝