1.1 The Euclidean Algorithm · 유클리드 호제법
표기. $\mathbb{Z}$(각각 $\mathbb{Q}, \mathbb{R}, \mathbb{C}$)는 정수(각각 유리수, 실수, 복소수) 전체의 집합을 나타낸다.
Notation. $\mathbb{Z}$(resp. $\mathbb{Q}, \mathbb{R}, \mathbb{C}$) denotes the set of integers (resp. rational numbers, real numbers, complex numbers).
$a$와 $b$를 주어진 정수라 하고, 이 중 적어도 하나는 0이 아니라고 하자. $a$와 $b$의 최대공약수는 $\gcd(a, b)$로 나타낸다.
Let $a$ and $b$ be given integers, with at least one of them different form zero. The greatest common divisor of $a$ and $b$ is denoted by $\gcd(a, b)$.
$a = 3\cdot5^2\cdot7$, $b = 2\cdot5^2\cdot7\cdot11$이면 $\gcd(a, b) = 5^2\cdot7$임을 안다.
For $a = 3\cdot5^2\cdot7$ and $b = 2\cdot5^2\cdot7\cdot11$, we know that $\gcd(a, b) = 5^2\cdot7$.
$\gcd(a, b)$는 어떻게 구할까? 소인수분해는 어렵다는 점에 주의하자. 따라서 소인수분해 없이 $\gcd(a, b)$를 구하기 위해 유클리드 호제법을 사용할 것이다. 나눗셈 알고리즘과 유클리드 호제법을 소개하자.
How to find $\gcd(a, b)$? Note that prime factorization is hard. Therefore we will use the Euclidean algorithm to find $\gcd(a, b)$ without prime factorization. Let introduce the division algorithm and the Euclidean algorithm.
입력 : $a, b \in \mathbb{Z}$이고 $b \neq 0$.
출력 : $a = qb + r$이고 $0 \le r \lt |b|$.
Input : $a, b \in \mathbb{Z}$ and $b \neq 0$.
Output : $a = qb + r$ and $0 \le r \lt |b|$.
입력 : 0이 아닌 정수 $a, b(|a| \ge |b|)$.
출력 : 입력 정수 $a$와 $b$의 $\gcd(a, b)$.
- $r_0 = b$라 하자.
- 나눗셈 알고리즘에 의해 $a = q_1 b + r_1$이고 $0 \le r_1 \lt |b|$인 $r_1, q_1$이 존재한다.
- $r_i \neq 0$이면, $r_{i-1} = q_{i+1} r_i + r_{i+1}$이고 $0 \le r_{i+1} \lt r_i$인 $q_{i+1}, r_{i+1}$이 존재한다. (나눗셈 알고리즘을 이용)
- $r_i = 0$이면, $\gcd(a, b) = r_{i-1}$이다.
Input : nonzero integers $a, b(|a| \ge |b|)$.
Output : $\gcd(a, b)$ of the input integers $a$ and $b$.
- Let $r_0 = b$.
- By the division algorithm, there exists $r_1, q_1$ such that $a = q_1 b + r_1$ and $0 \le r_1 \lt |b|$.
- If $r_i \neq 0$, then there exists $q_{i+1}, r_{i+1}$ such that $r_{i-1} = q_{i+1} r_i + r_{i+1}$ and $0 \le r_{i+1} \lt r_i$. (Using the division algorithm)
- If $r_i = 0$, then $\gcd(a, b) = r_{i-1}$.
1. 15와 3의 최대공약수를 구하자.
따라서 $\gcd(15, 3) = r_0 = 3$이다.
2. 15와 6의 최대공약수를 구하자.
따라서 $\gcd(15, 6) = r_1 = 3$이다.
1. Find the greatest common divisor of 15 and 3.
Therefore $\gcd(15, 3) = r_0 = 3$.
2. Find the greatest common divisor of 15 and 6.
Therefore $\gcd(15, 6) = r_1 = 3$.
0이 아닌 어떤 정수 $a, b(|a| \ge |b|)$에 대하여 유클리드 호제법을 정수 $a, b$에 적용하자. $r_3 = 0$이라 하자. 즉,
$r_1 = a - bq_1$이고 $a, b$는 $\gcd(a, b)$의 배수임을 안다. 그러므로 $r_1$은 $\gcd(a, b)$의 배수이다. 마찬가지로 $r_2 = b - r_1 q_2$이고 $b, r_1$은 $\gcd(a, b)$의 배수임을 안다. 그러므로 $r_2$는 $\gcd(a, b)$의 배수이다. $r_2 = \gcd(a, b)$의 나머지 증명은 생략한다.
For some nonzero integers $a, b(|a| \ge |b|)$, apply the Euclidean algorithm to integers $a, b$. Assume that $r_3 = 0$. In other words,
We know that $r_1 = a - bq_1$ and $a, b$ are multiple of $\gcd(a, b)$. So $r_1$ is multiple of $\gcd(a, b)$. Similarly, we know that $r_2 = b - r_1 q_2$ and $b, r_1$ are multiple of $\gcd(a, b)$. So $r_2$ is multiple of $\gcd(a, b)$. The remaining proof of $r_2 = \gcd(a, b)$ is omitted.
1.2 Solving the Diophantine Equation ax + by = c · 디오판토스 방정식 ax + by = c의 풀이
$a, b, c \in \mathbb{Z}$라 하자. $ax + by = c$는 어떻게 풀까? 더 구체적으로는 ‘$ax + by = c$가 해를 가지는가?’와 ‘$ax + by = c$의 모든 해를 구하라’가 궁금하다. 먼저 ‘$ax + by = c$가 해를 가지는가?’에 대해 이야기하자.
Let $a, b, c \in \mathbb{Z}$. How to solve $ax + by = c$? More specifically, we are curious about ‘$ax + by = c$ has a solution?’ and ‘Find the all solutions of $ax + by = c$’. At first, let’s talk about ‘$ax + by = c$ has a solution?’.
0이 아닌 정수 $a$와 $b$에 대하여 $T = \{ax + by|x, y \in \mathbb{Z}\}$라 하자. 그러면 $T$는 $\gcd(a, b)$의 배수 전체의 집합이다.
For nonzero integers $a$ and $b$, let $T = \{ax + by|x, y \in \mathbb{Z}\}$. Then $T$ is the set of all multiple of $\gcd(a, b)$.
예를 들어 $\{6x + 9y\} = \{3n|n \in \mathbb{Z}\}$이다. $ax + by = c$가 정수해를 가질 필요충분조건은 $\gcd(a, b) \mid c$임에 주목하자. 그러므로 $ax_0 + by_0 = \gcd(a, b)$인 $x_0, y_0 \in \mathbb{Z}$가 존재한다. $c = \gcd(a, b)m$이면 $a(mx_0) + b(my_0) = c$이다. $\gcd(a, b) \nmid c$이면 $ax + by = c$는 정수해를 갖지 않는다. $c$가 $\gcd(a, b)$일 때 $ax + by = c$의 해를 구할 수 있다면, $c$가 $\gcd(a, b)$의 배수일 때도 해를 구할 수 있다. $c = \gcd(a, b)$인 $ax + by = c$의 정수해를 구하는 알고리즘을 소개하자.
역주. 원문은 “$c|(a, b)$”로 인쇄되어 있으나 이는 표기 오류이며, 뜻은 $\gcd(a, b) \mid c$이다(§1.3에는 $\gcd(a, b)|c$로 바르게 인쇄되어 있다).
For example, $\{6x + 9y\} = \{3n|n \in \mathbb{Z}\}$. Remark $ax + by = c$ has an integral solution if and only if $c|(a, b)$. Therefore there exists $x_0, y_0 \in \mathbb{Z}$ such that $ax_0 + by_0 = \gcd(a, b)$. If $c = \gcd(a, b)m$, then $a(mx_0) + b(my_0) = c$. If $\gcd(a, b) \nmid c$, then $ax + by = c$ has no integral solution. If we can find the root of $ax + by = c$ when $c$ is $\gcd(a, b)$, we can also find the root when $c$ is a multiple of $\gcd(a, b)$. Let introduce an algorithm to find an integral solution of $ax + by = c$ such that $c = \gcd(a, b)$.
입력 : $c = \gcd(a, b)$이고 $|a| \ge |b|$인 $ax + by = c$.
출력 : $ax_0 + by_0 = c$인 정수해 $x_0, y_0$.
- $r_0 = b$, $m_1 = 1$이라 하자.
- 나눗셈 알고리즘에 의해 $r_1 = a - q_1 b$이고 $0 \le r_1 \lt |b|$인 $r_1, q_1$이 존재한다. $n_1 = -q_1$이라 하자. 그러면 $r_1 = m_1 a + n_1 b$이다.
- 나눗셈 알고리즘에 의해 $r_0 = q_2 r_1 + r_2$이고 $0 \le r_2 \lt r_1$인 $r_2, q_2$가 존재한다. $m_2 = -q_2$, $n_2 = 1 + q_1 q_2$라 하자. 그러면 $r_2 = m_2 a + n_2 b$이다.
- $r_i \neq \gcd(a, b)$이면, $r_{i-1} = q_{i+1} r_i + r_{i+1}$이고 $0 \le r_{i+1} \lt r_i$인 $r_{i+1}, q_{i+1}$이 존재한다. $m_{i+1} = m_{i-1} - q_{i+1} m_i$, $n_{i+1} = n_{i-1} - q_{i+1} n_i$라 하자. 그러면 $r_{i+1} = m_{i+1} a + n_{i+1} b$이다.
- $r_i = \gcd(a, b)$이면, $x_0 = m_i$, $y_0 = n_i$이다.
Input : $ax + by = c$ such that $c = \gcd(a, b)$ and $|a| \ge |b|$.
Output : an integral solution $x_0, y_0$ such that $ax_0 + by_0 = c$.
- Let $r_0 = b$ and $m_1 = 1$.
- By the division algorithm, there exists $r_1, q_1$ such that $r_1 = a - q_1 b$ and $0 \le r_1 \lt |b|$. Let $n_1 = -q_1$. Then $r_1 = m_1 a + n_1 b$.
- By the division algorithm, there exists $r_2, q_2$ such that $r_0 = q_2 r_1 + r_2$ and $0 \le r_2 \lt r_1$. Let $m_2 = -q_2$ and $n_2 = 1 + q_1 q_2$. Then $r_2 = m_2 a + n_2 b$.
- If $r_i \neq \gcd(a, b)$, then there exists $r_{i+1}, q_{i+1}$ such that $r_{i-1} = q_{i+1} r_i + r_{i+1}$ and $0 \le r_{i+1} \lt r_i$. Let $m_{i+1} = m_{i-1} - q_{i+1} m_i$ and $n_{i+1} = n_{i-1} - q_{i+1} n_i$. Then $r_{i+1} = m_{i+1} a + n_{i+1} b$.
- If $r_i = \gcd(a, b)$, then $x_0 = m_i$ and $y_0 = n_i$.
소인수분해를 이용하여 $\gcd(65, 105)$를 구하라.
$65 = 5 \times 13$이고 $105 = 3 \times 5 \times 7$이므로, 두 소인수분해에 공통으로 나타나는 소인수는 $5$뿐이다. 따라서 $\gcd(65, 105) = 5$이다.
Find $\gcd(65, 105)$ by using prime factorization.
Since $65 = 5 \times 13$ and $105 = 3 \times 5 \times 7$, the only prime factor common to both factorizations is $5$. Therefore $\gcd(65, 105) = 5$.
유클리드 호제법으로 $\gcd(a, b)$를 구하라.
1. $\gcd(65, 105)$
2. $\gcd(202, 98)$
1. 유클리드 호제법(algo01-2)을 $a = 105$, $b = 65$에 적용하면 $r_0 = 65$이고
이다. 즉 $r_1 = 40, r_2 = 25, r_3 = 15, r_4 = 10, r_5 = 5, r_6 = 0$이므로, $\gcd(65, 105) = r_5 = 5$이다.
2. 같은 알고리즘을 $a = 202$, $b = 98$에 적용하면 $r_0 = 98$이고
이다. 즉 $r_1 = 6, r_2 = 2, r_3 = 0$이므로, $\gcd(202, 98) = r_2 = 2$이다.
Find $\gcd(a, b)$ by Euclidean algorithm.
1. $\gcd(65, 105)$
2. $\gcd(202, 98)$
1. Applying the Euclidean algorithm (algo01-2) with $a = 105$, $b = 65$ gives $r_0 = 65$ and
that is, $r_1 = 40, r_2 = 25, r_3 = 15, r_4 = 10, r_5 = 5, r_6 = 0$, so $\gcd(65, 105) = r_5 = 5$.
2. Applying the same algorithm with $a = 202$, $b = 98$ gives $r_0 = 98$ and
that is, $r_1 = 6, r_2 = 2, r_3 = 0$, so $\gcd(202, 98) = r_2 = 2$.
다음 명제를 완성하라.
“$ax+by=c\ (a,b,c\in\mathbb{Z})$는 정수해를 가진다 $\iff$ $\boxed{\qquad\qquad}$”
빈칸에 들어갈 조건은 $\gcd(a, b) \mid c$이다. 즉 완성된 명제는 다음과 같다.
“$ax + by = c\ (a, b, c \in \mathbb{Z})$는 정수해를 가진다 $\iff$ $\gcd(a, b) \mid c$”
정리 1.4에 의해 $T = \{ax + by \mid x, y \in \mathbb{Z}\}$는 $\gcd(a, b)$의 배수 전체의 집합이므로, $c \in T$인 것, 즉 $ax + by = c$가 정수해를 가지는 것의 필요충분조건은 $c$가 $\gcd(a, b)$의 배수인 것, 다시 말해 $\gcd(a, b) \mid c$인 것이다.
Complete the following statement.
“$ax + by = c(a, b, c \in \mathbb{Z})$has an integral solution if and only if $\boxed{\qquad\qquad}$”
The condition that fills the blank is $\gcd(a, b) \mid c$. That is, the completed statement reads
“$ax + by = c\ (a, b, c \in \mathbb{Z})$ has an integral solution $\iff$ $\gcd(a, b) \mid c$”
By Theorem 1.4, $T = \{ax + by \mid x, y \in \mathbb{Z}\}$ is the set of all multiples of $\gcd(a, b)$, so $c \in T$ — that is, $ax + by = c$ has an integral solution — if and only if $c$ is a multiple of $\gcd(a, b)$, i.e. $\gcd(a, b) \mid c$.
$56x + 72y = 8$인 정수해를 구하라.
$x$와 $y$를 바꾸자. $72x + 56y = 8$인 정수해를 구하자.
- $r_0 = 56$, $m_1 = 1$.
- $r_1 = 16 = 72 - 1 \times 56$, $q_1 = 1$.
- $r_2 = 8 = 56 - 3 \times 16$, $q_2 = 3, m_2 = -3, n_2 = 4$. 그러면 $r_2 = -3 \times 72 + 4 \times 56$이다.
- $0 = r_3 = 16 - 2 \times 8$.
그러므로 $8 = -3 \times 72 + 4 \times 56$이다.
다시 $x$와 $y$를 바꾸면 $(x, y) = (4, -3)$은 정수해이다.
Find an integral solution such that $56x + 72y = 8$.
Replace $x$ and $y$. Find an integral solution such that $72x + 56y = 8$.
- $r_0 = 56$, $m_1 = 1$.
- $r_1 = 16 = 72 - 1 \times 56$, $q_1 = 1$.
- $r_2 = 8 = 56 - 3 \times 16$, $q_2 = 3, m_2 = -3, n_2 = 4$. Then $r_2 = -3 \times 72 + 4 \times 56$.
- $0 = r_3 = 16 - 2 \times 8$.
Therefore we have $8 = -3 \times 72 + 4 \times 56$.
Replace $x$ and $y$ again, then $(x, y) = (4, -3)$ is an integral solution.
1.3 Find all of integral solutions of ax + by = c (a, b, c ∈ ℤ) · ax + by = c의 모든 정수해
표기. 이 절에서 해라고 쓰면 정수해를 뜻한다.
$ax + by = c$가 해를 가질 필요충분조건은 $\gcd(a, b)|c$임에 주의하라.
다음 공식을 관찰하자. $ax_0 + by_0 = c$이고 $ax_n + by_n = 0$이면, $a(x_0 + x_n) + b(y_0 + y_n) = c$이다. 그러므로 $(x, y) = (x_0 + x_n, y_0 + y_n)$은 $ax + by = c$의 또 다른 해이다. $ax_0 + by_0 = c$이고 $ax'_0 + by'_0 = c$이면, $a(x_0 - x'_0) + b(y_0 - y'_0) = 0$이다. 그러므로 $(x, y) = (x_0 - x'_0, y_0 - y'_0)$는 $ax + by = 0$의 해이다. 동차방정식 $ax+by=0$의 해를 구하는 일이 $ax+by=c$의 해를 구하는 데 중요함에 주의하라.
역주. 원문은 둘째 가정을 “$ax'_n + by'_n = 0$”으로 인쇄했으나 이는 오타이다. 이어지는 결론 $a(x_0 - x'_0) + b(y_0 - y'_0) = 0$은 $(x'_0, y'_0)$ 역시 $ax + by = c$의 해일 때, 즉 $ax'_0 + by'_0 = c$일 때 성립한다(두 해의 차가 동차방정식의 해가 된다).
Notation. When we write solution, it means integer solution.
Note that $ax + by = c$ has a solution if and only if $\gcd(a, b)|c$.
Observe the following formula. If $ax_0 + by_0 = c$ and $ax_n + by_n = 0$, then $a(x_0 + x_n) + b(y_0 + y_n) = c$. Therefore $(x, y) = (x_0 + x_n, y_0 + y_n)$ is another solution of $ax + by = c$. If $ax_0 + by_0 = c$ and $ax'_n + by'_n = 0$, then $a(x_0 - x'_0) + b(y_0 - y'_0) = 0$. Therefore $(x, y) = (x_0 - x'_0, y_0 - y'_0)$ is solution of $ax + by = 0$. Note that find a solution of homogeneous equation ($ax + by = 0$) is important for finding solution of $ax + by = c$.
$a, b, c \in \mathbb{Z}$라 하자. $(x, y) = (x_0, y_0)$가 $ax + by = c$의 정수해라 하자. 그러면 $(x', y')$가 $ax + by = c$의 해일 필요충분조건은 다음과 같다.
단, $ax_n + by_n = 0$인 어떤 $(x_n, y_n) \in \mathbb{Z} \times \mathbb{Z}$에 대해서이다.
Let $a, b, c \in \mathbb{Z}$. Assume that $(x, y) = (x_0, y_0)$ is an integral solution of $ax + by = c$. Then $(x', y')$ is a solution of $ax + by = c$ if and only if
for some $(x_n, y_n) \in \mathbb{Z} \times \mathbb{Z}$ such that $ax_n + by_n = 0$.
$ax + by = c$의 모든 해를 구하려면 $ax + by = 0$의 모든 해를 구해야 한다. $ax + by = 0$의 모든 정수해를 구하자. $a = a'\gcd(a, b)$, $b = b'\gcd(a, b)$라 하자. 그러면 $(a', b') = 1$이다.
To find all solutions of $ax + by = c$, we need to find all solutions of $ax + by = 0$. Let’s find all integral solutions of $ax + by = 0$. Let $a = a'\gcd(a, b)$ and $b = b'\gcd(a, b)$. Then $(a', b') = 1$.
방정식 $ax + by = 0$의 모든 해는 다음과 같이 주어진다.
여기서 $n$은 임의의 정수이다.
Every solution of equation $ax + by = 0$ is given by
where $n$ is an arbitrary integer.
$ax + by = c$의 모든 해를 구하는 방법을 정리하면 다음과 같다.
1. $ax_0 + by_0 = c$인 특수해 $(x_0, y_0)$를 구한다.
2. $ax + by = c$의 일반해는 어떤 $n \in \mathbb{Z}$에 대하여 $x = x_0 + \dfrac{b}{\gcd(a, b)}n, y = y_0 - \dfrac{a}{\gcd(a, b)}n$로 나타난다.
To summarize how to find all solutions of $ax + by = c$.
1. Find a particular solution $(x_0, y_0)$ such that $ax_0 + by_0 = c$.
2. General solution of $ax + by = c$ is represented by $x = x_0 + \dfrac{b}{\gcd(a, b)}n, y = y_0 - \dfrac{a}{\gcd(a, b)}n$ for some $n \in \mathbb{Z}$.
$ax + by = 0$의 모든 정수해를 구하라.
1. $120x + 24y = 0$.
2. $256x + 30y = 0$.
1. $120 = 5 \times 24$이므로 $\gcd(120, 24) = 24$이다. 정리 1.10에 의해 $120x + 24y = 0$의 모든 정수해는
로 주어진다.
2. 유클리드 호제법으로 $\gcd(256, 30)$을 구하면
이므로 $\gcd(256, 30) = 2$이다. 정리 1.10에 의해 $256x + 30y = 0$의 모든 정수해는
로 주어진다.
Find all integral solutions of $ax + by = 0$.
1. $120x + 24y = 0$.
2. $256x + 30y = 0$.
1. Since $120 = 5 \times 24$, $\gcd(120, 24) = 24$. By Theorem 1.10, every integral solution of $120x + 24y = 0$ is given by
2. Computing $\gcd(256, 30)$ by the Euclidean algorithm,
so $\gcd(256, 30) = 2$. By Theorem 1.10, every integral solution of $256x + 30y = 0$ is given by
$ax + by = c$의 특수해를 구하라.
- $172x + 20y = 1000$.
- $278x + 102y = 2$.
$172x + 20y = 1000$. 먼저 알고리즘(algo01-3)으로 $172x + 20y = \gcd(172, 20)$의 정수해를 구한다.
- $r_0 = 20$, $m_1 = 1$.
- $r_1 = 12 = 172 - 8 \times 20$, $q_1 = 8$.
- $r_2 = 8 = 20 - 1 \times 12$, $q_2 = 1, m_2 = -1, n_2 = 9$. 그러면 $r_2 = -172 + 9 \times 20$이다.
- $r_3 = 4 = 12 - 1 \times 8$, $q_3 = 1, m_3 = 2, n_3 = -17$. 그러면 $r_3 = 2 \times 172 - 17 \times 20 = 4 = \gcd(172, 20)$이다.
그러므로 $2 \times 172 - 17 \times 20 = 4$이다. $1000 = 4 \times 250$이므로 양변에 $250$을 곱하면 $172 \times 500 - 20 \times 4250 = 1000$을 얻는다. 따라서 $(x_0, y_0) = (500, -4250)$은 정수해이다. (검산: $172 \times 500 - 20 \times 4250 = 86000 - 85000 = 1000$.)
$278x + 102y = 2$. 같은 알고리즘을 $a = 278$, $b = 102$에 적용한다.
- $r_0 = 102$, $m_1 = 1$.
- $r_1 = 74 = 278 - 2 \times 102$, $q_1 = 2$.
- $r_2 = 28 = 102 - 1 \times 74$, $q_2 = 1, m_2 = -1, n_2 = 3$. 그러면 $r_2 = -278 + 3 \times 102$이다.
- $r_3 = 18 = 74 - 2 \times 28$, $q_3 = 2, m_3 = 3, n_3 = -8$. 그러면 $r_3 = 3 \times 278 - 8 \times 102$이다.
- $r_4 = 10 = 28 - 1 \times 18$, $q_4 = 1, m_4 = -4, n_4 = 11$. 그러면 $r_4 = -4 \times 278 + 11 \times 102$이다.
- $r_5 = 8 = 18 - 1 \times 10$, $q_5 = 1, m_5 = 7, n_5 = -19$. 그러면 $r_5 = 7 \times 278 - 19 \times 102$이다.
- $r_6 = 2 = 10 - 1 \times 8$, $q_6 = 1, m_6 = -11, n_6 = 30$. 그러면 $r_6 = -11 \times 278 + 30 \times 102 = 2 = \gcd(278, 102)$이다.
따라서 $(x_0, y_0) = (-11, 30)$은 정수해이다. (검산: $278 \times (-11) + 102 \times 30 = -3058 + 3060 = 2$.)
Find a particular solution of $ax + by = c$.
- $172x + 20y = 1000$.
- $278x + 102y = 2$.
$172x + 20y = 1000$. First find an integral solution of $172x + 20y = \gcd(172, 20)$ by the algorithm (algo01-3).
- $r_0 = 20$, $m_1 = 1$.
- $r_1 = 12 = 172 - 8 \times 20$, $q_1 = 8$.
- $r_2 = 8 = 20 - 1 \times 12$, $q_2 = 1, m_2 = -1, n_2 = 9$. Then $r_2 = -172 + 9 \times 20$.
- $r_3 = 4 = 12 - 1 \times 8$, $q_3 = 1, m_3 = 2, n_3 = -17$. Then $r_3 = 2 \times 172 - 17 \times 20 = 4 = \gcd(172, 20)$.
Therefore $2 \times 172 - 17 \times 20 = 4$. Since $1000 = 4 \times 250$, multiplying both sides by $250$ gives $172 \times 500 - 20 \times 4250 = 1000$. Hence $(x_0, y_0) = (500, -4250)$ is an integral solution. (Check: $172 \times 500 - 20 \times 4250 = 86000 - 85000 = 1000$.)
$278x + 102y = 2$. Apply the same algorithm with $a = 278$, $b = 102$.
- $r_0 = 102$, $m_1 = 1$.
- $r_1 = 74 = 278 - 2 \times 102$, $q_1 = 2$.
- $r_2 = 28 = 102 - 1 \times 74$, $q_2 = 1, m_2 = -1, n_2 = 3$. Then $r_2 = -278 + 3 \times 102$.
- $r_3 = 18 = 74 - 2 \times 28$, $q_3 = 2, m_3 = 3, n_3 = -8$. Then $r_3 = 3 \times 278 - 8 \times 102$.
- $r_4 = 10 = 28 - 1 \times 18$, $q_4 = 1, m_4 = -4, n_4 = 11$. Then $r_4 = -4 \times 278 + 11 \times 102$.
- $r_5 = 8 = 18 - 1 \times 10$, $q_5 = 1, m_5 = 7, n_5 = -19$. Then $r_5 = 7 \times 278 - 19 \times 102$.
- $r_6 = 2 = 10 - 1 \times 8$, $q_6 = 1, m_6 = -11, n_6 = 30$. Then $r_6 = -11 \times 278 + 30 \times 102 = 2 = \gcd(278, 102)$.
Hence $(x_0, y_0) = (-11, 30)$ is an integral solution. (Check: $278 \times (-11) + 102 \times 30 = -3058 + 3060 = 2$.)
모든 정수해를 구하라.
1. $172x + 20y = 1000$.
2. $278x + 102y = 2$.
1) 연습문제 1.12에 의해, $1000 = 172 \times 500 - 20 \times 4250$이고 $\gcd(172, 20) = 4$임을 안다. 그러므로 $172x + 20y = 1000$의 모든 정수해는 어떤 $n \in \mathbb{Z}$에 대하여 $(x, y) = (500 + 5n, -4250 - 43n)$로 나타난다.
역주. 원문은 “$4 = 172 \times 500 - 20 \times 4250$”으로 인쇄되어 있으나 이는 오타이며, $\gcd(172, 20) = 4$이고 $172\cdot500 - 20\cdot4250 = 1000$이다.
2) 연습문제 1.12에 의해, $2 = 278 \times (-11) + 102 \times 30$이고 $\gcd(278, 102) = 2$임을 안다. 정리 1.9와 정리 1.10에 의해, $278x + 102y = 2$의 모든 정수해는 어떤 $n \in \mathbb{Z}$에 대하여
로 나타난다.
Find all integral solutions.
1. $172x + 20y = 1000$.
2. $278x + 102y = 2$.
1) By Exercise 1.12., we know that $4 = 172 \times 500 - 20 \times 4250$ and $\gcd(172, 20) = 4$. So every integral solution of $172x + 20y = 1000$ is represented by $(x, y) = (500 + 5n, -4250 - 43n)$ for some $n \in \mathbb{Z}$.
2) By Exercise 1.12., we know that $2 = 278 \times (-11) + 102 \times 30$ and $\gcd(278, 102) = 2$. By Theorem 1.9 and Theorem 1.10, every integral solution of $278x + 102y = 2$ is represented by
for some $n \in \mathbb{Z}$.