제곱수의 합
서론
숫자를 제곱수의 합으로 표현하는 문제는 매우 유명한 문제이다. 예를 들면, $11339 = 1^2+27^2+103^2$ 으로 표현 가능 하고, 11339는 세 제곱수의 합으로 표현 가능하다. 우리는 이 글에서, 어떤 자연수를 최소 갯수의 제곱수의 합으로 표현하는 방법에 대해 알아본다.
제곱수의 최소 갯수
우리는 어떤 자연수가 최소 갯수의 제곱수의 합으로 표현되려면, 제곱수의 합으로 어떤 자연수를 표현하려면, 제곱수가 몇 개 필요한지를 알아 볼 필요가 있다. 이를 위해서 다음의 세 정리들이 필요하다.
Lagrange의 네 제곱수 정리
Lagrange는 1770년에, 모든 자연수는 네 제곱의 합으로 표현가능됨을 증명했다. ($0=0^2$도 제곱수로 생각한다.) 이를 위해 Lagrange가 한 증명은 다음과 같다.
-
네 제곱수의 합으로 표현 가능한 두 정수의 곱은, 네 제곱수의 합으로 표현 가능하다.
증명)
$a = a_1^2 + a_2^2 + a_3^2 + a_4^2 $이고, $b = b_1^2 + b_2^2 + b_3^2 + b_4^2 $일 때, $c_1, c_2, c_3, c_4$를 다음과 같이 정의하자.
- $c_1 = a_1 b_1 - a_2 b_2 - a_3 b_3 - a_4 b_4$
- $c_2 = a_1 b_2 + a_2 b_1 + a_3 b_4 - a_4 b_3$
- $c_3 = a_1 b_3 - a_2 b_4 + a_3 b_1 + a_4 b_2$
- $c_4 = a_1 b_4 + a_2 b_3 - a_3 b_2 + a_4 b_1$
$ab = (a_1^2+a_2^2+a_3^2+a_4^2)(b_1^2+b_2^2+b_3^2+b_4^2)=c_1^2+c_2^2+c_3^2+c_4^2 $으로, 역시 네 제곱수의 합으로 표현 가능하다.
위 증명을 검증하는것은, 직접 전개를 한 후 검증을 해 보면 알 수 있다. 위 증명을 기억하는것은 어려울 수 있지만, 사원수의 곱과 같은 형태라는것을 기억하면 어렵지 않게 알 수 있다.
-
모든 소수는 네 제곱수의 합으로 표현 가능하다.
- $p^2$보다 작은 $p$의 배수 중에서 네 제곱수의 합으로 표현 가능한 수가 존재한다.
증명)
$0$ 이상 $\frac{p-1}{2}$ 이하의 $x$ 에 대해서, 가능한 $\frac{p+1}{2}$개의 $x^2 \bmod p$의 값을 생각해보자. 이 수는 모두 다르다. 왜냐하면, 서로 다른 수 $x, y$ 에 대해서, $x^2 \equiv y^2 \pmod p$라면, $(x-y)(x+y)$도 $p$로 나누어 떨어져야 하고, $x \neq y$ 라면, $x-y$와 $x+y$는 $p$의 배수일 수 없다.
또한, $0$ 이상 $\frac{p-1}{2}$이하의 $y$에 대해서, $\frac{p+1}{2}$ 개의 $-y^2-1 \bmod p$ 의 가능한 값도 겹치지 않는다. 즉, $x^2 \bmod p$과 $-y^2-1 \bmod p$로 가능한 $p+1$개의 수들을 생각 해 보면, 비둘기집의 원리에 의해 적어도 하나의 수가 겹친다. 즉, $x^2+y^2+1^2+0^2 = np$ 이고, 이는 네 제곱수의 합으로 표현 가능하다.
- $p$는 네 제곱수의 합으로 표현 가능하다.
증명)
네 제곱수의 합으로 표현 가능한 $p$의 배수 중에, 가장 작은 수를 $mp$라고 하자. $m=1$임을 증명하면 된다. 귀류법을 써서, $m=1$이 아니라고 하자.
$mp = x_1^2+x_2^2+x_3^2+x_4^2$이라고 하고, $y_i \equiv x_i \pmod m$인, $\frac{-m+1}{2}$ 이상 $\frac{m}{2}$ 이하의 수라고 하자. 이 때, $y_1^2+y_2^2 + y_3^2 +y_4^2$은 $x_1^2+x_2^2+x_3^2+x_4^2$ 과 $m$으로 나눈 나머지가 같고. 이 수를 $mr$이라고 표현하자. 여기서 $mr<m^2$ 이다. ($r = 0$ 이거나 $r=m$이려면, $x_1 = x_2 = x_3 = x_4 = 0$ 혹은 $\frac{m}{2}$ 여야 하기 때문에, 쉽게 모순임을 보일 수 있다.
$m^2pr$은 위의 정리에 의해 네 제곱수의 합으로 표현 가능하고, 이 수들을 $z_1, z_2, z_3, z_4$라고 하면, 이 수가 전부 모두 $m$의 배수임을 알 수 있다. 즉 $\frac{z_i}{m}$들의 제곱의 합은 $rp$ 이고, $r<m$이기 때문에, 모순이다.
모든 자연수는 잘 소인수 분해 될 수 있으므로, 모든 자연수는 네 제곱수의 합임을 증명했다.
Legendre의 세 제곱수 정리
Legendre는 1798년에, 세 제곱수의 합으로 표현 가능한 수랑 동치인 간단한 조건을 발견했다. $n=4^a(8b+7)$ 꼴이 아니면, $n$은 세 제곱수의 합으로 표현 가능하다.
$n=4^a(8b+7)$꼴의 수가 세 제곱수의 합으로 표현 가능하지 못한다는 사실은, 모든 제곱수는 8로 나눈 나머지가 0, 1, 혹은 4 라는 사실로 부터 쉽게 증명할 수 있지만, 역을 증명하는 것은 매우 복잡하다. 이 증명은 이 글의 범위를 매우 많이 넘어가므로 생략하도록 하겠다.
Fermat의 두 제곱수 정리
Euler는 1747년에 $4k+1$꼴의 소수는 두 제곱수의 합으로 표현 가능함을 증명했다. 또한, 어떤 자연수가 두 제곱수의 합으로 표현 가능하다는 것과, 이 자연수에서 $4k+3$꼴의 소인수의 지수가 2의 배수로 존재하지 않는다와 동치라는 사실을 증명했다.
-
두 제곱수의 합으로 표현되는 두 수의 곱 역시, 두 제곱수의 합으로 표현 가능하다.
- $(a^2+b^2)(c^2+d^2) = (ac+bd)^2+(ad-bc)^2$ 이다.
-
어떤 두 제곱수의 합으로 표현되는 자연수가, 두 제곱수의 합으로 표현되는 소수로 나누어 떨어진다면, 이 몫 역시 두 제곱수의 합으로 표현 가능하다.
증명)
$a^2+b^2$이, 소수인 $p^2+q^2$으로 나누어 떨어진다고 하자. 그럼, $p^2+q^2$ 은 $(pb-aq)(pb+aq) = p^2b^2-a^2q^2 = p^2(a^2+b^2)-a^2(p^2+q^2)$ 을 나눈다. $p^2+q^2$이 소수이기 때문에, 이 수는 $pb-aq$ 혹은 $pb+aq$ 중 한 수를 나누어야 한다. 일반성을 잃지 않고 ($a$ 를 $-a$로 대체하면 일반성을 잃지 않을 수 있다.) $pb-aq$를 나눈다고 하자. 그 경우, $(a^2+b^2)(p^2+q^2) = (ap+bq)^2 + (aq-bp)^2$ 이기 때문에, $(ap+bq)^2$ 도 $p^2+q^2$으로 나누어떨어져야 한다.
양변을 $(p^2+q^2)^2$ 으로 나누게 되면, $\dfrac{a^2+b^2}{p^2+q^2} = \left(\dfrac{ap+bq}{p^2+q^2}\right)^2+\left(\dfrac{aq-bp}{p^2+q^2}\right)^2$ 이 성립하고, 모든 수는 정수이기 때문에, 증명이 완료되었다.
이로 부터, 두 제곱수의 합으로 표현되는 자연수가 두 제곱수의 합으로 표현되지 않는 소수로 나누어 떨어진다면, 몫 역시 두 제곱수의 합으로 표현되지 않는 소수가 존재함을 쉽게 보일 수 있다.
-
$a$와 $b$가 서로소라면, $a^2+b^2$의 모든 소인수는 두 제곱수의 합으로 표현 가능하다.
증명)
$a^2+b^2$이 소수인 경우에는 자명하다. $a^2+b^2$이 소수가 아니라고 하자. $q$가 $a^2+b^2$을 나눈다면, $q$도 두 제곱수의 합으로 표현 가능하다는 것을 증명할 수 있으면, 수학적 귀납법을 적당히 사용하여 $a^2+b^2$의 모든 소인수들이 두 제곱수의 합으로 표현가능하다는 것을 증명할 수 있다. 또한, $q = 2$인 경우에는 $1^2+1^2=2$ 로 자명하기 때문에, $q>2$만 고려 할 것이다.
$mq$와 $nq$를 $a$와 $b$에 가장 가까운 $q$의 배수라고 하면, $a = mq+c, b = nq+d$ 이고 $\vert c \vert, \vert d \vert\ < \frac{q}{2}$ 가 된다. 이제 $a^2+b^2$ 을 이 수들에 대해 표현해 보면, $a^2+b^2 = m^2q^2+2mqc+c^2+n^2q^2+2nqd+d^2$ 이고, 적당한 $q$의 배수에다가 $c^2+d^2$을 더한 꼴이라는 것을 알 수 있다. 즉, $c^2+d^2$은 $q$로 나누어 떨어진다. 또한, $c^2+d^2 = qr$ 이라고 하면, 위의 라그랑주의 네 제곱수 정리를 증명할 때 사용했던 방법과 같은 방법으로, $c$, $d$를 $r$로 나눈 나머지를 이용해서 무한강하를 해 주면, $x^2+y^2=q$인 $x$와 $y$를 찾을 수 있다.
-
모든 $4k+1$꼴의 소수 $p$는 두 제곱수의 합으로 표현 가능하다.
증명)
페르마의 소정리에 의해 $1^{4k}, 2^{4k}, \cdots, 4k^{4k}$는 모두 $p$로 나눈 나머지가 1이기 때문에, $2^{4k}-1^{4k}, 3^{4k}-2^{4k}, \cdots, {4k}^{4k}-{4k-1}^{4k}$는 모두 $p$로 나눈 나머지가 같다. 이들의 최대 공약수가 $p$ 라는 사실을 증명하면, $a^{4k}-b^{4k} = (a^{2k}-b^{2k})(a^{2k}+b^{2k})$이므로, 우리는 어떤 $a, b$에 대해서 $a^{2k}-b^{2k}$ 가 $p$로 나누어 떨어지지 않는다는 사실을 보이면 된다. 이 $2^{2k}-1^{2k}, 3^{2k}-2^{2k}, \cdots$수열의 $2k-1$번째 계차항을 생각 해 보면, 이 수가 $(2k)!$라는 사실을 알 수 있고, $p$로 나누어 떨어지지 않으므로, 적어도 하나의 수는 $p$로 나누어 떨어지지 않는다.
하나의 제곱수
어떤 자연수가 하나의 제곱수의 합으로 표현가능하다는 사실은 무엇일까? $n=a^2$ 인 $a$가 존재한다는 것이고, 이는 $n$이 제곱수인지의 여부를 판단해 주면 쉽게 계산할 수 있다.
우리는 위의 정리들을 통해서, 어떤 수가 최소 몇 개의 제곱수의 합으로 표현가능한지를 살펴 보았다. 하지만, 우리는 이 수들을 명시적으로 찾는 방법을 알 지 못했다. 그렇기 위해서 우리는 어떤 수를 두 제곱수의 합으로 표현하는 방법을 명시적으로 살펴 볼 것이다. 이를 위해서는 어떤 소수 $p$를 두 제곱수의 합으로 나누는 법을 빠르게 찾으면 된다.
이를 위해, 우리는 정수를 확장한 가우스 정수(Gaussian Integer)라는 것을 살펴 볼 것이다.
가우스 정수
$a$와 $b$가 정수 일 때, $a+bi$를 가우스 정수라고 말한다. 이 집합을 $Z[i]$라고도 쓴다. 이 가우스 정수에서는 덧셈 곱셈이 잘 정의 된다. ( $(a+bi)(c+di) = (ac-bd)+(ad+bc)i, (a+bi)+(c+di) = (a+c)+(b+d)i$ ) 또한, 두 가우스 정수 $z$와 $w$의 곱이 0인 경우, $z$혹은 $w$가 0이라는 사실을 어렵지 않게 보일 수 있고, 곱셈의 항등원인 1과, 덧셈의 항등원인 0이 다르다는 사실을 알 수 있다. 이렇기 때문에, 우리는 이 숫자를 정수에 확장이라고 생각할 수 있다. 여기서 우리는 정수의 다양한 성질들을 그대로 이용하기 위해, 특히 소수(prime number)에 관련된 성질들을 그대로 이용하기 위해서 여러가지를 해 볼것이다.
가우스 소수
소수는 1이 아니면서, 1과 자기자신 이외의 수의 곱으로 표현되지 않는 수를 말한다. 여기서, 소수는 양의 정수에 대해서만 정의하지만, 가우스 정수가 음의 정수도 사용하기 때문에, 우리는 소수의 정의를 확장해서 생각 할 필요가 있다. 소수에 -1을 곱한 수도 소수라고 할 경우에 (-2, -3, -5, -7, …), 우리는 소수를 (1이나 -1) 이 아니면서, (1이나 -1)과 자기자신 이외의 수의 곱으로 표현되지 않는 수라고 정의할 수 있다. (실제로는, 이를 prime number가 아니라 irreducible number라고 말하지만, 우리가 다룰 대상에 대해서는 이 둘이 같을 것이다.)
여기서, 우리가 확장을 하려고 하면, (1이나 -1) 이 무엇인지 정확하게 정의할 필요가 있다. 1이나 -1의 특징은, 여러번 곱해서 1을 만들 수 있다는 수이다. 1은 곱셈의 항등원이기 때문에, 1을 만들 수 있는 수를 나눈다라고 말하는 것은 의미가 없다. 우리는 $a$가 단위수(unit)라는 것을, 곱해서 1을 만들 수 있는 수로, 즉 $ab = 1$인 $b$가 존재하는 것으로 정의할 것이다. 이 때, 우리는 이 단위수가, 정수일 경우에는 $1, -1$ 이 있고, 가우스 정수일 경우에는 $1, -1, i, -i$ 가 있음을 알 수 있다.
우리는 다양한 소수의 성질을 알아보겠다. 이를 위해서 먼저 곱셈의 성질을 알 필요가 있다. 가우스 정수의 Norm을 다음과 같이 정의하자. $N(a+bi) = a^2+b^2$, 평범한 Norm의 정의이다. 여기서 우리는 $N(zw) = N(z)N(w)$ 라는 사실을 알 수 있고, Norm은 두 제곱수의 합이기 때문에 $4k+3$ 꼴의 소인수를 가질 수 없음을 알 수 있다.
어떤 수가 가우스 소수라는 것은 다음중 하나를 만족하는 것과 동치이다.
- $a$혹은 $b$중 하나는 0이고, 하나의 절댓값은 $4k+3$꼴의 소수이다.
- $a^2+b^2$이 소수이다.
이 이외의 수가 소수가 아니라는 것은 쉽게 보일 수 있다. 왜냐하면, 위에서 설명했듯이, 두 제곱수의 합으로 표현되는 정수는, 두 제곱수의 합으로 표현되는 소인수를 가지기 때문이다. 그렇기 때문에, 그 둘로 쉽게 분해가 가능하다.
가우스 정수의 최대공약수
우리가 만약 가우스 정수에서 소인수를 효율적으로 찾을 수 있다면, $p=a^2+b^2 = (a+bi)(a-bi)$ 이기 때문에, $a+bi$를 찾을 수 있고, 우리가 원하는 $a$, $b$가 있음을 알 수 있다. 그렇기 위해서 우리에게는 한 가지 아이디어가 있다. 만약 우리가 $a+bi$의 다른 배수를 찾아 $q$라고 한 이후에, $\gcd(p, q)$ 를 구하면 $a+bi$가 나오지 않을까? 라는 아이디어 이다. 즉, 우리는 가우스 정수의 최대공약수에 대해 정의 할 필요가 있고, 이를 찾는 방법에 대해서 알아보아야 한다.
$a$와 $b$의 최대 공약수는, $a$와 $b$의 모든 약수로 나누어 떨어져야 한다. 이렇게 우리는 최대공약수를 정의 할 것이다. 이 최대공약수를 찾는 알고리즘은 유클리드 알고리즘이 있다. 즉 $a$를 $b$로 나눈 몫을 $q$, 나머지를 $r$이라고 할 때, $gcd(a, b) = gcd(b, r)$ 이라는 사실을 이용해 계산 하는 것이다. $a=bq+r$ 이기 때문에 $a, b$의 공약수와 $b, r$의 공약수의 집합이 같다는 사실을 쉽게 알 수 있다. 이 유클리드 알고리즘을 정의하기 위해서는 몫과 나머지를 정의해야하고, 나머지가 작아진다라는 사실을 알아야 한다. 유클리드 알고리즘을 사용하는데 $r$이 $a$보다 크다고 생각해 보면, 유클리드 알고리즘은 종료하지 않는다. 그래서 우리는 어떤 기준 $f$에 대해서, $f(r)<f(a)$가 되는 나눗셈이 있을때, 이를 적당한 나눗셈이 존재한다고 말하고, 가우스 정수에서 적당한 나눗셈이 존재하며, 그 기준이 $f = N$, 즉 Norm이 작아진다라는 것을 보일것이다.
일단 정수를 기준으로 생각해 보면 $a$를 $b$로 나눈 몫은, 유리수 나눗셈을 한 후 가장 근접한 수를 찾는다. 가우스 정수에서도 역시 마찬가지이다. $\frac{a}{b}$는, $x+yi$ 꼴이 나올 것인데, $x$와 $y$는 유리수가 될 것이다. 이에 가장 근접한 가우스 정수를 $z+wi$ 라고 하자. (즉, $\vert x-z \vert , \vert y-w \vert \le \frac{1}{2}$) 이다. 이 경우, $a-b(z+wi)$ 는 $(\vert x-z \vert + \vert y-w \vert i)b$ 이고, 이 수의 Norm을 계산 해 보면, $(x-z)^2+(y-w)^2 \le \frac{1}{2}$ 이기 때문에 $N(b)$ 보다 작음을 알 수 있다. (실제로는 , $\frac{N(b)}{2}$ 보다 작거나 같다.) 즉, 우리는 적당한 나눗셈 방법을 찾았다. 물론 나머지의 제한이 널널하기 때문에, 몫과 나머지가 유일하지 않을 수 있지만, 유클리드 알고리즘에서 몫과 나머지가 유일하다는 정보는 사용하지 않는다.
그래서 우리는 두 수의 최대공약수를 구할 때, 유클리드 알고리즘을 그대로 사용할 수 있다.
$p$의 약수 찾기
그래서, 우리는 $p$의 약수를 찾아야 하는데, 어떤 가우스 정수 $q$가 존재해서, $N(q)$가 $p^2$보다 작은 $p$의 배수라면 (그리고, $N(x) = p$인 $x$가 $(a \pm bi)$에 unit을 곱한 수 밖에 없다면), 우리는 $p$와 $q$의 공약수를 구하면 $(a\pm bi)$ 가 나올것이라고 생각 할 수 있다. 이런 $q$를 찾는 것은, $x^2 \equiv -1 \pmod p$인 $x$를 찾아서, $q = x+i$ 로 정의 해 주면, $x^2+1$이 $p$의 배수이기 때문에, 이 둘의 공약수를 구하면 된다는 사실을 알 수 있다. 이런 $x$는, 1이상 $p-1$이하의 $a$에 대해 $a^{(p-1)/2} \bmod p$ 중 절반이 -1이고 절반이 1이라는 사실을 이용하면, 평균 두번의 시도만에 이 값이 -1인 것을 찾으면, $a^{(p-1)/4}$ 가 해당하는 $x$가 된다. 즉, 위와 같은 로직을 이용해서 $gcd(p, x+i)$ 를 구하면, $a\pm bi$ 가 나올 것이고, 이 수가 우리가 원하는 두 제곱수의 합으로 표현한 수가 된다. 여기서 우리가 증명해야 할 사실이 남았다. 그것은 바로, 괄호 안에 썼던 “$N(x) = p$인 $x$가 $(a \pm bi)$에 unit을 곱한 수 밖에 없다면” 이라는 부분이다. 이를 증명하기 위해서, 우리는 $p$의 소인수 분해를 살펴보면 $(a +bi)(a-bi)$ 인데, 이 소인수 분해가 유일하다라는 것을 증명하면 된다. 이는, 유클리드 알고리즘의 과정에서 두 정수 $a$, $b$에 대해 $ar+bs = \gcd(a,b)$ 인 $r, s$ 가 존재하며, 이를 통해서 임의의 소수 $p$에 대해서 $p \vert ab$ 이면 $ p \vert a$ 혹은 $p \vert b$라는 것을 증명할 수 있다. ($a$가 $p$를 나누지 않는다고 하자, 이 경우에 $gcd(a, p)=1$ (혹은 unit이 곱해진 수)이기 때문에, $ar+ps = 1$ 인 $r, s$가 존재하며, $rab+psb=b$ 이고, $rab$는 $p$로 나누어 떨어지기 때문에, $p$도 $b$로 나누어 떨어져야 한다.) 이를 통해서, 소인수 분해의 유일성을 정수와 같은 방법으로 증명 해 줄 수 있다. 이렇기 때문에, $p=a^2+b^2$으로 표현하는 ${a, b}$가 유일하다는 사실도 알 수 있다.
제곱수의 합으로 표현하기
이제, 우리는 $N$을 두 제곱수의 합으로 표현 할 수 있으면, 그 수를 명시적으로 찾는 방법을 알았다. $O(N^{1/4})$ 소인수 분해 알고리즘을 사용해서, 소인수를 구하고, 이들 각각을 분해해서 찾아준 다음에, 제곱수의 곱을 사용해서 곱해주면 된다. 이제 세 제곱수와 네 제곱수에 대해서는 어떻게 해야 할까?
세 제곱수의 합으로 표현되는 $N$에 대해서는, 랜덤으로 제곱수 $a^2$을 하나 고른 다음에(혹은 1부터 증가시키면서 고른 다음에), $N-a^2$ 이 두 제곱수의 합으로 표현되는지를 찾으면 된다. $N$이하의 수가 두 제곱수의 합일 확률은 $O(\frac{1}{\sqrt{\ln N}})$ 이기 때문에, 총 $O(N^{1/4} \sqrt{\ln N})$ 의 시간 복잡도에 답을 찾을 수 있다. (tight한 제한이고, 이 증명이 어려운 경우에는, $4k+1$꼴의 소수일 확률이 $O(\frac{1}{\ln N})$ 이기 때문에, $O(N^{1/4} \ln N)$ 으로 시간복잡도를 증명할 수 도 있다.)
네 제곱수의 합인 경우 $4^a(8n+7)$ 꼴이고, $4^a(8n+6)$ 꼴의 수는 세 제곱수의 합으로 표현 가능하기 때문에, 이를 세 제곱수의 합으로 표현 하고 $(2^a)^2$을 더해주면 된다.
구현
아래 코드는 블로그 게시글을 작성하기 위해 백준 온라인 저지에 만든 제곱수의 합 2 문제에 대한 구현이다. Python 3를 이용하여 구현이 되어있다.
import random
from math import gcd
def ipow(x, y, p):
ret = 1
while y > 0:
if (y&1) == 1:
ret = ret*x%p
x = x*x%p
y >>= 1
return ret
def is_prime(x):
def miller_rabin(x, a):
if x%a == 0:
return False
d = x-1
while True:
k = ipow(a, d, x)
if (d&1) == 1:
return (k != 1 and k != x-1)
elif k == x-1:
return False
d >>= 1
for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
if x == i:
return True
if x > 40 and miller_rabin(x, i):
return False
return x > 40
def factorize(n):
def rec(n, ret):
if n == 1:
return
if n%2 == 0:
ret.append(2)
rec(n//2, ret)
return
if is_prime(n):
ret.append(n)
return
while True:
a = random.randint(2, n-1)
b = a
c = random.randint(1, 20)
do_while_flag = True
while do_while_flag or gcd(abs(a-b), n) == 1:
do_while_flag = False
def f(x):
return (c+x*x)%n
a = f(a)
b = f(f(b))
if a != b: break
x = gcd(abs(a-b), n)
rec(x, ret)
rec(n//x, ret)
return
ret = []
rec(n, ret)
return sorted(ret)
class GaussianInteger:
def __init__(self, re, im):
self.re = re
self.im = im
def norm(self):
return self.re*self.re+self.im*self.im
def __floordiv__(w, z):
def rem(a, b):
ret = a%b
if ret < 0: ret += b
if 2*ret > b: ret -= b
return ret
def quo(a, b):
return (a-rem(a,b))//b
w0, w1 = w.re, w.im
z0, z1 = z.re, z.im
N = z.norm()
u0, u1 = quo(w0*z0+w1*z1, N), quo(w1*z0-w0*z1, N)
return GaussianInteger(u0, u1)
def __mod__(a, b):
a0, a1 = a.re, a.im
b0, b1 = b.re, b.im
q = a//b
q0, q1 = q.re, q.im
r0 = a0-q0*b0+q1*b1
r1 = a1-q0*b1-q1*b0
return GaussianInteger(r0, r1)
@staticmethod
def gcd(w, z):
while z.re != 0 or z.im != 0:
w, z = z, w%z
return w
def quadratic_residue(p):
k = p//4
j = 2
while True:
a = ipow(j, k, p)
b = a*a%p
if b == p-1: return a
j += 1
def sum_of_two_squares_prime(p):
if p == 2: return (1, 1)
a = quadratic_residue(p)
g = GaussianInteger.gcd(GaussianInteger(p, 0), GaussianInteger(a, 1))
return (abs(g.re), abs(g.im))
def sum_of_two_squares(N):
square = 1
primes = set()
for x in factorize(N):
if x in primes:
square *= x
primes.remove(x)
else:
primes.add(x)
if len(primes) == 0:
return (square, 0)
for x in primes:
if x%4 == 3:
return None
a, b = square, 0
for x in primes:
c, d = sum_of_two_squares_prime(x)
a, b = a*c+b*d, a*d-b*c
return (abs(a), abs(b))
def sum_of_squares(n):
if n == 0: return []
cnt = 0
if n%4 == 0:
while n%4 == 0:
n //= 4
cnt += 1
return list(map(lambda x: x<<cnt, sum_of_squares(n)))
if n%8 == 7:
return sum_of_squares(n-1) + [1]
ab = sum_of_two_squares(n)
if ab is not None:
a, b = ab
ret = []
if a != 0: ret.append(a)
if b != 0: ret.append(b)
return ret
i = 2
if n%4 == 3: i = 1
while True:
ab = sum_of_two_squares(n-i*i)
if ab is not None:
return list(ab) + [i]
i += 2
def main():
N = int(input())
sos = sum_of_squares(N)
print(len(sos))
print(" ".join(map(str, sos)))
if __name__ == '__main__':
main()