일차 부정방정식 정수해 계산기

gcd(a, b)가 c를 나누면 있고, 나누지 못하면 없습니다. a도 b도 최대공약수의 배수이므로 둘을 정수배해 더한 것은 반드시 최대공약수의 배수가 되기 때문입니다. 6x + 4y = 5에 해가 없는 것도 왼쪽이 언제나 짝수인데 5는 홀수여서입니다. 이것을 베주 항등식이라고 합니다.

x = x₀ + (b/g)t, y = y₀ − (a/g)t입니다(g는 최대공약수, t는 임의의 정수). x를 b/g만큼 늘리면 ax가 ab/g만큼 늘고, 같은 때 y를 a/g만큼 줄이면 by가 똑같이 줄어 서로 상쇄되기 때문입니다. 이보다 촘촘한 간격은 있을 수 없습니다 — 더 작게 움직이면 상쇄가 정수로 떨어지지 않습니다.

확장 유클리드 알고리즘으로 찾습니다. 유클리드 호제법으로 최대공약수를 구하면서 나눗셈의 몫을 되짚어 올라가면 a·p + b·q = gcd(a, b)를 만족하는 정수 p, q가 나옵니다. 여기에 c/gcd를 곱한 것이 특수해입니다.

그 조건을 t에 대한 두 부등식으로 옮기면 t의 범위가 잘려 개수가 유한해집니다. 「300원짜리와 500원짜리로 4000원 맞추기」처럼 개수를 세는 문제가 여기에 해당합니다. 3x + 5y = 40의 경우 (0,8) (5,5) (10,2) 세 가지뿐입니다. 정수해가 있어도 0 이상인 것은 하나도 없을 수 있습니다.

있습니다. a와 b의 부호가 엇갈릴 때 그렇습니다. −2x + 3y = 1은 (1,1) (4,3) (7,5)처럼 x가 커지면 y도 같이 커져 어느 쪽도 음수로 떨어지지 않습니다. 계수가 둘 다 양수일 때만 개수가 유한합니다.

미지수가 둘인데 식이 하나뿐이라 해가 하나로 정해지지 않기 때문입니다. 실수 범위에서는 그냥 직선 하나이지만, 정수만 허용하면 그 직선 위의 격자점만 답이 되어 아예 없거나 띄엄띄엄 무한히 많거나 둘 중 하나가 됩니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.