서로소인 두 수 m, n의 조합으로 만들수 없는 최대 양의 정수 값은 어떻게 구해지나요?
즉, m의 배수와 n의 배수의 합으로 표현되어지지 않는 최대 양의 정수값을 구하는 방법이 없을런지요?
예를들면, 2와 3의 배수들의 합으로 표현할 수 없는 최대 양의 정수는 1이죠
{2, 3, 4=2+2, 5=2+3, 6=3+3, 7=2*2+3, ... }
또한 3과 5의 배수들의 합으로 표현할 수 없는 최대 양의 정수는 7이죠
{3, 5, 6=3+3, 8=3+5, 9=3*3, 10=2*5, 11=2*3+5, ...}
그러다면 위 문제에서와 같이 m과 n의 배수들의 합으로 표현할 수 없는 최대 양의 정수값을
찾을 수 있는 이론적 근거와 공식유도 방법이 궁금합니다.
많은 고수님들의 명쾌한 해법부탁드립니다.
첫댓글 일단 두 개의 다른 서로소 a,b 중에 a=2 이면 구하고자하는 값은 b-2가 됩니다. 2는 유일한 짝수 소수이고 b는 홀수소수이므로 생각해보시면 금방알 수 있습니다.
둘다 2가 아닌 소수라면... 좀더 생각해보지요. ㅎ 잠이와요.
n<m 이라고 가정해 볼께요. 그러면 n,2n,3n,4n,...,(m-1)n 은 m으로 나눈 나머지가 다 다르겠지요. 그러면 이것들을 가지고 잉여계를 구축할 수 있고 최소한 이것 보다 큰 수들은 그러면 n과 m의 조합으로 나타내어 지겠네요. 이걸 이용해서 다시 한번 생각해보세요^^