🧲 베주 항등식 계산기 | 확장 유클리드 정수해

정수 a

정수 b

베주 항등식과 확장 유클리드 호제법

두 정수 a와 b가 주어지면 ax+by=gcd(a,b)를 만족하는 정수 x, y가 반드시 존재합니다. 이것이 베주 항등식이고, 이때의 x, y를 베주 계수라고 합니다. 계수를 실제로 찾는 방법이 확장 유클리드 호제법입니다. 보통의 호제법은 나머지가 0이 될 때까지 나눠서 최대공약수만 구하지만, 확장판은 나눗셈을 진행하는 동안 계수를 함께 갱신해 x와 y까지 얻습니다.

이 계산기는 절댓값으로 호제법을 돌린 뒤 입력의 부호를 계수에 되돌려 반영합니다. 그래서 음수를 넣어도 정확한 해가 나옵니다. 계산이 끝나면 구한 x, y를 원래 식에 그대로 대입한 검산식을 보여주므로 결과가 실제로 최대공약수와 같아지는지 눈으로 확인할 수 있습니다.

정수해는 한 쌍이 아니라 무한히 많습니다. 한 쌍을 찾으면 정수 k에 대해 x+k(b/g)와 y−k(a/g)도 모두 해가 되므로 일반해 형태를 함께 표시합니다. 최대공약수가 1이면 서로소 판정 줄이 따로 나타나고, 이때 x는 b를 법으로 하는 a의 모듈러 역원이 됩니다. 아래 표에는 호제법의 각 나눗셈 단계가 순서대로 정리됩니다. 정확한 정수 연산을 보장하기 위해 절댓값 100만까지만 입력을 받고 소수는 지원하지 않습니다.

자주 묻는 질문

베주 항등식이란 무엇인가요?

두 정수 a, b에 대해 ax+by=gcd(a,b)를 만족하는 정수 x, y가 항상 존재한다는 정리입니다. 이 x, y를 베주 계수라고 부릅니다.

정수해는 한 쌍뿐인가요?

무한히 많습니다. 한 쌍을 x, y라 하면 정수 k에 대해 x+k(b/g), y−k(a/g)도 모두 해가 됩니다. 결과에 이 일반해 형태를 함께 표시합니다.

음수나 0을 넣어도 되나요?

됩니다. 절댓값으로 호제법을 돌린 뒤 부호를 계수에 되돌려 반영합니다. 다만 a와 b가 모두 0이면 최대공약수가 정의되지 않으므로 계산할 수 없습니다.

베주 항등식과 확장 유클리드 호제법

자주 묻는 질문

같은 카테고리 도구