예로 ax+by=t (t는 정수) 의 일반해를 구하라는 문제를 푼다고 할때, 아래의 (1)(2)과정을 문제풀이시에 생략하고 바로 ax+by=gcd(a,b)로 놓아도 되는 건지, 아니면 위의 과정을 모두 언급을 해주어야하는 건지, 아니면 짧게 언급할 수 있는 건지 궁금합니다. 만약 짧게 언급한다면 뭐라고 말할 수 있는 건가요?!
(1) 정수 a,b가 gcd(a,b)에 의해 나누어지므로, ax+by로 표현되는 수 역시 gcd(a,b)로 나누어진다.
(2) 따라서 ax+by로 표현되는 가장 작은 양의 정수는 gcd(a,b)이다.
저게 그냥 Bezout identity라고 아주 잘 알려진거라서 그냥 써도 될것 같긴한데 애매하네;
그리고 저 논리가 살짝 부족한게 저렇게 나타낼수 있다는놈의 하한이 gcd(a,b)인건 보였지만 그런 x,y가 존재하는지는 보장을 안해줌 ㅇㅇ
댓글 감사합니다! 혹시나 시험때 감점될까봐 고민하고있었는데 그러면 저 논리가 살짝 부족하면 어떻게 보충해야 할까요?!
답글에 쓰긴 좀 긴것 같고 영어위키에 Bezout identity 치면 증명이 나와있음 ㅇㅇ 간략하게나마 설명하면 ax+by꼴로 나타나는 양의 정수들의 집합에서 minimum이 저게 된다는걸 보였던것 같은데 ㅎㅁ