정수 계수 다항식 P가 0과 1에서 모두 짝수다. 두 입력의 검사만으로 모든 정수 n에서 P(n)이 짝수라고 결론 낼 수 있을까? 계수 조건을 정수값만 내는 다항식으로 약하게 바꾸면 같은 결론인지도 확인한다.
정수 n이 짝수이면 모든 양의 거듭제곱 n^k가 짝수여서 P(n)의 홀짝은 상수항 P(0)의 홀짝과 같다. n이 홀수이면 모든 n^k가 홀수라 각 정수 계수를 더한 P(1)의 홀짝과 같다. 두 종류의 입력에서 모두 짝수이므로 모든 정수에서 짝수다. 그러나 정숫값만 내는 조건으로 바꾸면 Q가 반례다. 연속한 정수의 곱은 짝수여서 Q(n)은 늘 정수지만 Q(0),Q(1)은 0이고 Q(2)는 1이다. 유한 검사가 충분한 이유는 검사 횟수가 많아서가 아니라 정수 계수와 두 나머지류라는 구조에 있다.
교사 질문: 3의 배수인지 확인하려면 어떤 세 입력을 검사할 수 있는지 같은 거듭제곱의 나머지 논증을 확장하자.
출처·착안: 第35回日本数学オリンピック本選問題. 위 문항의 조건·수치·풀이와 교사 질문은 새로 작성했다.