Sum of Squares (1) 썸네일형 리스트형 61. Sum of Squares 이번 글에서는 임의의 자연수 $p$를 최소 개수의 제곱수의 합으로 나타내는 문제를 살펴본다. 먼저 $p$를 제곱수 $1$개의 합으로 나타낼 수 있으려면 $x^2=p$를 만족하는 정수 $x$가 존재해야 한다는 사실은 쉽게 알 수 있다. $p$가 처음부터 제곱수였다면 $p$를 제곱수 $1$개의 합으로 나타낼 수 있다. 다음으로 $p$를 제곱수 $2$개의 합으로 나타낼 수 있는 경우를 알아본다. 먼저 임의의 제곱수를 $4$로 나눈 나머지를 구하면 다음과 같다: $(2k)^2=4k^2$ $(2k+1)^2=4k^2+4k+1=4k(k+1)+1$ 그 밖의 경우가 존재하지 않으므로 제곱수를 $4$로 나눈 나머지는 $0$ 또는 $1$이고, 제곱수 $2$개를 더한 결과를 $4$로 나눈 나머지는 $0, 1, 2$가 될 수 .. 이전 1 다음
