유클리드의 호제법을 이용한다. 우선 증명은 생략하자.
이걸 증명하는 건 그다지 효율적이지 않는듯하다. 외우자 무조건
1. 만약 A와 B 두 수가 있다고 가정하자.
2. A와 B 중 작은수로 큰수를 나누어 몫과 나머지를 구한다.
유클리드의 호제법!
A=B*Q+R
A와 B의 최대공약수는 Q와 R 의 최대공약수와 같다.
// 여기서 A 와 B의 최대 공약수를 구하기를 원한다면Q와 R의 최대공약수를 구하자.
위 과정을 계속 반복한다.
<문제>
원을 시작점을 중심으로 반대방향으로 A와 B의 속도로 두물체가 출발하였다.
계속해서 만날것이다. 그런데 만나는 위치가 시작점이 될 때 두 물체는 몇번을 만났는가?
해법
1.두물체의 최대 공약수를 구한다.
2. A와 B의 합을 최대공약수로 나눈 수가 두 물체가 만난 횟수가된다.
위 말은 결론적으로 그렇다는것이다.
의미를 씹어보자면 이렇다.
A와 B로 다른방향으로 가다가 젤 처음만나는 점을 생각해보면 그점까지 서로 이동한거리를 자신의 속도라고 가정하자.
그러면 원의 둘레는 A+B가 된다.
이것을 직선거리로 끝없이 늘어트리면 A와 B중 아무거나 A+B의 배수가되는 점과 만나는 경우가 된다.
서로의 이동거리의 합이 원의둘레의 배수가되는 경우마다 만난다.
결국 A+B(원의둘레)와 A와 B중 하나만 생각하면된다.
A와 B의 최대공약수로 A와 B의 합을 나누게되면(Ga+Gb)G = G(a+b) 가 된다.
우리는 a와 a+b 의 최소공배수 또는 b와 a+b의 최소공배수를 구하면 되는 것이다.
필요 개념
*서로소의 합과 곱은 서로소이다.(==서로소의 합은 원래 두수와도 서로소이다)
a+b 는 a와도 b와도 서로소라는 뜻이다.
관련글