[정수론 입문 시리즈 7편] 1차 디오판토스 방정식은 언제 정수해를 가질까?

학교 앱에서 리워드 포인트를 만든다고 해 봅시다. 5점짜리 활동 포인트와 7점짜리 쿠폰만 써서 정확히 100점을 만들 수 있을까요?

$$100 = 5x + 7y$$

처럼 쓸 수 있다면 가능합니다. 여기서 $x,y$는 사용한 포인트와 쿠폰의 개수이므로 정수여야 합니다.

이처럼 $ax+by=c$ 꼴에서 정수해가 있는지를 묻는 문제가 1차 디오판토스 방정식의 출발점입니다.

What this post covers

• 1차 디오판토스 방정식의 의미를 설명합니다.
• $ax+by=c$가 언제 정수해를 가지는지 정리합니다.
• 실제 예시로 해가 있는 경우와 없는 경우를 비교합니다.
• 이 주제가 이후 합동식 문제와 어떻게 이어지는지 봅니다.

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

• 1차 디오판토스 방정식 (Linear Diophantine Equation): 정수해를 찾는 $ax+by=c$ 꼴의 방정식입니다.
• 베주 항등식 (Bézout's Identity): $\gcd(a,b)$를 $ax+by$ 꼴로 표현할 수 있다는 정리입니다.
• 최대공약수 (Greatest Common Divisor): 두 정수가 공통으로 가지는 약수들 가운데 가장 큰 수입니다.
• 서로소 (Coprime): 두 수의 최대공약수가 1인 관계입니다.

디오판토스 방정식이란 무엇인가?

보통 방정식은 실수해나 복소수해를 찾는 문제로 많이 만납니다. 하지만 정수론에서는 해가 정수인지 아닌지가 더 중요할 때가 많습니다.

예를 들어

$$3x + 5y = 1$$

에서 실수해는 아주 많습니다. 하지만 정수해는 아무렇게나 나오지 않습니다. 이렇게 정수해를 찾는 방정식을 디오판토스 방정식이라고 합니다.

즉, 디오판토스 방정식의 핵심은 "방정식을 풀 수 있는가?"보다 "정수 조건까지 만족하는가?"에 있습니다.

이 글에서는 가장 기본적인 1차 형태

$$ax + by = c$$

만 다룹니다.

실험: 손으로 계산하기

먼저 정리를 외우기 전에, 왼쪽 $ax+by$가 실제로 어떤 값들을 만드는지 손으로 확인해 봅시다.

실험 1. $6x+9y$가 만드는 값

작은 정수 $x,y$를 넣어 봅니다.

$x$	$y$	$6x+9y$
1	0	6
0	1	9
2	-1	3
-1	1	3
1	-1	-3

나오는 값들이 모두 3의 배수라는 점을 확인할 수 있습니다.

실험 2. 오른쪽 값을 바꾸어 보기

같은 왼쪽 $6x+9y$에 대해 오른쪽 값을 바꾸면 어떻게 될까요?

방정식	$\gcd(6,9)$	정수해 가능성	한 예
$6x+9y=3$	3	가능	$x=2,y=-1$
$6x+9y=6$	3	가능	$x=1,y=0$
$6x+9y=4$	3	불가능	4는 3의 배수가 아님
$6x+9y=12$	3	가능	$x=2,y=0$

실험 3. 서로소 계수도 확인하기

이번에는 $4x+7y$를 봅시다. $\gcd(4,7)=1$입니다.

• $4(2)+7(-1)=1$
• $4(4)+7(-2)=2$
• $4(6)+7(-3)=3$

서로소인 두 계수에서는 작은 오른쪽 값들도 차례로 만들 수 있다는 감각이 생깁니다.

패턴 발견

위 실험에서 어떤 패턴이 보이나요?

• $6x+9y$는 어떤 정수 $x,y$를 넣어도 3의 배수만 만듭니다.
• 그래서 오른쪽 $c$가 3의 배수가 아니면 정수해가 나올 수 없습니다.
• 반대로 $c$가 3의 배수이면 베주 항등식의 한 해를 적당히 확대해서 해를 만들 수 있습니다.
• $a,b$가 서로소이면 최대공약수가 1이므로 모든 $c$에 대해 가능성이 열립니다.

핵심 통찰은 왼쪽 $ax+by$가 아무 정수나 만드는 것이 아니라, 항상 $\gcd(a,b)$의 배수만 만든다는 점입니다.

언제 정수해가 존재할까?

핵심 정리는 다음과 같습니다.

$ax+by=c$가 정수해를 가지려면, 그리고 그럴 때에만 $\gcd(a,b)$가 $c$를 나눕니다.

즉,

$$\gcd(a,b) \mid c$$

여야 하고, 또 이것만 만족하면 실제로 정수해를 만들 수 있습니다.

왜 이 조건이 나올까?

먼저 $d = \gcd(a,b)$라고 합시다.

그러면 $d$는 $a$와 $b$를 모두 나눕니다. 따라서 어떤 정수 $x,y$에 대해서도

$$ax + by$$

는 항상 $d$의 배수입니다. 즉, 왼쪽 전체가 $d$의 배수이므로 오른쪽 $c$도 $d$의 배수여야 합니다.

반대로 $d \mid c$라고 합시다. 그러면 $c = dk$로 쓸 수 있습니다. 베주 항등식에 의해

$$ax_0 + by_0 = d$$

가 되는 정수 $x_0,y_0$가 있으므로 양변에 $k$를 곱하면

$$a(kx_0) + b(ky_0) = dk = c$$

가 됩니다. 따라서 정수해가 존재합니다.

이 정리는 조건이 아주 간단합니다.

• $\gcd(a,b) \mid c$이면 정수해가 있고
• $\gcd(a,b) \nmid c$이면 정수해가 없습니다.

그래서 1차 디오판토스 방정식에서는 먼저 공식을 풀기보다 최대공약수부터 확인하는 습관이 중요합니다.

예시 1. 해가 있는 경우

다음 식을 봅시다.

$$6x + 9y = 3$$

여기서

$$\gcd(6,9) = 3$$

이고, 3은 오른쪽의 3을 나눕니다. 따라서 정수해가 존재합니다.

실제로

$$6(2) + 9(-1) = 12 - 9 = 3$$

이므로 $x=2, y=-1$은 한 개의 정수해입니다.

여기서는 해를 하나만 찾았지만, 핵심은 먼저 "해가 존재한다"는 사실을 판정하는 것입니다.

예시 2. 해가 없는 경우

이번에는

$$6x + 9y = 4$$

를 봅시다.

여전히

$$\gcd(6,9) = 3$$

이지만, 3은 4를 나누지 못합니다. 따라서 이 식은 정수해를 가질 수 없습니다.

실수해는 있더라도, 정수해는 없습니다. 정수론에서는 바로 이 차이가 중요합니다.

한 개의 해를 찾은 뒤에는?

1차 디오판토스 방정식은 정수해가 하나만 있는 경우가 드뭅니다. 보통 한 개의 해를 찾으면 다른 해들도 연쇄적으로 얻을 수 있습니다.

예를 들어 $ax+by=c$에서 한 해 $(x_0,y_0)$를 알면, 해 전체의 구조를 일반식으로 쓸 수 있습니다. 이 부분은 지금 단계에서는 “해가 한 점이 아니라 패턴을 가진다” 정도로만 기억해도 충분합니다. 중요한 것은 1차 디오판토스 방정식이 보통 "답 하나 찾고 끝"이 아니라, "해의 구조 전체를 본다"는 문제라는 점입니다.

서로소일 때 더 단순해진다

만약 $a$와 $b$가 서로소라면

$$\gcd(a,b)=1$$

입니다. 그러면 1은 모든 정수를 나누므로, $ax+by=c$는 항상 정수해를 가집니다.

이 점은 이후 모듈러 연산에서 역원을 찾을 때도 핵심 역할을 합니다.

이론 정리

1차 디오판토스 방정식의 존재 조건

정수 $a,b,c$에 대해 $d=\gcd(a,b)$라고 하자. 그러면

$$ax+by=c$$

가 정수해 $x,y$를 가지려면, 그리고 그럴 때에만

$$d \mid c$$

이다. 특히 $\gcd(a,b)=1$이면 모든 정수 $c$에 대해 정수해가 존재한다.

Python으로 확인하기

아래 코드는 작은 범위에서 $6x+9y=c$의 해가 실제로 존재하는지 확인합니다.

from math import gcd

def has_solution_by_search(a, b, c, limit=20):
    for x in range(-limit, limit + 1):
        for y in range(-limit, limit + 1):
            if a * x + b * y == c:
                return True, (x, y)
    return False, None

for c in [3, 4, 6, 12]:
    a, b = 6, 9
    possible_by_theory = (c % gcd(a, b) == 0)
    found, solution = has_solution_by_search(a, b, c)
    print(c, possible_by_theory, found, solution)

실행해 보면 $c$가 $\gcd(6,9)=3$의 배수일 때만 해가 발견됩니다.

Common mistakes

1. 실수해가 있으면 정수해도 있다고 생각하는 실수

정수론에서는 정수 조건이 핵심입니다. 실수해의 존재와 정수해의 존재는 전혀 다른 문제입니다.

2. 최대공약수만 구하고 조건을 확인하지 않는 실수

$\gcd(a,b)$를 구한 뒤, 반드시 그것이 오른쪽의 $c$를 나누는지 확인해야 합니다.

3. 해가 한 개뿐이라고 생각하는 실수

1차 디오판토스 방정식은 보통 해가 하나가 아니라 여러 개입니다. 먼저 “존재 조건”을 이해하고, 그 다음에 해의 일반형으로 넘어가면 됩니다.

Silverman 교재 연결

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

• 6장: 선형방정식과 최대공약수 - 베주 항등식 $ax+by=\gcd(a,b)$에서 출발해, 오른쪽이 일반 정수 $c$인 1차 디오판토스 방정식 $ax+by=c$로 확장합니다.
• 관련 정리/예제: $d=\gcd(a,b)$일 때 정수해 존재 조건은 $d \mid c$입니다. 이는 6장의 선형방정식 논의를 베주 항등식의 배수로 일반화한 형태입니다.

연습 문제

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

Wrap-up

이번 글에서는 1차 디오판토스 방정식

$$ax + by = c$$

가 정수해를 가지려면, 그리고 그럴 때에만

$$\gcd(a,b) \mid c$$

라는 점을 정리했습니다. 이 조건은 베주 항등식과 바로 연결됩니다.

다음 글에서는 정수론에서 빠질 수 없는 또 하나의 큰 축인 소수로 넘어가, 정수의 구조를 더 잘게 쪼개 보는 관점을 소개하겠습니다.