| [ QuizWit ] in KIDS 글 쓴 이(By): guest (sol) <maggie.kaist.ac.> 날 짜 (Date): 2002년 9월 2일 월요일 오후 10시 45분 58초 제 목(Title): Re: Postage Stamp 문제 2. proof] GCD(m,n)=1, WLOG, let's assume m<n. Because GCD(m,n)=1, n mod m , n*2 mod m, n*3 mod m, n*4 mod m ..., n*(m-1) mod m are different. That is, { n mod m, n*2 mod m, n*3 mod m,..., n*(m-1) mod m } = { 1, 2, 3, ..., m-1}. So the last element that we cannot express with m, n is n*(m-1)-m. So the answer is n*(m-1)-m+1, because the other elments can be expressed by m*?+?. |