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

mod 7 세계에서는 어떤 숫자가 절대 제곱수가 될 수 없을까요? 놀랍게도 3, 5, 6은 어떤 정수를 제곱해도 mod 7에서 나오지 않습니다.

이 글은 공식부터 시작하지 않습니다. 먼저 작은 표를 직접 만들어 보고, “제곱으로 만들 수 있는 나머지”와 “절대 만들 수 없는 나머지”를 구분해 보겠습니다. 그 질문이 바로 제곱잉여와 이차 합동식으로 이어집니다.

What this post covers

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

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

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

먼저 실험부터: mod 7에서 제곱들을 계산해 보자

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

$x$	$x^2$	mod 7에서의 나머지
0	0	0
1	1	1
2	4	4
3	9	2
4	16	2
5	25	4
6	36	1

따라서 mod 7에서 제곱으로 나타나는 나머지는

$$0, 1, 2, 4$$

입니다. 반면 3, 5, 6은 어떤 수의 제곱과도 같은 나머지가 아니므로 제곱잉여가 아닙니다.

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

선형 합동식

$$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에서는 어떤 규칙이 있는가?
• 이차 합동식은 몇 개의 해를 가지는가?

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

입문 단계에서 기억할 점

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

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

더 해보기: 손으로 계산하기

제곱잉여는 정의를 읽는 것보다 작은 mod에서 직접 제곱표를 만들어 보면 훨씬 잘 보입니다.

실험 1. mod 5에서 제곱 나머지

$x$	$x^2$	mod 5에서의 나머지
0	0	0
1	1	1
2	4	4
3	9	4
4	16	1

따라서 mod 5에서 제곱으로 나타나는 나머지는

$$0, 1, 4$$

입니다.

실험 2. mod 7에서 제곱 나머지

$x$	$x^2$	mod 7에서의 나머지
0	0	0
1	1	1
2	4	4
3	9	2
4	16	2
5	25	4
6	36	1

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

$$0, 1, 2, 4$$

입니다.

실험 3. 이차 합동식의 해 찾기

mod 7에서

$$x^2 \equiv 2 \pmod 7$$

을 만족하는 $x$를 표에서 찾으면 $x=3,4$입니다. 반면

$$x^2 \equiv 3 \pmod 7$$

은 표에 3이 없으므로 해가 없습니다.

패턴 발견

표에서 어떤 점이 보이나요?

• 모든 나머지가 제곱으로 나타나는 것은 아닙니다.
• $x$와 $n-x$는 같은 제곱 나머지를 만듭니다.
• 그래서 0을 제외하면 같은 제곱잉여가 보통 두 번씩 나타납니다.

예를 들어 mod 7에서

$$3^2 \equiv 4^2 \equiv 2 \pmod 7$$

입니다. 왜냐하면 $4 \equiv -3 \pmod 7$이고, 제곱하면 부호가 사라지기 때문입니다.

핵심은 이차 합동식은 “나머지 중 어떤 것이 제곱으로 만들어지는가”를 묻는 문제라는 점입니다.

이론 정리

제곱잉여와 이차 합동식

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

$$x^2 \equiv a \pmod n$$

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

반대로 그런 $x$가 존재하지 않으면 제곱잉여가 아닙니다.

입문 단계에서는 먼저 표를 만들어 가능한 제곱 나머지를 모두 찾는 방식이 가장 안전합니다. 이 표가 나중에 더 깊은 정리들의 출발점이 됩니다.

Python으로 확인하기

아래 코드는 mod $n$에서 가능한 제곱 나머지를 모두 계산합니다.

def quadratic_residues(n):
    residues = set()
    for x in range(n):
        residues.add((x * x) % n)
    return sorted(residues)

def solutions_to_square(a, n):
    solutions = []
    for x in range(n):
        if (x * x) % n == a % n:
            solutions.append(x)
    return solutions

for n in [5, 7]:
    print("mod", n, "제곱잉여:", quadratic_residues(n))

print("x^2 ≡ 2 (mod 7)의 해:", solutions_to_square(2, 7))
print("x^2 ≡ 3 (mod 7)의 해:", solutions_to_square(3, 7))

손으로 만든 표와 같은 결과가 나오는지 비교해 보세요.

Common mistakes

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

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

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

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

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

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

Silverman 교재 연결

이 글은 Silverman 《친절한 수론 길라잡이》(경문사)의 다음 내용과 연결됩니다.

• 20장-21장: 이차 잉여 관련 내용 - 어떤 같은 나머지를 가진 수들이 제곱으로 나타나는지, 즉 이차 잉여인지 판별하는 문제와 연결됩니다.
• 관련 정리/예제: 이 글은 입문 단계의 맛보기로, 작은 법 $m$에서 $x^2 \equiv a \pmod m$ 꼴의 이차 합동식을 표로 풀어 보며 이차 잉여의 감각을 만드는 데 초점을 둡니다. 이차 상호법칙의 본격적인 전개는 Silverman의 뒤쪽 장(21장-23장 흐름)에서 이어집니다.

연습 문제

아래 점검 퀴즈에서 학습한 내용을 확인해 보세요.

Wrap-up

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

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