이 포스팅에서 다룰 것은 AKS primality test에 사용하는 lemma 중 하나로, \(n \ge 7\)에 대해 \(\ell_{n} := \mathrm{lcm}(1,2, ... , n) \ge 2^{n}\)이 성립한다는 것이다. 사실 Prime Number Theorem에 의해서 \(\ell_{n} \sim e^{n}\)이 성립하기 때문에, 충분히 큰 \(n\)에 대해서는 자명히 성립하는 부등식이다. 다만 PNT가 좀 overkill이기도 하고, 기왕 non-analytical한 증명이 있으니 이야기해보도록 하자. 증명은 다음의 글에서 가져왔다. https://math.stackexchange.com/questions/851328/textlcm1-2-3-ldots-n-geq-2n-for-n-ge..

이건 또 정수론 공부할 때 (2017.08.09) 열심히 쓰던 글이다. Inline math 가독성 극혐... 나중에 TeX으로 써서 따로 올려야겠다. 일단은 포스팅이 적혀 있는 것까지만. 추가 notation : $$ \gamma := \lim_{n \to \infty} \left( \sum_{k=1}^{n}\frac{1}{k} - \text{log} n \right) \text{ (Euler - Mascheroni const.) } $$ $$ \zeta(s) := \begin{cases} \sum_{k=1}^{\infty} \frac{1}{k^s} & {(s>1)} \\ \lim_{x \rightarrow \infty} {\left(\sum_{n \le x} \frac{1}{k^s} - \frac{x..

문제 링크 원래 1년 전 (2017.12 초)에 정수론 들을 때쯤 푼 문제인데, 포스팅 도중 계산이 틀려서 보류되었다. 얼추 기워서 올리긴 하지만 여전히 틀린 부분이 있을 수 있다. \(3k+1\) 꼴의 소수 \(p\)에 대해서 함수 \(L(m)\)을 다음과 같이 정의한다:$$ L(m) \ = \ \sum_{x = 0}^{p-1} (\frac{x(x^3 + m)}{p}) $$ 다음의 문제에 답하여라. (a) \(\forall t (\neq 0), \ m , \ L(m) = L(mt^3)\)(b) \(\mathbb{Z}_{p}^{*}\)를 다음의 조건을 만족하는 크기가 \(\frac{p-1}{3}\)인 집합 \(A,B,C\)로 분할할 수 있다:$$L(m) = \begin{cases} a & (m \in A..

Definition.\(\phi(n)\) : Number of natural numbers in \(1..n\), which are relatively prime to \(n\).\(\sigma(n)\) : Sum of divisors of \(n\), including \(1\) and \(n\) itself.claim.$$n > 1 \Rightarrow \phi(n) > \frac{n}{4\log n}$$This section is intentionally left blank. Special thanks: H. Cho, W. Song. Solution 1. (Official) \(n := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k}\). $$ \phi(n) = n \p..

여름방학 때부터 3단원을 정리하려고 했지만 너무 귀찮아서 패스.4단원은 \(\pi (x)\)를 신나게 갖고 노는 1부와, 소수 역수의 합을 가지고 노는 2부로 나뉘어서 업로드됩니다.

페르마 수의 primality test에 Miller - Rabin을 쓰면 어떨까? 라는 생각에서 기존 이론을 search하다가 찾아낸 이론인데, 생각해보니 옛날에 배웠던 거다... 그럼 그렇지. $$ F_n = 2^{2^n} + 1 \text{ is prime} \\ \Leftrightarrow 3^{\frac{F_n-1}{2}} \equiv -1 (\text{mod} \ F_n) (n>0)$$ pf)\( \Rightarrow) \)\( \text{by Euler's Criterion,} \) \( 3^{{F_n-1}/2} \equiv \left(\frac{3}{F_n}\right) \)이 때 \(F_n \equiv 2 (mod 3)\)이므로 \(F_n\)은 법 3에 대한 이차잉여가 아니다. \(\le..