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

지난 글에서 베주 항등식을 통해 $\gcd(a,b)$를 $ax+by$ 꼴로 표현할 수 있다는 점을 봤습니다. 이제 자연스럽게 다음 질문이 나옵니다.

$$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=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$는 항상 정수해를 가집니다.

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

Common mistakes

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

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

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

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

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

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

Wrap-up

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

$$ax + by = c$$

가 정수해를 가질 필요충분조건이

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

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

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