티스토리

레프네 약방
검색하기

블로그 홈

레프네 약방

tamref.com/m

졸업하고 싶다

구독자
11
방명록 방문하기

주요 글 목록

  • lcm(1, 2, ... , n)의 크기 이 포스팅에서 다룰 것은 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.. 공감수 1 댓글수 0 2019. 9. 4.
  • Apostol 해석적 정수론 CH3. 28~31 이건 또 정수론 공부할 때 (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.. 공감수 0 댓글수 0 2018. 12. 7.
  • AOPS 직접 풀이 #003 문제 링크 원래 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.. 공감수 1 댓글수 0 2018. 12. 7.
  • 3 Distinct proofs on lower bound of Euler's totient function 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.. 공감수 4 댓글수 0 2018. 6. 27.
  • Apostol 해석적 정수론 4단원 - (1) 여름방학 때부터 3단원을 정리하려고 했지만 너무 귀찮아서 패스.4단원은 \(\pi (x)\)를 신나게 갖고 노는 1부와, 소수 역수의 합을 가지고 노는 2부로 나뉘어서 업로드됩니다. 공감수 0 댓글수 0 2018. 2. 17.
  • Pépin's test 페르마 수의 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.. 공감수 0 댓글수 0 2017. 10. 14.
  • 소수의 sum-of-square 표현은 존재한다면 유일하다! stackexchange에서 본 내용. 페르마의 두 제곱수 정리에 의해, \(4k+1\)꼴의 소수는 두 제곱수의 합으로 표현이 가능하다. 이번엔 그 표현이 유일함을 보이자.기본적으로 꼴은 귀류. 1. Algebraic(?) NT\(p = a^2 + b^2 = c^2 + d^2 \)으로 표현될 수 있다고 하자. (\(\{a,b\}\neq\{c,d\}\)) 그럼 다음과 같이 \(p\)는 최소 4개의 서로 다른 가우스 소인수를 가진다. $$p = (a+bi)(a-bi) = (c+di)(c-di) $$그런데 가우스 정수의 집합 \(Z[i]\)는 Unique Factorization Domain이기 때문에,(*소인수 분해 꼴이 유일한 집합인 것 같다. 머수ㅡ알못이라 한참 후에야 추가가 가능할 듯하다) 이는 \(a.. 공감수 0 댓글수 0 2017. 8. 15.
  • Apostol 해석적 정수론 CH2. (20~27) 1편 : http://drugstoreoftamref.tistory.com/152편 : http://drugstoreoftamref.tistory.com/16I have no time!D20. Generalized Dirichlet Convolution$$ \text{for } x \in \mathbb{R}, \\ (a \circ F)(x) := \sum_{n \le x} a(n)F(\frac{x}{n}) $$ \(\text{cf) if } \forall x\notin \mathbb{Z} \quad F(x)=0 \ \Rightarrow \ \circ \equiv \ast \) T21. $$ a \circ (b \circ F) = (a \ast b) \circ F $$ pf) \( a \circ (b \c.. 공감수 0 댓글수 0 2017. 8. 8.
  • APOSTOL 해석적 정수론 CHAP 2. 12 ~ 19 1편 : http://drugstoreoftamref.tistory.com/15Qkffl Qkffl dmdkdkdkdkdkdD12. (Completely) Multiplicative Function MF : \(f \text{ s.t. } f(mn)=f(m)f(n) \ \forall m,n \text{ s.t. }gcd(m,n)=1\) CMF : \(f \text{ s.t. } f(mn)=f(m)f(n) \ \forall m,n \) * 앞으로 MF들의 집합을 \(\mathbb{M}\)으로, CMF들의 집합을 \(\mathbb{CM}\)으로 denote. C12-1. $$f \in \mathbb{M} \Rightarrow f(1)=1$$ T13. $$f \in \mathbb{M} \Leftrightarr.. 공감수 0 댓글수 0 2017. 8. 7.
  • [Apostol 해석적 정수론] Chap 2. 1~11 Apostol의 해석적 정수론을 공부해 보았다. 대부분 증명을 혼자 쓰다 보니 오류가 있을 수도...? 오류 제보 환영합니다.Notation :D : DefinitionT : Thm.C : Corollary별 말 없으면 \(p\)는 소수D1. (Mobius Func.) \( \mu(n) = \begin{cases} 1 \quad (n = 1) \\ 0 \quad (\exists \ p \ s.t. \ p^{2} | n) \\ {(-1)}^{\omega(n)} \quad (otherwise) \end{cases}\)( \(\omega(n)\) : \(n\)의 서로 다른 소인수 개수) T2. $$ \sum_{d|n}{\mu(d)} = I(n) = \lfloor \frac{1}{n} \rfloor $$ pf).. 공감수 0 댓글수 0 2017. 8. 6.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.