이거 증명하기는 조금 어려운데.. 흐음..

직관적으로 생각해 봅시다.

소시지가 N개, 평론가가 M명이 있습니다. 그러면 일단 이렇게 생각해 봅시다.

(1) 평론가에게 주기 전에, 소시지를 자른다.

즉, 평론가 1에게 주기 전에 소시지를 자릅니다.

또 평론가 2에게 주기 전에 소시지를 자릅니다.

...

이런 식으로 하면 M이 나오겠지요.

이 각각의 사람들이 N/M씩 가져가게 되고요. t명이 가져갔다면

t*(N/M)만큼의 소시지가 사라지겠지요.

문제는 (t*N)/M이 자연수인 경우가 있습니다. 이 경우는 소시지를 안 잘라도 되겠죠..

그러면 제가 말한 (t*N)/M이 자연수가 되는 경우를 생각해 봅시다.

(1) N과 M이 서로소인 경우는

t가 M인 경우에만 (t*N)/M이 자연수가 됩니다. 고로 1만 빠지겠죠.

(2) gcd(N,M) = k라고 가정해 봅시다.

그러면 (t*N)/M = (t*N/k)/(M/k)로 나타낼 수 있고요. N/k, M/k 역시 자연수가 되겠죠.

그러면 (t*Q)/Q'으로 나타낼 수 있는데요. Q와 Q'은 서로소이므로

t가 Q'의 배수일 때만 자연수가 되어버립니다.

예를 들어서 N=9, M=15라고 가정하면 이 둘의 gcd는 3입니다.

Q와 Q'은 3, 5가 나오고요. t는 1부터 15까지의 자연수인데요. 이 중에 t가 5의 배수인 경우는..

5, 10, 15가 나오므로, 15에서 3이 빠진 12가 답이 되는데요.

M - M/Q'를 구하는 것과 사실 동치이지요.

Q' = M/gcd(N,M) 이네요. 따라서 M/Q' = gcd(N,M)입니다.

와 자세한 설명 감사합니다.

더 생각을 했어야 됬군요 ㅋㅋ

이해가 됬습니다.