검문 문제는 최대공약수를 활용하는 문제이다. 두 수를 어떤 수로 나누었을 때 나머지를 같게 하는 수는 두 수의 차의 모든 약수이다. 또한 두 수의 차의 모든 약수는 두수를 나머지가 같게 나눈다. 위의 명제는 귀류법과 a=bq+r의 식을 활용하여 증명할 수 있다. 위의 두 문장은 두 수를 나누었을 때 나머지를 같게 만드는 어떤 수가 두 수의 차의 약수와 동일하다는 것을 알려준다. M개의 수를 나머지가 같게 만드는 어떤 수를 찾아야하므로 M개의 수를 정렬하고 순차적으로 두 수의 차의 최대공약수를 계산하여야 한다. 최종적으로 M개의 수를 나누었을 때 같은 나머지를 같게 하는 어떤 수들을 약수로 같는 최대공약수가 얻어진다. 이 최대공약수의 모든 약수를 출력함으로써 문제는 해결된다. 주의할 점은 마지막에 구한 최..