일차부정방정식 ax + by = c의 계수를 입력해 주세요. 아래 수식은 입력란과 연동되어 있어서 숫자 부분을 직접 고쳐도 계산할 수 있습니다. ‘구할 해의 범위’를 바꾸면 양의 정수해만 골라낼 수도 있습니다.
값은 정수를 숫자로 입력해 주세요(소수·분수는 쓸 수 없습니다). 음수도 쓸 수 있습니다. x나 y의 항이 없을 때는 그 계수에 0을 입력해 주세요.
계산 결과·그래프
왼쪽 입력란에 계수 a, b, c를 넣고 ‘계산’을 누르면 여기에 정수해와 그래프가 표시됩니다.
이 페이지에서 할 수 있는 것
- 정수 계수 \(a,\ b,\ c\)를 넣기만 하면 \(ax + by = c\)를 만족하는 정수의 쌍 \(x,\ y\)(정수해)를 구할 수 있습니다
- \(c\)가 \(a\)와 \(b\)의 최대공약수의 배수가 아니면 정수해가 없습니다. 그 판정과 왜 없는지에 대한 이유도 보여 줍니다
- 유클리드 호제법의 나눗셈 표와, 나머지를 거꾸로 따라가 특수해를 만드는 표를 한 줄씩 그대로 볼 수 있습니다
- 답은 1쌍만이 아니라 \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\)(\(t\)는 정수)의 일반해와, \(t\)를 바꿔 가며 구한 정수해의 목록으로 보여 줍니다
- ‘양의 정수해만’, ‘0 이상의 정수해만’으로 좁힐 수 있습니다. 50 g짜리 추와 80 g짜리 추로 딱 1,000 g을 맞추는 조합을 구하는 문제를 그대로 풀 수 있습니다
계수에는 정수만 넣을 수 있습니다(소수·분수는 쓸 수 없습니다). 계수 하나는 15자리 이내이며, \(a\)와 \(b\)를 동시에 0으로 할 수는 없습니다.
이 계산은 어디에 쓰일까요?
딱 맞는 무게·딱 맞는 개수가 되는 조합 찾기
50 g짜리와 80 g짜리 추만으로 딱 1,000 g을 맞추기, 두 종류의 쿠폰만으로 정해진 금액을 딱 맞추기, 정해진 길이의 자재만으로 딱 맞는 길이 만들기. 이런 ‘정해진 크기의 것을 조합해 목표에 딱 맞추는’ 문제는 그대로 \(ax + by = c\)의 정수해를 구하는 문제가 됩니다.
개수는 음수가 될 수 없으므로, 실제로는 양의 정수해를 골라내는 데까지 해야 비로소 답이 됩니다.
묶음 포장으로 ‘만들 수 있는 개수·만들 수 없는 개수’ 가려내기
6개들이와 10개들이 상자만 있을 때 주문받은 개수를 딱 맞출 수 있는지는 \(6x + 10y = c\)에 0 이상의 정수해가 있는지로 정해집니다. 6과 10의 최대공약수는 2이므로, 홀수 개의 주문은 어떻게 조합해도 만들 수 없습니다.
식품이나 부품의 상자 포장에서는 이 ‘만들 수 있는 개수’를 가려내는 것이 주문을 받을 수 있는지, 어떤 크기의 상자를 갖춰야 하는지의 판단으로 바로 이어집니다.
눈금 없는 그릇으로 원하는 양 재기
5 L와 3 L 그릇만으로 4 L를 재는 유명한 문제는 \(5x + 3y = 4\)의 정수해에 대응합니다(\(x\), \(y\)는 각 그릇으로 붓은 횟수와 덜어 낸 횟수를 부호를 붙여 나타낸 것입니다). \(\gcd(5,\ 3) = 1\)이므로 이 두 그릇이 있으면 1 L 단위로 어떤 양이든 잴 수 있다는 것을 식으로 먼저 판정할 수 있습니다.
실험이나 요리에서 ‘가진 도구만으로 필요한 양을 만들 수 있을까’를 생각할 때 그대로 쓰이는 수학입니다.
인터넷 통신 암호(RSA)의 키 만들기
인터넷 뱅킹과 온라인 쇼핑을 떠받치는 RSA 암호에서는 공개 키의 값 \(e\)로 비밀 키의 값 \(d\)를 만들 때 \(e d + \varphi k = 1\)이라는 일차부정방정식을 풉니다(\(\varphi\)는 키마다 정해지는 정수). 여기에 쓰이는 것이 이 페이지와 같은 확장 유클리드 호제법입니다.
몇백 자리나 되는 수라도 이 방법이라면 순식간에 풀 수 있다는 것이 암호를 실용적으로 만드는 토대 가운데 하나입니다.
재료를 낭비 없이 다 쓰는 생산 계획
1개에 재료를 \(a\) g 쓰는 제품 A와 \(b\) g 쓰는 제품 B를 만들어, 준비한 재료 \(c\) g을 딱 다 쓰고 싶다고 합시다. 이 계획은 \(ax + by = c\)의 0 이상의 정수해를 구하는 문제입니다. 제품을 0.5개만 만들 수는 없으므로 답은 정수여야 합니다.
이처럼 ‘답이 정수로 한정되는 계획 문제’를 다루는 분야를 정수 계획법이라고 하며, 생산 계획, 근무표 작성, 배송 계획 등에 쓰입니다.
공식과 그래프
정수해가 있기 위한 조건
그래프
수학 표기
(일반적인 수식)
\(c\)
\(=\)
\(\gcd(a,\ b)\)
\(\times\)
\(m\)
말로 쓴 표기
(기호를 말로 바꾼 식)
③
우변의 상수 \(c\)
\(=\)
①
\(a\)와 \(b\)의 최대공약수 \(g\)
\(\times\)
②
어떤 정수 \(m\)
공식을 말로 읽으면
①
\(a\)와 \(b\)의 최대공약수(\(g\))
를
②
어떤 정수(\(m\))
배 한 것이
③
우변의 상수(\(c\))
와 딱 같아질 때(즉 \(c\)가 \(g\)의 배수일 때), 그리고 그때에만 정수해가 있습니다
간단한 예
\(2x + 4y = 6\)에는 정수해가 있지만, \(2x + 4y = 5\)에는 1쌍도 없습니다(둘 다 \(\gcd(2,\ 4) = 2\))
우변의 상수(6)
\(=\)
최대공약수(2)
\(\times\)
정수(3)
\(\gcd(2,\ 4) = 2\)
\(6 = 2 \times 3 \quad \Rightarrow \quad 2 \times 1 + 4 \times 1 = 6\)
\(5 = 2 \times 2 + 1 \quad \Rightarrow \quad 2x + 4y \neq 5\)
이해의 핵심
왜 \(g\)의 배수가 아니면 안 될까요? \(a\)도 \(b\)도 \(g\)의 배수이므로 \(a = g a'\), \(b = g b'\)로 쓸 수 있습니다. 그러면 좌변은
\(ax + by = g(a'x + b'y)\)
가 되어, \(x\)와 \(y\)가 정수인 한 좌변은 반드시 \(g\)의 배수가 됩니다. 그래서 우변의 \(c\)가 \(g\)의 배수가 아니면 어떤 정수를 넣어도 등식은 성립하지 않습니다.
반대로 \(c\)가 \(g\)의 배수이기만 하면 해는 반드시 있습니다(이것을 보장하는 것이 다음의 베주 항등식입니다). 그래프로 말하면, 직선 \(ax + by = c\)가 격자점(\(x\)좌표도 \(y\)좌표도 정수인 점)을 지나는지, 격자점 사이를 빠져나가는지의 차이입니다.
베주 항등식(호제법으로 찾는 정수 1쌍)
수학 표기
(일반적인 수식)
\(a x_1\)
\(+\)
\(b y_1\)
\(=\)
\(\gcd(a,\ b)\)
말로 쓴 표기
(기호를 말로 바꾼 식)
①
\(x\)의 계수 \(a\)와, 호제법으로 찾는 정수 \(x_1\)을 곱한 항
\(+\)
②
\(y\)의 계수 \(b\)와, 호제법으로 찾는 정수 \(y_1\)을 곱한 항
\(=\)
③
\(a\)와 \(b\)의 최대공약수 \(g\)
공식을 말로 읽으면
①
\(x\)의 계수 \(a\)와, 호제법으로 찾는 정수 \(x_1\)을 곱한 항
에
②
\(y\)의 계수 \(b\)와, 호제법으로 찾는 정수 \(y_1\)을 곱한 항
을 더하면
③
\(a\)와 \(b\)의 최대공약수(\(g\))
를 만들 수 있습니다. 그렇게 되는 정수의 쌍 \(x_1,\ y_1\)은 반드시 있으며, 유클리드 호제법을 거꾸로 따라가면 찾을 수 있습니다
간단한 예
\(7\)과 \(5\)로 호제법을 계산하고 나머지를 거꾸로 따라가면(\(\gcd(7,\ 5) = 1\))
\(7\)과 정수 \(-2\)를 곱한 항
\(+\)
\(5\)와 정수 \(3\)을 곱한 항
\(=\)
최대공약수(1)
\(7 = 5 \times 1 + 2, \quad 5 = 2 \times 2 + 1\)
\(1 = 5 - 2 \times 2 = 5 - (7 - 5) \times 2 = 3 \times 5 - 2 \times 7\)
\(7 \times (-2) + 5 \times 3 = -14 + 15 = 1\)
이해의 핵심
호제법의 나머지는 언제나 ‘처음 두 수의 정수배의 합’으로 쓸 수 있습니다. 실제로 \(2 = 7 - 5\)이고, 그다음 \(1 = 5 - 2 \times 2\)의 \(2\)에 이것을 대입하면 \(1\)이 \(7\)과 \(5\)의 정수배의 합이 됩니다. 이 작업을 어떤 두 수에서든 기계적으로 할 수 있는 것이 확장 유클리드 호제법입니다.
찾은 \(x_1,\ y_1\)은 최대공약수 \(g\)를 만드는 쌍이므로 그대로는 \(c\)에 대한 해가 아닙니다. 양변을 \(\dfrac{c}{g}\)배 하면 원하는 방정식의 해가 1쌍 생깁니다.
\(x_0 = \dfrac{c}{g} x_1, \quad y_0 = \dfrac{c}{g} y_1\)
예를 들어 \(7x + 5y = 3\)이라면 위의 식을 3배 해서 \(7 \times (-6) + 5 \times 9 = 3\), 즉 \((x_0,\ y_0) = (-6,\ 9)\)가 1쌍의 해가 됩니다. 이 계산기는 이렇게 얻은 해를 보기 쉬운 크기가 될 때까지 옮긴 다음에 보여 줍니다(어느 1쌍을 고르든 다음의 일반해는 같은 모임이 됩니다).
모든 정수해(일반해)
그래프
수학 표기
(일반적인 수식)
\(x\)
\(=\)
\(x_0\)
\(+\)
\(\dfrac{b}{g}\)
\(t\)
\(y\)
\(=\)
\(y_0\)
\(-\)
\(\dfrac{a}{g}\)
\(t\)
말로 쓴 표기
(기호를 말로 바꾼 식)
정수해의 \(x\)
\(=\)
①
특수해의 \(x_0\)
\(+\)
②
\(x\)가 바뀌는 간격 \(\dfrac{b}{g}\)
③
정수 \(t\)
정수해의 \(y\)
\(=\)
④
특수해의 \(y_0\)
\(-\)
⑤
\(y\)가 바뀌는 간격 \(\dfrac{a}{g}\)
정수 \(t\)
공식을 말로 읽으면
①
특수해의 \(x_0\)
에
②
\(x\)가 바뀌는 간격(\(\dfrac{b}{g}\))
을
③
정수(\(t\))
배 해서 더하면 정수해의 \(x\)가 되고, 동시에
④
특수해의 \(y_0\)
에서
⑤
\(y\)가 바뀌는 간격(\(\dfrac{a}{g}\))
을 같은 \(t\)배 해서 빼면 정수해의 \(y\)가 됩니다. \(t\)에 정수를 넣을 때마다 다른 해가 1쌍 생기며, 이것으로 모든 정수해를 나타낼 수 있습니다
간단한 예
\(3x + 4y = 10\)은 \((x_0,\ y_0) = (2,\ 1)\)이 1쌍의 해이고, \(\gcd(3,\ 4) = 1\)이므로
정수해의 \(x\)
\(=\)
특수해(2)
\(+\)
간격(4)
정수 \(t\)
정수해의 \(y\)
\(=\)
특수해(1)
\(-\)
간격(3)
정수 \(t\)
\(3 \times 2 + 4 \times 1 = 10\)
\(x = 2 + 4t, \quad y = 1 - 3t\)
\(t = 1 \ \Rightarrow \ (x,\ y) = (6,\ -2), \quad 3 \times 6 + 4 \times (-2) = 10\)
\(t = -1 \ \Rightarrow \ (x,\ y) = (-2,\ 4), \quad 3 \times (-2) + 4 \times 4 = 10\)
이해의 핵심
왜 \(x\)는 \(\dfrac{b}{g}\)씩, \(y\)는 \(\dfrac{a}{g}\)씩만 바뀔까요? \((x,\ y)\)와 \((x_0,\ y_0)\)이 둘 다 해라면 두 식을 빼서
\(a(x - x_0) = -b(y - y_0)\)
이 성립합니다. 양변을 \(g\)로 나누면 \(\dfrac{a}{g}(x - x_0) = -\dfrac{b}{g}(y - y_0)\)이 되고, \(\dfrac{a}{g}\)와 \(\dfrac{b}{g}\)는 서로소(공약수가 1뿐)입니다.
그러면 좌변은 \(\dfrac{b}{g}\)의 배수여야 하고, \(\dfrac{a}{g}\) 쪽에 그 인수가 없는 이상 \(x - x_0\)이 \(\dfrac{b}{g}\)의 배수라고 정해집니다. 즉 \(x - x_0 = \dfrac{b}{g}t\)로 쓸 수 있고, 여기에서 \(y\)의 식도 정해집니다.
그래프로 보면 직선 \(ax + by = c\) 위에 격자점이 같은 간격으로 가지런히 늘어서 있고, 그 간격이 가로로 \(\dfrac{b}{g}\), 세로로 \(\dfrac{a}{g}\)입니다.
양의 정수해 골라내기
그래프
수학 표기
(일반적인 수식)
\(x_0\)
\(+\)
\(\dfrac{b}{g}\)
\(t\)
\(\ge 1\)
\(y_0\)
\(-\)
\(\dfrac{a}{g}\)
\(t\)
\(\ge 1\)
말로 쓴 표기
(기호를 말로 바꾼 식)
①
특수해의 \(x_0\)
\(+\)
②
\(x\)가 바뀌는 간격 \(\dfrac{b}{g}\)
③
정수 \(t\)
\(\ge 1\)
④
특수해의 \(y_0\)
\(-\)
⑤
\(y\)가 바뀌는 간격 \(\dfrac{a}{g}\)
정수 \(t\)
\(\ge 1\)
공식을 말로 읽으면
①
특수해의 \(x_0\)
에
②
\(x\)가 바뀌는 간격(\(\dfrac{b}{g}\))
을
③
정수(\(t\))
배 해서 더한 값(= 정수해의 \(x\))이 1 이상이고, 또한
④
특수해의 \(y_0\)
에서
⑤
\(y\)가 바뀌는 간격(\(\dfrac{a}{g}\))
을 같은 \(t\)배 해서 뺀 값(= 정수해의 \(y\))도 1 이상이 됩니다. 이 두 가지를 동시에 만족하는 \(t\)의 범위를 구하면 양의 정수해를 모두 알 수 있습니다
간단한 예
3개들이와 5개들이 팩만으로 딱 47개를 맞추면(\(3x + 5y = 47\), \((x_0,\ y_0) = (4,\ 7)\))
특수해(4)
\(+\)
간격(5)
정수 \(t\)
\(\ge 1\)
특수해(7)
\(-\)
간격(3)
정수 \(t\)
\(\ge 1\)
\(3 \times 4 + 5 \times 7 = 47\)
\(4 + 5t \ge 1 \ \Leftrightarrow \ t \ge -\dfrac{3}{5} \ \Leftrightarrow \ t \ge 0\)
\(7 - 3t \ge 1 \ \Leftrightarrow \ t \le 2\)
\(0 \le t \le 2 \ \Rightarrow \ (x,\ y) = (4,\ 7),\ (9,\ 4),\ (14,\ 1)\)
이해의 핵심
개수나 사람 수를 구하는 문제에서는 답이 양의 정수(또는 0 이상의 정수)로 한정됩니다. 일반해를 부등식에 넣어 \(t\)의 범위를 구하면 조건에 맞는 해만 골라낼 수 있습니다. \(t\)는 정수이므로 \(t \ge -\dfrac{3}{5}\)처럼 경계가 분수가 되어도 그 안쪽의 정수(이 예에서는 \(t \ge 0\))까지 좁힐 수 있다는 것이 핵심입니다.
\(a\)와 \(b\)의 부호가 같으면(둘 다 양수 등) 한쪽 부등식이 하한, 다른 쪽이 상한이 되므로 조건을 만족하는 해는 반드시 유한개입니다. 부호가 다르면(예: \(3x - 5y = 1\)) 두 제한이 같은 방향이 되어 양의 정수해가 무수히 많습니다. 계수 한쪽이 0일 때(예: \(0x + 5y = 10\))는 0이 아닌 쪽 문자의 값이 하나로 정해지고 다른 쪽은 자유롭게 움직일 수 있습니다. 정해진 쪽이 조건을 만족하면 해는 무수히 많고, 만족하지 않으면 1쌍도 없습니다.
반대로 조건을 만족하는 \(t\)가 하나도 없을 수도 있습니다. 그때는 ‘맞출 수 있는 조합은 없다’가 답입니다.
일차부정방정식 \(ax + by = c\)에 정수해가 있는 것은 \(c\)가 \(a\)와 \(b\)의 최대공약수 \(g\)의 배수일 때뿐입니다. 해가 있을 때는 유클리드 호제법을 거꾸로 따라가 특수해 \((x_0,\ y_0)\)을 1쌍 만들면, 나머지는 모두 \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\)(\(t\)는 정수)로 나타낼 수 있습니다.
용어·기호 해설
기호
| \(a,\ b\) | 에이, 비 | \(x\)와 \(y\)에 곱해진 계수입니다. 정해진 수를 나타낼 때는 알파벳 앞쪽의 문자 \(a,\ b,\ c\)를 쓰는 관례가 있습니다. 이 페이지에서는 둘 다 정수입니다. |
| \(c\) | 시 | 방정식 우변의 상수입니다. constant(상수)의 머리글자입니다. ‘만들고 싶은 합계’에 해당하는 수로, 이것이 최대공약수의 배수인지에 따라 해가 있는지가 정해집니다. |
| \(x,\ y\) | 엑스, 와이 | 구하려는 미지수입니다. 모르는 수를 알파벳 뒤쪽의 문자로 나타내는 방법은 데카르트가 널리 퍼뜨렸다고 합니다. 이 페이지에서는 정수 값만 답으로 다룹니다. |
| \(\gcd(a,\ b)\) | 지시디 에이 비 | \(a\)와 \(b\)의 최대공약수입니다. greatest common divisor(가장 큰 공약수)의 머리글자입니다. 정수론 책에서는 \((a,\ b)\)로 줄여 쓰기도 합니다. |
| \(g\) | 지 | 최대공약수 \(\gcd(a,\ b)\)를 짧게 쓴 기호입니다. greatest(가장 큰)의 머리글자입니다. 일반해의 \(\dfrac{b}{g}\), \(\dfrac{a}{g}\)처럼 식이 길어지지 않게 하려고 씁니다. |
| \(x_0,\ y_0\) | 엑스 영, 와이 영 | 특수해, 즉 처음 찾은 1쌍의 정수해입니다. ‘기준이 되는 0번째 해’라는 뜻으로 오른쪽 아래에 0을 붙입니다. 여기를 출발점으로 모든 정수해를 나타냅니다. |
| \(x_1,\ y_1\) | 엑스 일, 와이 일 | 호제법을 거꾸로 따라가면 찾을 수 있는 정수의 쌍으로, \(a x_1 + b y_1 = g\)를 만족합니다. 이것을 \(\dfrac{c}{g}\)배 하면 특수해 \((x_0,\ y_0)\)이 됩니다. |
| \(t\) | 티 | 정수라면 무엇이든 되는 변수(매개변수)입니다. 모든 정수해를 하나의 식으로 묶어 나타내려고 씁니다. \(t\)에 정수를 넣을 때마다 다른 정수해가 1쌍 나타납니다. |
| \(m\) | 엠 | ‘\(c\)가 \(g\)의 몇 배인지’를 나타내는 정수입니다. 정수를 나타내는 문자로는 \(m\), \(n\), \(k\)를 자주 쓰며, \(m\)은 multiple(배수)의 머리글자에서 왔다고 합니다. \(c = g \times m\)으로 쓸 수 있을 때, 그리고 그때에만 정수해가 있습니다. |
| \(q\) | 큐 | 나눗셈의 몫입니다. quotient(몫)의 머리글자입니다. 호제법의 표에서는 \(13 = 5 \times 2 + 3\)의 \(2\)에 해당합니다. |
| \(r\) | 알 | 나눗셈의 나머지입니다. remainder(나머지)의 머리글자입니다. 호제법의 표에서는 \(13 = 5 \times 2 + 3\)의 \(3\)에 해당합니다. 이 나머지가 0이 되었을 때 계산이 끝납니다. |
| \(\ge\) | 크거나 같다(이상) | ‘좌변이 우변 이상’임을 나타내는 부등호입니다. \(x \ge 1\)은 ‘\(x\)는 1 이상’이라는 뜻입니다. 짝이 되는 \(\le\)는 ‘작거나 같다(이하)’를 나타냅니다. |
용어
| 일차부정방정식 | \(ax + by = c\)처럼 미지수가 2개인데 식이 하나뿐인 일차방정식입니다. ‘부정’은 해가 하나로 정해지지 않는다는 뜻으로, 실수 범위라면 직선 위의 모든 점이 해가 됩니다. 정수해로 한정해도 보통은 무수히 많습니다. |
| 디오판토스 방정식 | 정수해만을 답으로 하는 방정식을 통틀어 부르는 이름입니다. 고대 그리스의 수학자 디오판토스의 이름에서 왔습니다. 이 페이지에서 다루는 일차부정방정식은 그중에서 가장 기본적인 것입니다. |
| 정수해 | 방정식을 만족하는 해 중에서 \(x\)도 \(y\)도 정수인 것입니다. 개수나 사람 수처럼 ‘딱 떨어지지 않을 수 없는 양’을 구하는 문제에서는 정수해만 의미가 있습니다. |
| 특수해 | 무수히 많은 정수해 중에서 처음 찾은 1쌍입니다. 어느 1쌍을 골라도 상관없습니다. 여기를 출발점으로 일반해의 꼴로 모든 해를 나타냅니다. |
| 일반해 | 모든 정수해를 정수 \(t\)를 써서 하나의 식으로 묶어 나타낸 것입니다. \(t\)에 정수를 넣으면 그때마다 다른 해를 1쌍 꺼낼 수 있습니다. |
| 최대공약수 | 2개 이상의 정수를 모두 나누어떨어지게 하는 자연수 중 가장 큰 수입니다. 일차부정방정식에서는 이 값이 ‘해가 있는지’와 ‘해와 해 사이의 간격’을 모두 정합니다. |
| 유클리드 호제법 | 큰 수를 작은 수로 나누고, 나누는 수와 나머지의 쌍으로 바꾸는 조작을 되풀이해 최대공약수를 구하는 방법입니다. 나머지가 0이 되었을 때의 나누는 수가 최대공약수입니다. 기원전 3세기쯤의 책 《원론》에 실려 있어 세계에서 가장 오래된 알고리즘이라고도 불립니다. |
| 확장 유클리드 호제법 | 호제법의 나눗셈 식을 아래부터 차례로 다시 대입해 최대공약수를 \(a x_1 + b y_1\)의 꼴로 나타내는 방법입니다. 일차부정방정식의 특수해를 만들 때 씁니다. |
| 베주 항등식 | \(a x_1 + b y_1 = \gcd(a,\ b)\)를 만족하는 정수 \(x_1,\ y_1\)이 반드시 있다는 정리입니다. 프랑스의 수학자 베주의 이름이 붙어 있습니다. 일차부정방정식을 풀 수 있다는 근거입니다. |
| 서로소 | 두 정수의 최대공약수가 1인 것입니다. 예를 들어 3과 4는 서로소입니다. \(\dfrac{a}{g}\)와 \(\dfrac{b}{g}\)는 반드시 서로소가 되며, 이것이 ‘해가 같은 간격으로 늘어선다’는 것의 결정적인 이유입니다. |
| 배수 | 어떤 정수를 정수배 해서 만들 수 있는 수입니다. \(10\)의 배수는 \(\dots,\ -20,\ -10,\ 0,\ 10,\ 20,\ \dots\)입니다. 0이나 음수도 배수에 넣습니다. |
| 나머지 | 정수의 나눗셈에서 나누어떨어지지 않고 남는 수입니다. \(13 \div 5\)는 몫이 \(2\), 나머지가 \(3\)입니다. 호제법은 이 나머지만을 써서 진행합니다. |
| 몫 | 정수의 나눗셈에서 ‘나누는 수가 몇 번 들어가는지’를 나타내는 정수입니다. \(13 = 5 \times 2 + 3\)의 \(2\)가 몫입니다. |
| 격자점 | 좌표평면 위에서 \(x\)좌표도 \(y\)좌표도 정수인 점입니다. 모눈종이의 칸이 만나는 점에 해당합니다. 일차부정방정식의 정수해는 직선 \(ax + by = c\) 위에 있는 격자점 그 자체입니다. |
| 매개변수 | 해의 모임 전체를 하나의 식으로 나타내려고 두는, 자유롭게 바꿀 수 있는 변수입니다. 이 페이지의 \(t\)가 그것입니다. 파라미터라고도 합니다. |
| 계수 | 문자 앞에 붙어 있는 수입니다. \(3x\)의 \(3\)이 계수입니다. 수가 쓰여 있지 않은 \(x\)의 계수는 1로 생각합니다. |
| 부등식 | \(t \ge 0\)처럼 두 값의 크기 관계를 나타내는 식입니다. 양의 정수해를 골라낼 때 씁니다. |
먼저 알아 두면 좋은 내용
이 페이지의 계산을 ‘뜻을 이해하고’ 쓸 수 있도록 먼저 알아 두면 좋은 내용을 정리했습니다.
막히면 이 표의 내용으로 돌아가 복습하는 것이 지름길입니다.
| 정수의 나눗셈과 나머지(초등학교 3학년~중학교 1학년, 8~13세) |
|
| 약수·배수·최대공약수(초등학교 5학년~중학교 1학년, 10~13세) |
|
| 문자와 식, 일차방정식(중학교 1학년, 12~13세) |
|
| 미지수가 2개인 일차방정식과 그 그래프(중학교 2학년, 13~14세) |
|
| 부등식(중학교 2학년~고등학교, 13~16세) |
|
| 분수의 계산(초등학교 5학년~중학교 1학년, 10~13세) |
|
Excel로 계산하는 방법
아래 표를 통째로 복사해 Excel의 A1 셀에 붙여 넣으면 그대로 사용할 수 있습니다.
‘정수해가 있는지’ 확인하는 표
| x의 계수 a | 50 |
| y의 계수 b | 80 |
| 우변의 상수 c | 1000 |
| 최대공약수 g | =GCD(B1,B2) |
| c를 g로 나눈 나머지 | =MOD(B3,B4) |
| 정수해가 있는가 | =IF(B5=0,"정수해가 있음","정수해가 없음") |
‘베주 항등식’을 확인하는 표
| x의 계수 a | 50 |
| y의 계수 b | 80 |
| 호제법으로 찾은 x1 | -3 |
| 호제법으로 찾은 y1 | 2 |
| a×x1 + b×y1 | =B1*B3+B2*B4 |
| 최대공약수 g | =GCD(B1,B2) |
‘모든 정수해(일반해)’에서 해를 만드는 표
| x의 계수 a | 50 |
| y의 계수 b | 80 |
| 우변의 상수 c | 1000 |
| 최대공약수 g | =GCD(B1,B2) |
| 특수해 x0 | 4 |
| 특수해 y0 | 10 |
| 정수 t | 1 |
| x = x0 + (b/g)×t | =B5+(B2/B4)*B7 |
| y = y0 − (a/g)×t | =B6-(B1/B4)*B7 |
| 검산 a×x + b×y | =B1*B8+B2*B9 |
‘양의 정수해 골라내기’를 하는 표
| x의 계수 a | 50 |
| y의 계수 b | 80 |
| 최대공약수 g | =GCD(B1,B2) |
| 특수해 x0 | 4 |
| 특수해 y0 | 10 |
| t의 하한(x ≥ 1에서) | =-INT((B4-1)/(B2/B3)) |
| t의 상한(y ≥ 1에서) | =INT((B5-1)/(B1/B3)) |
| 양의 정수해의 개수 | =MAX(0,B7-B6+1) |
붙여 넣으면 위쪽 행(계수나 특수해)이 입력 칸이 되고, 아래쪽 행이 자동 계산 결과가 됩니다. GCD는 최대공약수, MOD는 나눈 나머지, INT는 소수점 아래를 버리는 함수입니다.
첫 번째 표는 50x + 80y = 1000의 예로, 최대공약수는 10, 1000을 10으로 나눈 나머지는 0이므로 ‘정수해가 있음’이 표시됩니다. 여기를 1001로 바꾸면 ‘정수해가 없음’으로 바뀝니다.
두 번째 표는 호제법을 거꾸로 따라가 얻은 x1 = −3, y1 = 2가 정말로 베주 항등식을 만족하는지 확인하는 표입니다. 50×(−3) + 80×2 = 10이 되어 최대공약수와 같습니다.
세 번째 표는 일반해에서 해를 1쌍 꺼내는 표입니다. t에 1을 넣으면 x = 12, y = 5가 되고, 검산 행은 1000으로 돌아옵니다. t를 여러 정수로 바꿔 보세요.
네 번째 표는 양의 정수해를 골라내는 표입니다. t의 하한은 0, 상한은 1로 나오므로 양의 정수해는 2쌍(t = 0과 t = 1)임을 알 수 있습니다. 이 두 식은 a와 b가 모두 양수인 경우의 식이므로, 음수 계수를 넣을 때는 부등호의 방향이 바뀌는 점에 주의하세요.
첫 번째 표는 50x + 80y = 1000의 예로, 최대공약수는 10, 1000을 10으로 나눈 나머지는 0이므로 ‘정수해가 있음’이 표시됩니다. 여기를 1001로 바꾸면 ‘정수해가 없음’으로 바뀝니다.
두 번째 표는 호제법을 거꾸로 따라가 얻은 x1 = −3, y1 = 2가 정말로 베주 항등식을 만족하는지 확인하는 표입니다. 50×(−3) + 80×2 = 10이 되어 최대공약수와 같습니다.
세 번째 표는 일반해에서 해를 1쌍 꺼내는 표입니다. t에 1을 넣으면 x = 12, y = 5가 되고, 검산 행은 1000으로 돌아옵니다. t를 여러 정수로 바꿔 보세요.
네 번째 표는 양의 정수해를 골라내는 표입니다. t의 하한은 0, 상한은 1로 나오므로 양의 정수해는 2쌍(t = 0과 t = 1)임을 알 수 있습니다. 이 두 식은 a와 b가 모두 양수인 경우의 식이므로, 음수 계수를 넣을 때는 부등호의 방향이 바뀌는 점에 주의하세요.
Google 스프레드시트로 계산하는 방법
아래 표를 통째로 복사해 Google 스프레드시트의 A1 셀에 붙여 넣으면 그대로 사용할 수 있습니다.
‘정수해가 있는지’ 확인하는 표
| x의 계수 a | 50 |
| y의 계수 b | 80 |
| 우변의 상수 c | 1000 |
| 최대공약수 g | =GCD(B1,B2) |
| c를 g로 나눈 나머지 | =MOD(B3,B4) |
| 정수해가 있는가 | =IF(B5=0,"정수해가 있음","정수해가 없음") |
‘베주 항등식’을 확인하는 표
| x의 계수 a | 50 |
| y의 계수 b | 80 |
| 호제법으로 찾은 x1 | -3 |
| 호제법으로 찾은 y1 | 2 |
| a×x1 + b×y1 | =B1*B3+B2*B4 |
| 최대공약수 g | =GCD(B1,B2) |
‘모든 정수해(일반해)’에서 해를 만드는 표
| x의 계수 a | 50 |
| y의 계수 b | 80 |
| 우변의 상수 c | 1000 |
| 최대공약수 g | =GCD(B1,B2) |
| 특수해 x0 | 4 |
| 특수해 y0 | 10 |
| 정수 t | 1 |
| x = x0 + (b/g)×t | =B5+(B2/B4)*B7 |
| y = y0 − (a/g)×t | =B6-(B1/B4)*B7 |
| 검산 a×x + b×y | =B1*B8+B2*B9 |
‘양의 정수해 골라내기’를 하는 표
| x의 계수 a | 50 |
| y의 계수 b | 80 |
| 최대공약수 g | =GCD(B1,B2) |
| 특수해 x0 | 4 |
| 특수해 y0 | 10 |
| t의 하한(x ≥ 1에서) | =-INT((B4-1)/(B2/B3)) |
| t의 상한(y ≥ 1에서) | =INT((B5-1)/(B1/B3)) |
| 양의 정수해의 개수 | =MAX(0,B7-B6+1) |
Excel과 같은 수식을 그대로 쓸 수 있습니다(GCD, MOD, INT, MAX, IF 모두 이름과 기능이 같습니다). 표를 통째로 복사해 A1 셀에 붙여 넣고, 계수를 원하는 값으로 바꿔 주세요.
Python으로 계산하는 방법
from math import gcd
# ax + by = c의 계수(정수)
a, b, c = 50, 80, 1000
def extended_gcd(x, y):
# 확장 유클리드 호제법: gcd와, x*s + y*t = gcd를 만족하는 s, t를 돌려준다
if y == 0:
return x, 1, 0
g, s, t = extended_gcd(y, x % y)
return g, t, s - (x // y) * t
g = gcd(a, b)
if c % g != 0:
print(f"우변 {c}: {g}의 배수가 아니므로 정수해가 없습니다")
else:
_, s, t = extended_gcd(a, b)
x0, y0 = s * (c // g), t * (c // g) # 특수해(정수해 1쌍)
step_x, step_y = b // g, a // g # x가 바뀌는 간격과 y가 바뀌는 간격
# x가 0 이상에서 가장 작아질 때까지 옮겨서 보기 쉬운 특수해로 고친다
n = x0 // step_x
x0, y0 = x0 - n * step_x, y0 + n * step_y
print(f"특수해: (x, y) = ({x0}, {y0})")
print(f"일반해: x = {x0} + {step_x}t, y = {y0} - {step_y}t (t는 정수)")
for k in range(-2, 3):
print(f" t = {k:2}: (x, y) = ({x0 + step_x * k}, {y0 - step_y * k})")
# 양의 정수해(x >= 1이고 y >= 1)만 꺼낸다
t_low = -((1 - x0) // -step_x)
t_high = (y0 - 1) // step_y
print("양의 정수해:", [(x0 + step_x * k, y0 - step_y * k)
for k in range(t_low, t_high + 1)])
표준 라이브러리의 math.gcd와 재귀로 쓴 확장 유클리드 호제법만으로 풀 수 있습니다. 이 예는 50x + 80y = 1000이며, 실행하면 특수해 (4, 10), 일반해 x = 4 + 8t, y = 10 − 5t, 양의 정수해 [(4, 10), (12, 5)]가 표시됩니다. 계수를 바꿔서 해 보세요(마지막 양의 정수해 부분은 a와 b가 모두 양수인 경우의 식입니다).
LaTeX 등 수식 언어로 쓰는 법(복사 가능)
정수해가 있기 위한 조건
c = gcd(a, b) × m
c = \gcd(a, b) \times m
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>c</mi>
<mo>=</mo>
<mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
<mo>×</mo>
<mi>m</mi>
</mrow>
</math>
c = gcd(a, b) * m
Mod[c, GCD[a, b]] == 0
irem(c, igcd(a, b)) = 0;
mod(c, gcd(a, b)) == 0
c = gcd(a,b) × m
베주 항등식(호제법으로 찾는 정수 1쌍)
a·x₁ + b·y₁ = gcd(a, b)
a x_1 + b y_1 = \gcd(a, b)
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>a</mi><msub><mi>x</mi><mn>1</mn></msub>
<mo>+</mo>
<mi>b</mi><msub><mi>y</mi><mn>1</mn></msub>
<mo>=</mo>
<mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
</mrow>
</math>
a*x_1 + b*y_1 = gcd(a, b)
ExtendedGCD[a, b]
igcdex(a, b, x1, y1);
[g, x1, y1] = gcd(a, b);
a x_1 + b y_1 = gcd(a,b)
모든 정수해(일반해)
x = x₀ + (b/g)t, y = y₀ − (a/g)t
x = x_0 + \frac{b}{g} t, \quad y = y_0 - \frac{a}{g} t
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>x</mi><mo>=</mo><msub><mi>x</mi><mn>0</mn></msub>
<mo>+</mo>
<mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>,</mo><mspace width="1em"/>
<mi>y</mi><mo>=</mo><msub><mi>y</mi><mn>0</mn></msub>
<mo>−</mo>
<mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
</mrow>
</math>
x = x_0 + (b/g)t, y = y_0 - (a/g)t
Solve[a x + b y == c, {x, y}, Integers]
isolve(a*x + b*y = c);
S = solve(a*x + b*y == c, [x y], 'Integer', true);
x = x_0 + (b/g)t, y = y_0 - (a/g)t
양의 정수해 골라내기
x₀ + (b/g)t ≥ 1, y₀ − (a/g)t ≥ 1
x_0 + \frac{b}{g} t \ge 1, \quad y_0 - \frac{a}{g} t \ge 1
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<msub><mi>x</mi><mn>0</mn></msub>
<mo>+</mo>
<mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>≥</mo><mn>1</mn>
<mo>,</mo><mspace width="1em"/>
<msub><mi>y</mi><mn>0</mn></msub>
<mo>−</mo>
<mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>≥</mo><mn>1</mn>
</mrow>
</math>
x_0 + (b/g)t >= 1 and y_0 - (a/g)t >= 1
Solve[a x + b y == c && x >= 1 && y >= 1, {x, y}, Integers]
isolve({a*x + b*y = c, x >= 1, y >= 1});
S = solve([a*x + b*y == c, x >= 1, y >= 1], [x y], 'Integer', true);
x_0 + (b/g)t ≥ 1, y_0 − (a/g)t ≥ 1
ChatGPT 에게 물어서 계산하는 방법
당신은 수학(정수의 성질) 계산 도우미입니다. 다음 계산을 반드시 Python 코드를 실제로 실행해서 하고, 실행 결과의 수치만을 근거로 답해 주세요(암산이나 추측으로 답하지 마세요). 일차부정방정식 50x + 80y = 1000의 정수해를 구해 주세요. 다음 내용을 각각 보여 주세요. 1. 50과 80의 최대공약수와, 1000이 그 배수인지 아닌지 2. 유클리드 호제법의 나눗셈 식(나머지가 0이 될 때까지)과, 그것을 거꾸로 따라가 얻는 50×x1 + 80×y1 = 최대공약수의 x1, y1 3. 특수해 (x0, y0)와 일반해 x = x0 + (b/g)t, y = y0 − (a/g)t 4. x와 y가 모두 1 이상인 정수해 전부 Python에서는 math.gcd와 확장 유클리드 호제법을 써서 정확하게 계산하고, 계산에 쓴 식과 실행 결과의 수치를 보여 주세요.
사용법
-
1숫자 입력계산하고 싶은 숫자를 입력란에 입력합니다
-
2계산‘계산’ 버튼을 누릅니다
-
3결과 확인계산 결과가 바로 표시됩니다. 계산의 원리와 공식 해설도 같은 페이지에서 확인할 수 있습니다
DataChef의 특징
간단하고 무료
무료로 횟수 제한 없이 변환
전문 지식 없이도 직관적이고 간단하게 사용
전문 지식 없이도 직관적이고 간단하게 사용
회원가입 불필요
접속 즉시 바로 사용 가능
개인정보를 등록하지 않고도 이용할 수 있습니다
개인정보를 등록하지 않고도 이용할 수 있습니다
안전하고 안심
통신을 강력하게 암호화
"다운로드"를 누르면 파일이 자동으로 삭제됩니다
"다운로드"를 누르면 파일이 자동으로 삭제됩니다
빠른 속도
기다림 없는 쾌적한 표시 속도와 변환 속도
워터마크 없음
워터마크 없음
출처 표기 불필요
출처 표기 불필요
상업적 이용 가능
무료로 상업적 이용 가능
상업적 이용 허가 연락도 필요 없습니다
상업적 이용 허가 연락도 필요 없습니다
관련 기능
최대공약수 계산기(GCD)
2개 이상의 정수의 최대공약수를 소인수분해와 유클리드 호제법 해설과 함께 계산합니다
최소공배수 계산기(LCM)
2개 이상의 정수의 최소공배수를 계산합니다. 최대공약수와의 관계도 확인할 수 있습니다
소인수분해 계산기
정수를 소수의 곱으로 분해합니다. 서로소인지 확인할 때도 쓸 수 있습니다
연립방정식 계산기(가감법·대입법 풀이 과정)
미지수가 2개인 연립일차방정식을 중학교 교과서와 같은 가감법·대입법 풀이 과정과 함께 풉니다. 두 직선의 그래프와 해가 없음·무수히 많음 판정도
