1. 전수 조사에 의한 증명 (Exhaustive Proof by Classification)

모듈로 연산의 가장 강력한 증명 방식은 **"모든 정수를 p개의 나머지 그룹으로 분류하여, 각 그룹에 대해 성립함을 보이면 전체에 대해 성립함이 증명된다"**는 논리입니다.

• 원리: 정수 n에대해 어떤 성질을 증명하고 싶을 때, n을 직접 대입하는 것은 불가능합니다(무한하므로). 하지만 법(mod) p를 도입하면, 모든 정수는 0,1,…,p−1 중 하나의 나머지를 가집니다. 따라서 이 p가지 케이스만 전부 확인하면 증명이 완료됩니다,.

• 실제 예시 (교토대 문제): n3−7n+9가 소수가 되는 n을 구하는 문제에서, n을 3으로 나눈 나머지(0,1,2)로 분류했습니다.

    ◦ n≡0일 때: 03−0+0≡0(mod3)

    ◦ n≡1일 때: 13−7(1)+9≡1−1+0≡0(mod3)

    ◦ n≡2일 때: 23−7(2)+9≡8−14≡−6≡0(mod3)

    ◦ 결론: 어떤 경우든 식은 3의 배수입니다. 따라서 소수가 되려면 그 값 자체가 3이어야 한다고 증명하여 후보를 좁혔습니다.