두 제곱수의 합

개요 — 동기·문제의식

합동 $A\equiv B\pmod M$ 은 참된 등식 $A=B$ 의 근사일 뿐이다 — 하지만 이 근사가 진짜 등식을 만들어내는 도구가 될 수 있다면? 이 장의 질문은 순수하게 등식에 관한 것이다: 어떤 자연수가 두 정수 제곱의 합으로 써지는가? $5=1^2+2^2$, $13=2^2+3^2$ 는 되지만 $3,7,11,19$ 는 안 된다. 패턴을 찾아보면 답은 놀랍도록 깨끗하다: 소수는 $p\equiv1\pmod4$ 일 때, 오직 그때만. 이 정리를 증명하는 도구가 바로 이차상호법칙(합동에 관한 정리)이고, 그 증명 기법(Fermat의 하강법)은 정수론에서 가장 우아한 논증 중 하나로 꼽힌다. 일반 합성수로 확장하면 답은 소인수분해의 형태로 완전히 결정되고, 가장 깔끔한 설명은 가우스 정수 $\mathbb{Z}[i]$ 의 인수분해로 얻어진다.

직관

$p=a^2+b^2$ 이면 $\bmod p$ 로 보아 $a^2\equiv-b^2\pmod p$, 즉 $-1$ 이 $p$ 를 법으로 한 제곱수(QR)라는 뜻이다. 이차잉여 보충법칙은 정확히 $-1$ 이 QR인 소수가 $p\equiv1\pmod4$ 인 소수임을 알려준다. 그래서 "두 제곱수의 합인가"와 "$\bmod4$ 로 $1$ 인가"는 본질적으로 같은 질문의 두 얼굴이다 — 하나는 정수 등식(어렵다), 하나는 합동(쉽다). 어느 쪽이 "더 깊은" 명제인지 가늠하는 법: 쉬운 명제(B: $p\equiv1\bmod4$)에서 어려운 명제(A: $p$가 두 제곱의 합)로 가는 방향이 깊은 정리고, 그 역방향은 상대적으로 얕다.¹ 실제로 "$A\Rightarrow B$"(두 제곱의 합이면 $1\bmod4$)는 몇 줄로 끝나지만, "$B\Rightarrow A$"는 Fermat의 하강법(descent) 이라는 본격적인 증명 기법을 요구한다.

정의

(Fermat의 두 제곱수 정리 — 소수, Theorem 24.1) 소수 $p$ 가 두 제곱수의 합으로 써진다 ⟺ $p\equiv1\pmod4$ 또는 $p=2$.¹

(일반 합성수 판정, ch.25) $n=2^{a_0}\prod p_i^{a_i}\prod q_j^{b_j}$ ($p_i\equiv1$, $q_j\equiv3\pmod4$, 서로 다른 소수들)가 두 제곱수의 합 ⟺ 모든 $b_j$ 가 짝수.² 즉 $3\bmod4$ 형 소인수는 짝수 차수로만 들어갈 수 있고, $2$ 와 $1\bmod4$ 형 소인수는 차수에 제약이 없다.

(곱셈성, Brahmagupta–Fibonacci 항등식) $$(u^2+v^2)(A^2+B^2)=(uA+vB)^2+(vA-uB)^2.$$ 두 제곱수의 합인 수들의 곱은 다시 두 제곱수의 합이다 — 직접 전개하면 검증되며,² 가우스 정수 노름의 곱셈성 $N(\alpha\beta)=N(\alpha)N(\beta)$ 의 실수 버전이다(가우스 정수).

주요 정리

정리 1 (쉬운 방향, $p=a^2+b^2\Rightarrow p\equiv1\bmod4$).¹

정리 2 (어려운 방향, $p\equiv1\bmod4\Rightarrow p=a^2+b^2$, Fermat의 하강법).¹

이 과정은 예제 3에서 $p=881$ 에 대해 구체적으로 보인다.

예제

예제 1 (소수 판정표). $13=2^2+3^2$ ($13\equiv1\bmod4$), $29=2^2+5^2$, $97=4^2+9^2$. $7,11,19$ ($\equiv3\bmod4$)는 불가 — 직접 $19-1,19-4,19-9,19-16$ 중 제곱수가 없음을 확인해도 같은 결론.¹

예제 2 (일반 합성수 판정). $45=3^2\cdot5$: $3\equiv3\bmod4$ 의 지수는 $2$(짝수), $5\equiv1\bmod4$ → 조건 충족 → $45=36+9=6^2+3^2$. 반면 $21=3\cdot7$: $3,7$ 모두 $3\bmod4$ 인데 지수가 둘 다 $1$(홀수) → 불가. $63=3^2\cdot7$: $3$ 의 지수는 짝수지만 $7\equiv3\bmod4$ 의 지수가 $1$(홀) → 역시 불가.

예제 3 (Fermat 하강법, Silverman의 $p=881$ 예제).¹ $881\equiv1\pmod4$ ($881=220\cdot4+1$). 출발: $A^2+1^2=Mp$ 형태로 $387^2+1^2=170\cdot881$ ($149770=149770$ ✓, 즉 $M=170$). 하강 1단계: $u\equiv387,\ v\equiv1\pmod{170}$ 이며 $|u|,|v|\le85$ 인 값을 고르면 $u=47,\ v=1$( $387\equiv47\pmod{170}$ ). 곱셈성 항등식으로 $47^2+1^2=170\cdot13$ ($2210=2210$ ✓) — 배수가 $170$ 에서 $13$ 으로 줄었다. 13은 작아서 직접 $13=2^2+3^2$. 다시 하강 절차를 적용(또는 직접 인수분해 시도)하면 최종적으로 $881=16^2+25^2$ ($256+625=881$ ✓)에 도달한다.

예제 4 (곱셈성으로 새 표현 만들기). $5=1^2+2^2$, $13=2^2+3^2$ → $65=5\cdot13=(1\cdot2-2\cdot3)^2+(1\cdot3+2\cdot2)^2=(-4)^2+7^2=16+49=65$ ✓. 직접 찾아보면 $65=1^2+8^2$ 도 성립 — 두 가지 표현이 존재한다(서로 다른 소인수 $5,13$ 각각이 $1\bmod4$ 이기 때문).

예제 5 (표현 개수와 소인수의 개수). $325=5^2\cdot13$: 직접 탐색하면 $325=1^2+18^2=6^2+17^2=10^2+15^2$ — 세 가지 표현이 나온다. 서로 다른 $1\bmod4$ 소인수($5,13$)의 개수가 늘수록 표현 방식도 늘어나는 패턴을 보여준다(정확한 개수 공식은 이 위키 범위 밖이지만, 곱셈성 항등식을 $5=1^2+2^2$ 와 $13=2^2+3^2$ 의 서로 다른 조합 — $(uA-vB,\,uB+vA)$ 와 $(uA+vB,\,uB-vA)$ — 에 적용하면 여러 표현이 동시에 나오는 이유를 짐작할 수 있다).

예제 6 (불가능 케이스의 빠른 진단). $99=9\cdot11=3^2\cdot11$: $11\equiv3\bmod4$ 의 지수가 $1$(홀) → 불가. $\bmod4$ 로도 확인: $99\equiv3\pmod4$ 인데, 정리 1에 의해 두 제곱의 합은 절대 $3\bmod4$ 가 될 수 없으므로(합성수에도 같은 필요조건이 부분적으로 적용 — 단, $\bmod4$ 만으로는 충분조건이 안 됨에 주의, 예제 2의 $21$ 처럼 $\bmod4$ 조건과 무관하게 막히는 경우도 있다) 즉답 가능.

예제 7 ($101$, 더 큰 소수). $101\equiv1\pmod4$ → 두 제곱의 합. $101-1=100=10^2$ → $101=1^2+10^2$. (작은 소수일수록 $a$를 $1$부터 차례로 대입하는 탐색이 빠르다.)

흔한 오해와 함정

• "$p\equiv1\bmod4$ 인 합성수도 항상 두 제곱의 합"으로 오해 — 틀림. $21\equiv1\bmod4$ 인데($21=20+1$) $21=3\cdot7$, 둘 다 $3\bmod4$ 형 소인수가 홀수 차수라 불가. $\bmod4$ 조건은 소수에 대해서만 정확한 동치다. 합성수는 소인수분해 전체를 봐야 한다(일반 정리).
• 표현이 유일하다고 가정 — 틀림. 예제 5의 $325$ 처럼 서로 다른 $1\bmod4$ 소인수가 여럿이면 표현 방식도 여럿이다. 소수는 (순서·부호를 무시하면) 표현이 유일하지만 합성수는 아니다.
• "두 제곱의 합 ⟺ $\bmod4$ 로 $1$"을 합성수에도 그대로 적용 — $\bmod4$ 로 $1$ 인 것은 필요조건도 충분조건도 아니다(필요조건조차 아니다 — $2$는 두 제곱의 합이면서 $\bmod4$로 $2$, 그리고 합성수의 진짜 조건은 $3\bmod4$형 소인수의 짝수성이다).
• 곱셈성 항등식을 "어느 조합이든 다 된다"로 오해 — $(uA+vB)^2+(vA-uB)^2$ 와 $(uA-vB)^2+(vA+uB)^2$ 는 부호 선택에 따라 서로 다른(때로는 같은) 표현을 준다. 항등식 자체는 항상 성립하지만 어떤 조합이 새로운 표현을 주는지는 직접 계산해 확인해야 한다.
• 하강법을 "한 번에 끝나는 트릭"으로 오해 — Fermat 하강은 배수 $M$ 이 매 단계 엄격히 줄어드는 것을 보장할 뿐, $M\to1$ 까지 몇 단계가 걸릴지는 사전에 알 수 없다(예제 3은 $170\to13\to1$ 두 단계였지만 일반적으로 더 걸릴 수 있다).

큰 그림 / 연결

이 정리는 이차잉여의 보충법칙("$-1$ 이 QR ⟺ $p\equiv1\bmod4$")을 정수 등식으로 번역한 첫 사례이며, 증명 기법인 Fermat의 하강법은 정수론 전역에서 "해가 없음" 또는 "최소해의 존재"를 보이는 표준 도구로 재등장한다(예: $x^4+y^4=z^2$ 의 해 없음, 피타고라스 세 쌍 관련 논의). 가장 개념적으로 깨끗한 설명은 가우스 정수 $\mathbb{Z}[i]$ 에서 나온다 — $p\equiv1\bmod4$ 인 소수는 $\mathbb{Z}[i]$ 에서 $p=\pi\bar\pi=(a+bi)(a-bi)=a^2+b^2$ 로 쪼개지고, $p\equiv3\bmod4$ 는 쪼개지지 않는다(가우스 소수로 남는다); 곱셈성 항등식 자체도 가우스 정수 노름의 곱셈성 $N(\alpha\beta)=N(\alpha)N(\beta)$ 의 그림자다. 이 주제는 디오판토스 방정식의 더 넓은 풍경 — $a^2+b^2=c^2$(직각삼각형), $x^2-Dy^2=1$(Pell) — 과 나란히 놓인다: 모두 "이차형식이 어떤 정수를 표현하는가"라는 같은 질문의 변주다.

연습문제

1. $1$ 부터 $25$ 까지 두 제곱수의 합인 수를 모두 찾아라.
2. $p=101$ 을 두 제곱수의 합으로 나타내라.
3. $50$ 을 두 가지 방법으로 두 제곱수의 합으로 써라.
4. $99$ 가 두 제곱수의 합이 아님을 보여라.
5. 곱셈성으로 $25=5^2$ 를 두 제곱수의 합으로 나타내라(자명 외).
6. $441=3^2\cdot7^2$ 이 두 제곱수의 합인지 일반 판정 정리로 확인하라.
7. $p=37$ 이 두 제곱수의 합임을 직접 찾아 확인하라.
8. $325=5^2\cdot13$ 의 세 가지 표현을 모두 찾아라.
9. 정리 1의 증명을 따라 $p\equiv3\pmod4$ 인 소수가 절대 두 제곱의 합이 될 수 없음을 다시 서술하라.

관련 개념

• 이차잉여 — $-1$ 이 QR ($p\equiv1\bmod4$)인 것이 핵심 동치 조건
• 이차 상호법칙 — 보충법칙의 출처
• 가우스 정수 — $\mathbb{Z}[i]$ 의 인수분해로 가장 깔끔한 설명·재증명
• 피타고라스 세 쌍 — $a^2+b^2=c^2$, 같은 이차형식 가족의 다른 질문
• 펠 방정식 — $x^2-Dy^2=1$, 이차형식이 정수를 표현하는 또 다른 사례