라그랑주의 정리 (정수론)

다른 뜻에 관한 내용은 라그랑주 정리 문서를 읽어 주세요.

진술

p가 소수일 때, 합동식

[math]\displaystyle{ a_0+a_1x+\cdots+a_nx^n\equiv 0\pmod{p}, a_n\not\equiv 0\pmod{p} }[/math]

는 n개 이하의 해를 가진다. 만약 합동식이 해 n개를 가지고

[math]\displaystyle{ x\equiv c_1\pmod{p},x\equiv c_2\pmod{p},\cdots, x\equiv c_n\pmod{p} }[/math]

이면 임의의 정수 x에 대해

[math]\displaystyle{ a_0+a_1x+\cdots+a_nx^n\equiv a_n(x-c_1)(x-c_2)\cdots(x-c_n)\pmod{p} }[/math]

이다.

증명

수학적 귀납법을 이용해 증명한다.

합동식

[math]\displaystyle{ a_0+a_1x \equiv 0\pmod{p},a_1\not\equiv 0\pmod{p} }[/math]

은 [math]\displaystyle{ \gcd(a_1,p)=1 }[/math]이므로 해를 단 하나 가진다. 이 해를 [math]\displaystyle{ x\equiv c_1\pmod{p} }[/math]라고 하자. 그러면

[math]\displaystyle{ a_0+a_1c_1\equiv 0\pmod{p} }[/math]

이므로

[math]\displaystyle{ a_0\equiv-a_1c_1\pmod{p} }[/math]

이다. 따라서

[math]\displaystyle{ a_0+a_1x\equiv a_1(x-c_1)\pmod{p} }[/math]

이다. 이제 [math]\displaystyle{ n\ge 2 }[/math]일 때 [math]\displaystyle{ n-1 }[/math]차 합동식의 해의 개수가 [math]\displaystyle{ n-1 }[/math]개 이하라고 가정하자. 만약 합동식

[math]\displaystyle{ a_0+a_1x+\cdots+a_nx^n\equiv 0\pmod{p}, a_n\not\equiv 0\pmod{p} }[/math]

이 해를 가지지 않는다면, 원하는 결론을 얻는다. 합동식이 해 [math]\displaystyle{ x\equiv c_1\pmod{p} }[/math]를 가진다고 가정하자. 이때 인수정리(remainder theorem)에 의해

[math]\displaystyle{ a_0+a_1x+\cdots+a_nx^n=(x-c_1)q_1(x) }[/math]

인 다항식 [math]\displaystyle{ q_1(x) }[/math]가 존재하고 [math]\displaystyle{ \deg q_1(x)=n-1 }[/math]이다. 따라서

[math]\displaystyle{ a_0+a_1x+\cdots+a_nx^n\equiv (x-c_1)q_1(x)\pmod{p} }[/math]

이다. 귀납법 가정에 의해 [math]\displaystyle{ q_1(x)\equiv 0\pmod{p} }[/math]는 [math]\displaystyle{ n-1 }[/math]개 이하의 해를 가지므로, [math]\displaystyle{ a_0+a_1x+\cdots+a_nx^n\equiv 0\pmod{p} }[/math]는 n개 이하의 해를 가진다. 만약 합동식의 해 [math]\displaystyle{ x\equiv c_2\pmod{p},c_2\not\equiv c_1\pmod{p} }[/math]가 존재한다면 반드시 [math]\displaystyle{ q_1(x)\equiv 0\pmod{p} }[/math]의 해이고, 따라서

[math]\displaystyle{ q_1(x)=(x-c_2)q_2(x) }[/math]

인 [math]\displaystyle{ n-2 }[/math]차의 다항식 [math]\displaystyle{ q_2(x) }[/math]가 존재한다. 해가 n개 존재한다면 같은 과정을 반복하여 원하는 결론을 얻을 수 있다.