$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

수학

(9)
페르마의 두 제곱수 정리 이번 포스팅에서는 다음과 같은 정리를 증명해 보려고 한다. Theorem 1. 페르마의 두 제곱수 정리 어떤 소수 $p$ ($p > 2$)가 두 제곱수의 합, 즉 자연수 $x, y$에 대해 $$p = x^2 + y^2$$으로 나타내어질 필요충분조건은 $p \equiv 1 \mod 4$ 인 것이다. $\Rightarrow$ 거의 자명. 모든 제곱수는 모듈러 4에서 1 또는 0이고 (홀수를 제곱하면 1, 짝수를 제곱하면 0임이 어렵지 않다), 이를 더하여 $4k+3$ 형태의 홀수는 절대 얻을 수 없다. 따라서, 소수가 $4k + 1$ 인 것은 두 제곱수의 합이기 위한 필요조건임을 안다. $\Leftarrow$ 긴 여행을 떠나야 한다 (...) Wikipedia나 http://www.secmem.org/blo..
해석개론 - 연습문제 1.6.7 [출처] : 김김계 해석개론 연습문제 1.6.7 문제 임의의 자연수 $n = 1, 2, \dots$ 에 대하여, $\sqrt{n-1} + \sqrt{n+1}$ 은 무리수임을 보여라. 먼저, 주어진 수 $x = \sqrt{n-1} + \sqrt{n+1}$ 에 대해, $x^2 = 2n + 2 \sqrt{n^2-1}$ 이다. 따라서, $\sqrt{n^2-1}$이 모든 자연수에 대하여 무리수임을 보이는 것으로 충분하다. (만약 $x$가 유리수라면 $x^2$ 도 유리수이고, 이때 $\sqrt{n^2-1}$ 이 무리수일 수 없으므로) 어떤 수 제곱수 $a^2$ 과 $b^2$ 에 대해 $a^2+1 = b^2$ 이면, $(b-a)(b+a) = 1$ 이어야 하고 $b>a, a, b \in \N$ 이어야 하는데 이러한 두..
디리클레 합성곱 (Dirichlet Convolution) 디리클레 합성곱 (Dirichlet Convolution) 은 수론적 함수 (Arithmetic Function) 를 다루는 데 매우 유용한 연산이다. 다양한 정수론 증명에서 매우 써먹을 데가 많을 것 같으므로 한번은 먼저 다루고 싶었다. 정의 / 기본적인 성질 함수 $f(n)$ 과 $g(n)$ 의 Dirichlet Convolution은 $(f * g) (n)$ 으로 쓰며, 다음과 같이 정의한다. $$(f*g)(n) = \sum_{d | n}f(d)g(\frac{n}{d})$$ 다르게 쓰면 이렇게도 쓸 수 있다. (이 notation은 조금 더 직관적인데, 의외로 이렇게 쓰여 있는 곳이 많지 않다.) $$(f*g)(n) = \sum_{ab = n} f(a) g(b)$$ 이런 이상한? 정의가 매우 도움이..
2013 IMO Problem 1 / BOJ 15948 간단한 문제 2018 UCPC Problem K 와 2013 IMO Problem 1이 사실상 같은 문제다. 정확히는 UCPC 문제의 출처가 이 문제고, 저 UCPC 문제 포스팅을 하려다 보니 그냥 원본 문제도 같이 포스팅하려고 한다. 문제 임의의 자연수 $n$과 $k$에 대하여, 다음을 만족하는 $k$개의 자연수 $m_1, m_2, \dots m_k$ 가 있음을 보여라. $$1 + \frac{2^k-1}{n} = (1 + \frac{1}{m_1})(1+\frac{1}{m_2}) \cdots (1+\frac{1}{m_k})$$ 풀이 1 : 수학적 귀납법 $k$에 대한 수학적 귀납법을 써 보자. $k = 1$ 일 때, 좌변은 $1 + \frac{1}{n}$ 이고, $m_1 = n$ 이면 되므로 임의의 $n$에 대해서 ..
2019 IMO Problem 1 함수방정식 문제. 이걸로 올해 내가 풀 수 있는 IMO 문제는 끝일듯하다. 문제 모든 정수 $a, b$ 에 대하여 다음 조건을 만족하는 함수 $f: \mathbb{Z} \rightarrow \mathbb{Z}$ 를 모두 구하여라. $$f(2a) + 2f(b) = f(f(a+b))$$ 스포방지선 사실 굳이 스포방지선 없어도 될 것 같지만, IMO 문제니까 예의상 넣어주자. 풀이 $a = 0$ 을 대입. $$f(0) + 2f(b) = f(f(b))$$ 이 식을 식 (1) 이라고 하자. $a = 1$ 을 대입. $$f(2) + 2f(b) = f(f(b+1))$$ 이 식을 식 (2) 라고 하자. $b = 0$ 을 대입. $$f(2a) + 2f(0) = f(f(a))$$ 이 식을 식 (3) 라고 하자. 식 (1)..
2019 IMO Problem 4 누군가 2019 IMO 문제지를 던져 줬는데 (어제 시험이 끝났다고 하는데, 이렇게 빨리 공개되는지는 몰랐다), 일단 내 실력으로 상식적인 시간내에 풀수있을 번호는 1번과 4번뿐이고 4번이 정수 문제길래 천천히 풀어보기로 했다. 고등학교때 올림피아드 준비를 했던것도 아니고, 이제막 정수론 공부해보려고 하는 정도라서 엄청 오래 걸렸다;;; 문제 다음 조건을 만족하는 양의 정수의 순서쌍 $(k, n)$ 을 모두 구하여라. $$k!=(2^n - 1)(2^n - 2)(2^n - 4) \cdots (2^n - 2^{n-1})$$ (스포 방지선) 풀이 왜 이런 notation을 쓰는지는 잘 모르겠지만, $\nu_{a}(x)$ 는 $x$ 가 $a^{n}$ 으로 나누어 떨어지는 최대의 정수 $n$을 의미한다. (즉, ..
KAIST PoW 2019-06. Simple but not too simple integration KAIST PoW (Problem of the Week) 2019-06. 내가 본 KAIST PoW 문제 중에는 가장 쉬운 축에 속하는 문제인데, Best Solution에는 상당히 어려운 해석학 지식을 요구하는 풀이가 꽤 많이 적혀있었다. 그냥 적분으로도 계산 가능하지만... 문제 Compute the following Integral. $$\int_{0}^{{\pi}/{2}} \log (2\cos{x}) \ dx$$ 스포방지선 풀이 먼저, 약간의 관찰로 다음을 생각해 볼 수 있다. $$\int_{0}^{{\pi}/{2}} \log (2\cos{x}) \ dx = \int_{0}^{{\pi}/{2}} \log (2\sin{x}) \ dx $$ 당연하게도, 적분하려는 두 함수가 서로 $\pi / 4$ 에..
수열의 극한 문제 문제 출처 : 서울대학교 해석개론 및 연습 1 기말고사 (2019) 오늘 본 해석개론 시험에서, 대학 1학년 미적분학 수준에서 그렇게 어렵지 않게 잘 풀 수 있는 문제가 하나 나와서 포스팅해 보려고 한다. Analysis 쪽에서 나머지 문제들을 다 풀어 보고 싶은데, 일단 시험때 못푼 문제가 있고 지금은 남은 시험이 있으니 제일 쉬운 거부터. 언젠가 김김계나 PMA의 연습문제들도 풀어볼것 같고, 아무튼 여름방학 중에 수학 포스팅도 많이 해보려고 한다. 문제 $a_n$ 이 다음과 같이 정의되어 있을 때, $\lim_{n \rightarrow \infty} a_n$ 의 값을 구하여라. $$a_n = \frac{1}{n} ((n+1)(n+2)\cdots(2n-1)(2n))^{\frac1n}$$ 풀이 딱히 스포..