[중고딩문제] 유클리드 호제법 나머지가 음수일때

[익명(223.38)]

a=bq+r (0<=r<b)일때 a와b의 최대공약수가 b와r의 최대공약수와 같잖아요?

이건 r이 음수일때는 성립 안하나요?

예를들어서 126이랑 35 최대공약수 구할때 

126=35x3+21

35랑21최대공약수는 7이라서 답은 7인데

126=35x4-14라서

35랑 14최대공약수도 7이라서 답은 같게 나오는데 

다른숫자경우에는 반례가 존재할거같아서요

알려주시면 감사하겠습니다

[익명(anxious1657)]

유클리드 호제법은 (a,b)=(a,b+ak)라서 나머지가 음수여도 상관없습니다

[수갤러 1(39.7)]

나머지는 음이 아닌 정수인데 어떻게 음수가 됨 에휴

[익명(49.98)]

어차피 division algorithm은 본질적으로 나머지의 minimality가 중요하니 norm을 쓰든 뭘 하든 하면 음수 나머지도 정의할 수는 있지.