아직 上편을 본 적이 없다면, 일단 보고 오자. Part II. 페르마의 두 제곱수 정리 이번에는 사원수 대신에 복소수를 가져와 보자. 사원수 때와 유사하게, 복소수 \(z=x+iy\)의 norm은 \(\text{N}(z)=z\overline z=x^2+y^2\)로 정의된다. 또한 \(\text{N}(zw)=\text{N}(z)\text{N}(w)\) 역시 사원수 때와 마찬가지로 성립하므로, 어떤 자연수를 두 제곱수로 나타낼 수 있음의 필요조건은 그 자연수의 모든 소인수가 두 제곱수의 합으로 표현될 수 있음이다. 모든 소수가 두 제곱수의 합으로 표현될 수는 없다. 당장 \(3\)만 해도 두 제곱수의 합으로 표현될 수 없는 소수이다. 임의의 제곱수는 \(4\)로 나눈 나머지가 \(0, 1\)이므로, 두 제..

디오판토스. 그러니까 3세기부터 수학자들의 관심을 끈 문제가 하나 있다. 어떤 자연수 하나를 최대 몇 개의 제곱수의 합으로 나타낼 수 있을까? 일단 3개 이상일 것 같다. \(3=1^2+1^2+1^2\)로 나타낼 수 있으니까. 조금만 더 나아가면 4개 이상일 것 같다. \(7=2^2+1^2+1^2+1^2\)이니까. 그러면 다섯 개일 수는 있을까? 여섯 개일 수는? 일단 답이 그렇게 크지는 않을 것 같다. 직감만으로 생각을 해 본다면. 한 자리 수 안에서 정리되지 않을까. 이 문제가 본격적으로 주류 수학계의 화두에 오른 것은 디오판토스의 산술을 클로드 가스파르 바셰가 라틴어로 번역한 1621년이었다. 그리고 이 문제는 조제프-루이 라그랑주가 답이 4라는 증명을 내놓은 1770년까지 약 150년 동안이나 미..

근래 다시 출시하여 뭇 어린이와 어른이를 미치게 했던 포켓몬 빵을 기억하는가? 스티커만 가지고 빵을 버리는 사람, 편의점에서 산 빵을 개당 3000원에 되팔이하는 사람은 양반이었다. 빵 공장에서 일하는 사람이 수백 장의 스티커를 되팔 작정으로 횡령했다 뉴스에도 나왔지. 포켓몬 빵이 처음 나왔을 때도 지금도, 관건은 모든 스티커를 모을 때 필요한 빵의 갯수였다. n종류의 스티커를 모을 때 필요한 빵의 갯수는 몇 개인가? 어라... 어디서 많이 본 문제 아니던기? 그렇다, 26217번 문제에서 한 번 다루었던 쿠폰 수집가 문제이다. 해당 포스트에서 한 증명은 사실 엄밀하지 않다. \(\mathbb{E}(i+1)\)을 구하는 방법을 약간 어물쩡하게 넘긴 감이 있다. 여기서 완벽하게 한 번 짚고, 그 다음 원래..

피보나치 수에 관한 여러 가지 성질은 7677번 문제에서 예를 들었듯이 행렬과, 그리고 크게 상관은 없어 보이지만 황금비와도 큰 연관이 있다. 이번 포스트에서는 그 쪽과 관련하여 다루어 볼 예정이다. 먼저 피보나치 수의 일반항부터 시작하도록 하자. 일반항을 구하기 위해서 점화식을 이런 등비수열 닮은 꼴의 식으로 나타내 보자. \(F_{n+2}-aF_{n+1}=b(F_{n+1}-aF_n)\)의 형태로 말이다. 그러면 \(F_{n+2}=F_{n+1}+F_n\)과 비교해 보면 \(a+b=1, ab=-1\)이 된다. \(a>b\)라고 둔다면, \(a=\frac{1+\sqrt5}{2}\)가 되고, 이것은 황금비이다! 자, 그럼 지금부터는 \(a=\phi, b=\psi\)로 나타내 보자. \(\phi\)는 황금비를..

피보나치 수는 막 배우기 시작하는 초보 프로그래머와 뗄래야 뗄 수 없는 관계이다. 범위가 아주 작을 때는 재귀함수, 어느 정도 커질 때는 다이나믹 프로그래밍, 그리고 감당할 수 없을 정도로 커지면 분할 정복을 이용한 거듭제곱까지. 피보나치 수열에 관한 문제는 7677번 문제뿐만이 아니다. 대충 세어도 백준에만 50개가 넘는 피보나치 수열 관련 문제가 있다. 그렇게나 자주 나오는 피보나치 수열인 만큼, 단순히 N번째 피보나치 수를 계산하는 것에서 그치지 않고 피보나치 수열의 합이라거나, 제곱 합이라거나, 최대공약수라거나 이것저것 (뇌절로 읽힐 수도 있는) 바리에이션을 보여 준다. 그 중 간단하게 증명 가능한 것들을 하나씩 증명해 보자. 간단한 녀석들은 두어 줄로 끝이 나니 편하게, 편하게 보자. 우선 20..

16563번 문제에서 말한 바 있듯이, 무식하게 전부 나눠 보는 방식인 에라토스테네스의 체는 시간복잡도가 \(O(N\log\log N)\)이고 조금 더 영리하게 계산한 linear seive는 시간복잡도가 \(O(N)\)이다. 이 두 가지 모두 소수를 판정하고 소인수분해하기는 확실하지만, 매우 심각한 하자가 있다. 시간이 너무 오래 걸린다는 것이다. 충분히 빠른 컴퓨터라면 대여섯자리 수가 소수인지 검사하는 것은 그렇게 오래 걸리지 않는다. 하지만 10자리라면? 20자리라면? 4149번 문제에서는 최악의 경우 19자리 수를 계산해야 한다. 영리한 linear seive를 사용하더라도 걸리는 시간이 N에 비례하기 때문에 시간초과가 날 것이다. 이를 정말 빠르게 계산할 수 있는 것이 밀러-라빈 소수판정법과 폴..