Problems and Solutions #036

Problem #036

어떤 충분히 큰 정수가 $1$부터 $10000$까지의 수 중에서 정확히 두 개의 수를 제외한 모든 수로 나누어떨어진다고 한다. 이때 제외되는 두 개의 수가 연속인 정수라면, 이 두 수는 어떤 수여야 할까?

문제의 조건을 만족하는 충분히 큰 정수를 $N$이라 하고, $N$을 나누지 않는 두 연속인 정수를 각각 $k$, $k+1$이라 하자. 만약 $k\le 5000$이라면 $N$은 $k$, $k+1$, $2k$로 나누어떨어지게 되기 때문에 문제의 가정에 모순이다. 따라서 $5000<k<10000$임을 알 수 있다. 

이제 서로소인 두 정수 $m$과 $n$이 존재하여, $k=mn$과 같이 나타낼 수 있다고 가정해 보자. 만약에 $m$과 $n$이 모두 $N$을 나눈다면 $k$ 또한 $N$을 나누게 되어 모순이므로, $m$과 $n$ 중에 적어도 하나는 $N$을 나누지 못한다. 하지만 이 경우, $N$을 나누지 않는 정수가 적어도 세 개 이상이 되므로 역시 모순이 발생한다. 마찬가지 이유로 $k+1=mn$을 만족하는 서로소인 두 정수 $m$과 $n$은 존재하지 않는다.

따라서 $k$와 $k+1$ 모두 어떤 소수의 거듭제곱의 형태여야만 함을 알 수 있다. 또한 $k$ 또는 $k+1$ 중에 하나는 짝수이므로 둘 중에 하나는 반드시 $2$의 거듭제곱의 형태여야만 한다. 하지만 $2$의 거듭제곱의 형태인 수 중에서 $5000$과 $10000$ 사이의 수는 $2^{13}=8192$가 유일하다. 또한 $8191$은 소수이므로 조건을 만족하고, $8193=3\times 2731$으로 (서로소인 두 정수의 곱의 형태가 되어) 조건을 만족하지 못함을 알 수 있다. 

따라서 문제의 조건을 만족하는 연속인 두 정수는 유일하고 이는 $8191$, $8192$이다.