[정수론 입문 시리즈 19편] 이차 합동식과 제곱잉여는 무엇을 보여 줄까?

합동식의 기본 계산, 역원, 선형 합동식, 중국인의 나머지 정리까지 왔다면 이제 “1차” 문제를 넘어설 준비가 된 것입니다. 그다음 단계에서 자주 만나는 질문은 이런 것입니다.

x^2 \equiv a \pmod n

이런 식은 언제 풀릴까요? 이 질문은 제곱잉여 개념으로 이어집니다.

What this post covers

이차 합동식이 무엇인지 설명합니다.
제곱잉여의 기본 의미를 소개합니다.
작은 예시로 어떤 수가 제곱잉여인지 확인합니다.
마지막 글의 응용 정리로 이어집니다.

이번 글에서 새로 나오는 용어

제곱잉여 (Quadratic Residue): 어떤 mod에서 어떤 수의 제곱과 합동인 수입니다.
합동 (Congruence): 같은 나머지를 가지는 관계입니다.
모듈러 연산 (Modular Arithmetic): 나머지를 기준으로 하는 계산입니다.
소수 (Prime Number): 정수론에서 기본 블록 역할을 하는 수입니다.

이차 합동식은 무엇이 다른가?

선형 합동식

ax \equiv b \pmod n

은 비교적 구조가 단순했습니다. 하지만

x^2 \equiv a \pmod n

처럼 제곱이 들어오면 문제의 성격이 달라집니다. 어떤 수는 제곱으로 나타날 수 있고, 어떤 수는 그렇지 않기 때문입니다.

제곱잉여란 무엇인가?

정수 $a$ 가 mod $n$ 에서 어떤 정수 $x$ 에 대해

x^2 \equiv a \pmod n

를 만족하면, $a$ 를 mod $n$ 에서의 제곱잉여라고 합니다.

즉, “어떤 수의 제곱으로 나타날 수 있는 나머지인가?”를 묻는 개념입니다.

예시. mod 7에서 제곱들을 계산해 보자

mod 7에서는 모든 정수가 결국 0, 1, 2, 3, 4, 5, 6 중 하나와 합동이므로, 이 일곱 값만 제곱해 보면 가능한 제곱 나머지를 모두 확인할 수 있습니다.

mod 7에서 0부터 6까지 제곱해 보면

$0^2 \equiv 0$
$1^2 \equiv 1$
$2^2 \equiv 4$
$3^2 \equiv 9 \equiv 2$
$4^2 \equiv 16 \equiv 2$
$5^2 \equiv 25 \equiv 4$
$6^2 \equiv 36 \equiv 1$

입니다.

따라서 mod 7에서 제곱잉여는

0, 1, 2, 4

입니다.

반면 3, 5, 6은 어떤 수의 제곱과도 합동이 아니므로 제곱잉여가 아닙니다.

왜 흥미로운가?

지금 단계에서는 단순히 표를 만들어 찾는 것처럼 보일 수 있습니다. 하지만 제곱잉여는 정수론의 훨씬 깊은 영역으로 이어집니다.

어떤 수가 제곱으로 나타나는가?
소수 mod에서는 어떤 규칙이 있는가?
이차 합동식은 몇 개의 해를 가지는가?

이 질문들은 더 깊은 대수적 구조와 연결됩니다.

입문 단계에서 기억할 점

이 글의 목표는 제곱잉여를 완전히 정복하는 것이 아닙니다. “합동식의 세계가 선형 문제에서 끝나지 않는다”는 점을 보는 것이 핵심입니다.

즉, 정수론은 약수와 소수에서 시작해, 합동식과 거듭제곱을 지나, 더 깊은 해 구조로 계속 확장됩니다.

Common mistakes

1. 선형 합동식처럼 항상 쉽게 풀릴 거라고 생각하는 실수

이차 합동식은 훨씬 까다롭습니다. 해가 없을 수도 있고, 여러 개일 수도 있습니다.

2. 표를 만드는 계산만 하고 개념을 놓치는 실수

중요한 것은 “어떤 나머지가 제곱으로 나타나는가”라는 구조 질문입니다.

3. mod가 바뀌어도 같은 결과를 기대하는 실수

제곱잉여 여부는 mod에 따라 달라집니다.

Wrap-up

이번 글에서는 제곱잉여를 통해 이차 합동식이 선형 합동식보다 더 깊은 구조를 가진다는 점을 맛보기로 살펴봤습니다.

다음 글에서는 시리즈를 마무리하면서, 지금까지의 내용을 RSA 같은 응용과 연결하고 앞으로의 학습 방향을 정리하겠습니다.