이 문제는 서로 다른 두 소수 $p,q$에 대해서 $p^{1/n}+q^{1/m}(n,m\in \mathbb{N}_{\ge 1}$의 최소 다항식을 구하는 문제이다. 아래 두 개의 lemma를 증명하며 최소 다항식을 구하는 방법을 알아보자. $K$가 $F$의 field extension이라 하자. Lemma 1. $\forall \alpha \in K$, $\alpha$ acting by left-multiplication on $K$ is a $F$-linear transformation of $K$. Proof. 임의의 $x, y\in K$와 $a, b\in F$를 잡자. 그럼 $\alpha(ax+by)=\alpha ax+\alpha by = a(\alpha x)+b(\alpha y)$가 된다. 따라서 ..

원점에서 $(n,m)$으로 레이저를 쏘는 상황을 생각해보자. 집은 몇 개가 부숴질까? $y=\frac{m}{n}x$를 생각해보자. 이 직선에서 $x,y$가 모두 정수인 점이 집이 있는 구간이다. 결국 $mx=ny$의 정수 해의 개수가 된다. $(m,n)=d$라 하면 $m'=m/d,\ n'=n/d$ 일 때 $m'x=n'y$이고 따라서 $x=\alpha n',\ y=\alpha m'(1\le \alpha \le d)$이다. 그러므로 총 $d$개 의 집이 부숴진다. 원점도 집이 있으므로 $d+1$개 부숴진다. 벽을 지난다는 것은 무엇을 의미할까? 세로 벽을 생각하면 위에서 생각한 직선이 $(a,b)$와 $(a,b+1)$의 사이를 지난다는 것을 의미한다 그렇다는 것은 $b

굉장히 오랜만에 올리는 포스팅~ 방학동안 버클리에 가 있어서 백준을 못한게 크다 ㅜㅜ. 본론으로 들어가자. 문제는 $m$개의 재료 중에서 $n$개를 선택해서 그 값들의 곱을 모두 더하는 것이다!! 간단히 주어진 예제로 생각해보면 값이 각각 $x, y, z$라고 할 때 $$x^{3}+y^{3}+z^{3}+x^{2}(y+z)+y^{2}(z+x)+z^{2}(x+y)+xyx$$ 를 구하는 것이다. 우리가 생각할 수 있는 것은 이 식을 어떻게 좀 간단하게 할 수 있냐는 것이다. 놀랍게도 위의 식은 다음과 같이 간단하게 표현된다! $$\frac{x^{5}}{(x-y)(x-z)}+\frac{y^{5}}{(y-x)(y-z)}+\frac{z^{5}}{(z-x)(z-y)}$$ 값이 서로 다른 $m$개의 재료 중에서 $n$..

방학때 버클리에서 현대대수학 1을 들으면서 현대대수학 2를 스터디해서 가을 학기에는 현대대수학 2를 듣기로 결정! 버클리 현대대수학 1은 현대대수학 2 내용까지 일부 나가서 오히려 좋다. 응미방은 수리 전공을 위해서 들어야하는 기선이다. 저거까지 듣고 다른 과 기선 들어야지! 라고 생각했지만 다른 과는 들을 과목이 없으니까 확률 및 통계를 듣지 않을까 싶다. 미적분학 2랑 일반 물리학 2를 빨리 없애야지. 일반 생물학이랑 일반 물리학 실험 1이 남긴 했지만 1학기에 일반 화학 실험을 B+받은 뒤로 보고서를 쓰기 싫어져 버렸다. 2학기에는 전공 과목을 조금 듣는 시기로 선형대수학을 포함했다. 1학기때 선형 대수학 개론을 들었으니까 잘 되겠지?ㅎ 입학 영어 시험이 망해서 가을 학기에 영어 한 과목을 또 청산..

이라는 제목의 논문(?)을 써보았다. 내 블로그에 있는 증명에 있는 오류를 모두 수정하여 썼다~ 한참 전에 썼었는데 까먹고 못 올리고 있었다ㅎㅎ 블로그에 신경쓸 수 없을 정도로 바빴다. 물론 지금도 바쁘고! 윌슨의 정리 확장을 이용한 재미있는 알고리즘을 소개했으니 한 번 읽어보기를 바란다!

문제에서 주어진 조건으로부터 $(n,m)=1$이고 $m\not\equiv n\pmod{2}$라는 사실을 알 수 있다. 그럼 우리가 구하고자 하는 값은 다음과 같다. $$\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1][n=odd][m=even]$$ 위 식을 변형 시키면 다음을 얻는다. $$=\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1](1-[2|n])[2|m]$$ $$=\sum_{n=1}^{L}\sum_{m=1}^{L} [(n,m)=1][2|m]-\sum_{n=1}^{L}\sum_{m=1}^{L}[(n,m)=1][2|n][2|m]$$ 이때 오른쪽 항은 항상 0이 된다는 사실을 알 수 있다. \[=\sum_{n=1}^{L}\sum_{m=1}^{L}\sum_{s=1..