이 포스팅에서 다룰 것은 AKS primality test에 사용하는 lemma 중 하나로, n≥7n \ge 7n≥7에 대해 ℓn:=lcm(1,2,...,n)≥2n\ell_{n} := \mathrm{lcm}(1,2, ... , n) \ge 2^{n}ℓn​:=lcm(1,2,...,n)≥2n이 성립한다는 것이다. 사실 Prime Number Theorem에 의해서 ℓn∼en\ell_{n} \sim e^{n}ℓn​∼en이 성립하기 때문에, 충분히 큰 nnn에 대해서는 자명히 성립하는 부등식이다. 다만 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 : γ:=lim⁡n→∞(∑k=1n1k−logn) (Euler - Mascheroni const.)  \gamma := \lim_{n \to \infty} \left( \sum_{k=1}^{n}\frac{1}{k} - \text{log} n \right) \text{ (Euler - Mascheroni const.) } γ:=n→∞lim​(k=1∑n​k1​−logn) (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+13k+13k+1 꼴의 소수 ppp에 대해서 함수 L(m)L(m)L(m)을 다음과 같이 정의한다:L(m) = ∑x=0p−1(x(x3+m)p) L(m) \ = \ \sum_{x = 0}^{p-1} (\frac{x(x^3 + m)}{p}) L(m) = x=0∑p−1​(px(x3+m)​) 다음의 문제에 답하여라. (a) ∀t(≠0), m, L(m)=L(mt3)\forall t (\neq 0), \ m , \ L(m) = L(mt^3)∀t(=0), m, L(m)=L(mt3)(b) Zp∗\mathbb{Z}_{p}^{*}Zp∗​를 다음의 조건을 만족하는 크기가 p−13\frac{p-1}{3}3p−1​인 집합 A,B,CA,B,CA,B,C로 분할할 수 있다:L(m) = \begin{cases} a & (m \in A..

Definition.ϕ(n)\phi(n)ϕ(n) : Number of natural numbers in 1..n1..n1..n, which are relatively prime to nnn.σ(n)\sigma(n)σ(n) : Sum of divisors of nnn, including 111 and nnn itself.claim.n>1⇒ϕ(n)>n4log⁡nn > 1 \Rightarrow \phi(n) > \frac{n}{4\log n}n>1⇒ϕ(n)>4lognn​This section is intentionally left blank. Special thanks: H. Cho, W. Song. Solution 1. (Official) n:=p1e1p2e2⋯pkekn := p_{1}^{e_1} p_{2}^{e_2} \cdots p_{k}^{e_k}n:=p1e1​​p2e2​​⋯pkek​​. \phi(n) = n \p..

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

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