라그랑주 정리

p가 소수일 때

\[ f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 \equiv 0 \pmod{p} \]

는 최대 n개의 incongruent solution을 가진다. \( ( a_n \not \equiv 0 \pmod{p} ) \)

n에 관한 귀납적 접근을 시도한다.

n=1일 때 \(f(x) = a_1 x+a_0 \equiv 0 \pmod{p} \), 즉 \(a_1 x \equiv -a_0 \pmod{p} \) 이라는 일차식이 나오는데, a_1과 p의 최대공약수가 1이므로 해가 최대 한 개 존재한다.

n=k-1일 때 \(f(x) \equiv 0 \pmod{p} \)의 해가 최대 k-1개 존재한다고 가정하자.

n=k일 때

\[f(x) \equiv 0 \pmod{p} \]

이 식의 해가 없다면 명제는 참이다.

이 식의 해가 있다면 그 해를 \(a\)로 놓자.

\[f(x) \equiv (x-a)q(x) \pmod{p} \]

incongruent한 또 다른 해 \(b\)에 대해서 생각해보면

\[f(x) \equiv (b-a)q(b) \pmod{p} \]

\(b-a \not \equiv 0 \pmod{p} \)이므로 \(q(b) \equiv 0 \pmod{p}\)이다. 그런 b는 최대 k-1개 있고, a와 같이 생각하면 전체 해는 최대 k개 존재한다.