2025-01-21 기준 Number Theory #0 :: 소인수분해의 존재성과 유일성 #1 :: 피타고라스 삼원쌍 #2 :: 선형 디오판토스 방정식 #3-1 :: 합동 #3-2 :: 선형 합동 방정식 #3-3 :: 역원 #3-4 :: 고차방정식 #3-5 :: 중국인의 나머지 정리 #4-1 :: 페르마 소정리 #4-2 :: 오일러 정리 #4-3 :: 윌슨 정리 #5-1 :: 소수의 무한성 #5-2 :: 소수 정리 #5-3 :: 메르센 소수와 완전수 #5-4 :: 소수 판정법 #6 :: RSA #7 :: 수학적 귀납법 #8 :: 원시 근 (Pri..

Number systems $\begin{gather*}\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}\end{gather*}$">$\begin{gather*} \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \end{gather*}$ 자연수 ⊂ 정수 ⊂ 유리수 ⊂ 실수  대수적 수 (Algebraic number)정수 계수 다항방정식  $\begin{gather*}c_0x^d+c_1x^{d-1}+...+c_{d-1}x+c_d=0\end{gather*}$">$\begin{gather*} c_0x^d+c_1x^{d-1}+...+c_{d-1}x+c_d=0 \end..

Pell's equation in general제곱수가 아닌 n에 대하여 x^2 - ny^2 = 1의 양의 정수해가 존재한다.  $\begin{gather*}x+\sqrt{n}y=(a_1+b_1\sqrt{n})^k\end{gather*}$">$\begin{gather*} x+\sqrt{n}y=(a_1+b_1\sqrt{n})^k \end{gather*}$ for some k ≥ 1, where (a_1, b_1) is the fundamental solution.이때 a1, b1은 가장 밑바닥 해  무리수의 판별정리If α = a/b is a rational number, we have |qα - p| ≥ 1/b for any rational number p/q with (α ≠ p/q).무리수라면 좋은 ..

10진법 전개에 의한 √2의 유리수 근사:  $\begin{gather*}1.4, \ \ 1.41, \ \ 1.414, \ \ 1.4142, \ \ ...\end{gather*}$">$\begin{gather*} 1.4, \ \ 1.41, \ \ 1.414, \ \ 1.4142, \ \ ... \end{gather*}$ 유리수열 {r_n}에 대해 다음 부등식이 성립한다.  $\begin{gather*}|\sqrt2 -r_n| ">$\begin{gather*} |\sqrt2 -r_n|  이것은 수렴속도가 느리다. 펠 방정식 x_k^2 - 2y_k^2 = 1 의 해 x_k + y_k√2 = (3 + 2√2)^k에 대하여,  $\begin{gather*}(\frac{x_k}{y_k})^2-2=\frac{1}{..

사각-삼각수삼각수   $\begin{gather*}\frac{n(n+1)}{2}\end{gather*}$">$\begin{gather*} \frac{n(n+1)}{2} \end{gather*}$ 사각수 (= 제곱수)  $\begin{gather*}n^2\end{gather*}$">$\begin{gather*} n^2 \end{gather*}$ 사각수이면서 삼각수인 사각-삼각수는 무한할까?  Pell’s equation $\begin{gather*}n^2=\frac{m(m+1)}{2}\end{gather*}$">$\begin{gather*} n^2=\frac{m(m+1)}{2} \end{gather*}$ 를 만족하는 수를 찾자. x = 2m+1, y = 2n을 사용.   $\begin{gather*}x=2..

$\begin{gather*}x^4+y^4=z^4\end{gather*}$">$\begin{gather*} x^4+y^4=z^4 \end{gather*}$ 서로소인 양의 정수해는 없다.⇒ infinite descent (무한 강하법)을 사용하여 증명. Theorem $\begin{gather*}x^4+y^4=z^2\end{gather*}$">$\begin{gather*} x^4+y^4=z^2 \end{gather*}$ 서로소인 양의 정수해는 없다.⇒ z^4과 상호 호환됨.  Lemma - Primitve Pythagorean Triples $\begin{gather*}a^2+b^2=c^2 \\a=st, \ \ \ \ b=\frac{s^2-t^2}{2}, \ \ \ \ c=\frac{s^2+t^2}{2},..

정의1. the order of a mod n is the smallest k such that a^k ≡ 1 mod n    a^k ≡ 1 mod n을 만족하는 가장 작은 k를 order of a mod n이라고 한다.  $\begin{gather*}ord_na=k, \ \ \ \ (ord_na \leq\phi(n))\end{gather*}$">$\begin{gather*}ord_na=k, \ \ \ \ (ord_na \leq\phi(n)) \end{gather*}$ 2. a is a primitive root mod n ↔  $\begin{gather*}ord_na=\phi(n)\end{gather*}$">$\begin{gather*}ord_na=\phi(n) \end{gather*}$   를 만족한..

하노이의 탑하노이의 탑은 한쪽 기둥에 쭉 쌓여있는 원판들을 다른 쪽 기둥으로 하나씩 옮기는 문제이다. 이때 작은 원판 위에는 큰 원판을 올릴 수 없다.  하노이의 탑은 풀리는 문제일까? 1. 원판이 1개라면 그냥 자유롭게 옮길 수 있다. 즉, 풀린다.2. 원판이 n개일 때 풀린다고 가정한다면, n+1개일 때는 위쪽 n개의 원판을 B로 옮긴 다음에 제일 아래 원판을 C로 옮기고,B의 원판 n개를 C에 있는 제일 아래 원판 위로 올리면 된다.  n개의 원판을 옮기려면 몇 번 이동해야 할까? 필요한 이동 작업을 a_n이라 하자.  $\begin{gather*}a_{n+1}=a_n+1+a_n=2a_n+1 \\\end{gather*}$">$\begin{gather*}a_{n+1}=a_n+1+a_n=2a_n+1 \..

RSA 암호화 방법1. 엄청 큰 잘 알려지지 않은 소수 p, q의 곱 m을 구한다. (m = p*q)2. Φ(m) = (p-1)(q-1)3. Φ(m)과 서로소인 k를 구한다.4. 다음을 만족하는 l을 구한다.  $\begin{gather*}kl≡ 1 \mod \phi(m) \\\Rightarrow kl-\phi(m)y=1\end{gather*}$">$\begin{gather*}kl≡ 1 \mod \phi(m) \\ \Rightarrow kl-\phi(m)y=1 \end{gather*}$ public : m, k 공개해도 됨.Secret key : l 공개해선 안됨.Bank’s Secret : p, q, Φ(m) 공개해선 안됨.  암호화1. 평문을 표를 보고 숫자의 조합 M으로 바꾼다.2. M을 쪼개서 a..

거듭제곱 계산mod를 사용해서 간단하게 계산하자.  $\begin{gather*}7^{2000}\equiv7^{120}\equiv905*841*1225*449\equiv1761\end{gather*}$">$\begin{gather*}7^{2000}\equiv7^{120}\equiv905*841*1225*449\equiv1761 \end{gather*}$ Computational complexity일반적으로 a^n mod m을 계산하기 위해 곱셈을 log_2 n번 (n을 2진법으로 표현시의 자릿수)정도 하면 된다.  소수/합성수 판정법에라스토스테네스의 체n이하의 소수를 찾기 위해선 sqrt(n)이하의 소수에 의한 체로 걸러내자.ex) 100이하의 소수 : 10이하의 소수로만 거르기.  페르마 소정리를 이용..