[일반] 다항식 유클리드호제법 왤캐헷갈림?

[익명(14.45)]

두개의 다항식 유클리드호제법으로

최대공약수 얻는건데

나머지 구해서 왜 뜬금없이 계수를 빼서 나누는지 이해불가능 ㄹㅇ

- dc official App

[아까꺼다날아감(gkghwns)]

나도 왜 그러는지는 모르겠는데 그러면 엄청 편함. 정수론에서는 정수계수 방정식의 정수해를 찾는 것이 시작이자 끝이라고 할 수 있음. 엄청 큰 두 개의 정수가 있을 때 a, b가 있다고 하자. 이 때 ax + by = c (a,b,c는 정수인 상수 x,y는 정수) 이 방정식의 해는 뭘까? 아니 해가 존재하기는 할까? 만약 gcd(a,b)=d | c 라면

[아까꺼다날아감(gkghwns)]

정수해가 존재함이 알려짐. 이 때 정수해가 존재한다고 하자. 해가 존재한다면 해로서의 정수쌍이 무한개 존재함. 근데 이건 또 어떻게 구함? 그 방법 중 하나가 유클리드 호제법임. 유클리도 호제법으로 나머지가 0이 될때 까지 한 후 거꾸로 올라가면 한 쌍의 정수해 (x_0,y_0)를 구할 수 있음. 특수해 한 쌍을 알 때 일반해를 구하는 공식도 있음.