질문 최대공약수를 구하는 두가지 방법

[언어수학]

일반적으로 78 과 36 이 있으면

이것을 2 로 나누어 39 와 18 이 되고 다시

이것을 3 으로 나누어 13 과 6 이 되어

더이상 공통의 수로 나눌 수 없게되면

나눈 수 2 와 3 을 곱해 최대공약수가 6 이라고

답하지 않습니까? 아니면 바로 6 으로 나누고 더이상 나눌 수 없어

6 이라고 바로 답하던지요.

그런데 이것 말고도 다른 방법이 있더라구요. 혹시 알고 계신지 모르겠어요?

78 과 36

36 과 6(36으로 78을 나눈 나머지)

6 과 0(6으로 36을 나눈 나머지)

최대 공약수는 6

또 다른 예로

104 와 14

14 와 6(14로 104를 나눈 나머지)

6 과 2(6으로 14를 나눈 나머지)

2 와 0(2로 6을 나눈 나머지)

최대 공약수는 2


어떻게해서 같은 답이 나오는지 잘 모르겠어요. 혹시 아는 분 계시나요?

나중에 알려드린 방법은 최대공약수를 구하는 프로그램에 사용된 방법입니다.

[달령]

방식이 똑같은 거잖아요;;;