Twin Prime Conjecture2만큼 차이나는 소수 쌍은 무한할까?ex) (3, 5), (5, 7), (11, 13), …Primes are randomly distributed소수는 규칙성이 없다. ⇒ 증명 안됨.  Mersenne Prime $\begin{gather*}2^p-1\end{gather*}$">$\begin{gather*}2^p-1 \end{gather*}$ 위와 같은 소수를 메르센 소수라고 한다.ex) 2^2 - 1 = 32^3 - 1 = 7…2^11 - 1 = 2047 = 23 * 89⇒ 2^p - 1이 항상 소수가 되는 것은 아님.Are there infinitely many mersenne prime? : 증명 안됨.  Euclid’s perfect number formul..

Prime number Theorem $\begin{gather*}\Pi(n) := n보다 \ \ 작은 \ \ 소수의 \ \ 개수\end{gather*}$">$\begin{gather*}\Pi(n) := n보다 \ \ 작은 \ \ 소수의 \ \ 개수 \end{gather*}$ ex)π(10) = 4π(20) = 6π(30) = 8… $\begin{gather*}\lim_{n\rightarrow\infty}\Pi(n)=\infty\end{gather*}$">$\begin{gather*}\lim_{n\rightarrow\infty}\Pi(n)=\infty \end{gather*}$⇒ 소수는 정수 전체에서 얼마 정도의 크기일까?  $\begin{gather*}\lim_{n\rightarrow\infty}{\f..

Prime numberPrime factorization (소인수 분해) 소인수분해의 존재성과 유일성"> 소인수분해의 존재성과 유일성  $\begin{gather*}n=p_1^{k_1}p_2^{k_2}...p_l^{k_l}\end{gather*}$">$\begin{gather*}n=p_1^{k_1}p_2^{k_2}...p_l^{k_l} \end{gather*}$  Euclid TheoremThere are infinitely many primes소수는 유한하지 않다. 증명 (귀류법)소수는 유한하다고 가정하면 모든 소수가 들어있는 소수의 리스트를 구할 수 있다.  $\begin{gather*}p_1,p_2,...,p_r\end{gather*}$">$\begin{gather*}p_1,p_2,...,..

Wilson’s Theorem $\begin{gather*}(p-1)!\equiv -1 \mod p\end{gather*}$">$\begin{gather*}(p-1)!\equiv -1 \mod p \end{gather*}$ ex) $\begin{gather*}4!=4\cdot3\cdot2\cdot1\equiv-1\mod 5\end{gather*}$">$\begin{gather*}4!=4\cdot3\cdot2\cdot1\equiv-1\mod 5 \end{gather*}$4 ≡ -1 mod 53 * 2 ≡ 1 mod 5 ⇒ inverse of mod 5⇒ 4! ≡ -1 mod 5  증명 추측) 1, p-1을 제외한 나머지 곱은 서로 다른 둘씩 짝을 지어서 inverse를 만족.⇒ 당연히 걔네는 self in..

Euler’s theorem오일러 정리 = 페르마 소정리의 일반화.  $\begin{gather*}\gcd(a,k)=1\end{gather*}$">$\begin{gather*}\gcd(a,k)=1 \end{gather*}$  $\begin{gather*}a^{\phi(k)}≡1 \mod k\end{gather*}$">$\begin{gather*}a^{\phi(k)}≡1 \mod k \end{gather*}$Φ(k) : Euler phi Function{1, 2, … ,(k-1)} 중 k와 서로소인 원소의 개수.이때 gcd(a, k) = 1이므로 a로는 그 서로소인 원소들만 될 수 있다.k : prime인 경우엔? Φ(p) = p - 1 당연히 1 ~ p-1 전부 p와 서로소이기 때문. ⇒ 페르마 소정리...

Fermat’s little theorem $\begin{gather*}p : prime, \ \ \ \ p\not{|}a\end{gather*}$">$\begin{gather*}p : prime, \ \ \ \ p\not{|}a \end{gather*}$  $\begin{gather*}a^{p-1} ≡ 1 \mod p\end{gather*}$">$\begin{gather*}a^{p-1} ≡ 1 \mod p \end{gather*}$ 이때 a의 후보로는 1, …, p-1중에 가능. (p와 서로소) ex)a와 a - p가 mod p로 같다는 점을 이용하여 간소화 한다. $\begin{gather*}3^6=(3^2)^3=9^3 \mod 7 \\\Rightarrow 2^3 = 8 ≡1 \mod 7\end{ga..

Chinese remainder theorem $\begin{gather*}\gcd(m,n)=1 \end{gather*}$">$\begin{gather*}\gcd(m,n)=1 \end{gather*}$  $\begin{gather*}\begin{cases}x \equiv a \mod m \\x \equiv b \mod n \end{cases}\end{gather*}$">$\begin{gather*} \begin{cases} x \equiv a \mod m \\ x \equiv b \mod n \end{cases} \end{gather*}$ 위 연립 방정식의 해는 mod mn에서 유일하게 존재한다.  증명 및 풀이과정 $\begin{gather*}x ≡ a \mod m \\\Rightarrow x=my+a..

Lagrange’s Theorem $\begin{gather*}f(x)=a_0x^d+a_1x^{d-1}+...+a_{d-1}x+a_d\end{gather*}$">$\begin{gather*}f(x)=a_0x^d+a_1x^{d-1}+...+a_{d-1}x+a_d \end{gather*}$d ≥ 1, a0 ≠ 0즉, d차 방정식. (a와 x의 차수 순서 주의!) $\begin{gather*}If \ \ p\not{|} a_0, \ \ then \ \ f(x) \equiv 0 \mod p \\has \ \ of \ \ most \ \ d \ \ distinct \ \ solutions \ \ mod \ \ p\end{gather*}$">$\begin{gather*}If \ \ p\not{|} a_0, \ \ ..

gcd(a, m)=1인 경우 ax ≡ c mod m은 유일한 해만 존재한다.gcd = 1이므로 당연히 해 1개. (ax - my = c)⇒ 마치 나눗셈이 가능한 것처럼 이해 가능. (실제로 나눗셈이 가능한 건 아님!!)  $\begin{gather*}7x \equiv 1 \mod 15 \\\Rightarrow x \equiv 1 *\frac{1}{7} \mod 15 \\\Rightarrow x \equiv 13 \mod 15 \\\Rightarrow \frac{1}{7} \equiv 13\end{gather*}$">$\begin{gather*}7x \equiv 1 \mod 15 \\ \Rightarrow x \equiv 1 *\frac{1}{7} \mod 15 \\ \Rightarrow x \equiv ..

Linear congruence equation $\begin{gather*}a\equiv b\mod m\end{gather*}$">$\begin{gather*}a\equiv b\mod m \end{gather*}$ 위를 만족하는 x를 구하기 위해선  $\begin{gather*}\Leftrightarrow ax-c=my \ \ \ \ for \ \ some \ \ y\in\mathbb{Z} \\\Rightarrow ax-my=c\end{gather*}$">$\begin{gather*}\Leftrightarrow ax-c=my \ \ \ \ for \ \ some \ \ y\in\mathbb{Z} \\ \Rightarrow ax-my=c \end{gather*}$ 위의 선형 디오판토스 방정식을 풀면 된다..