라그랑주의 정리(숫자 이론)

수 이론에서 라그랑주의 정리는 정수를 넘는 다항식이 고정된 프라임의 배수로 얼마나 자주 평가할 수 있는지에 대해 조셉 루이스 라그랑주의 이름을 딴 것이다.보다 정확하게는 p가 $소수$이고 ${\displaystyle f\mathbb{}}$( ${\displaystyle x}$) ${\displaystyle \in }$ Z${\displaystyle }$[ ${\displaystyle x}$ ${\displaystyle ]}$ ${\$이(가) 정수 계수를 갖는 다항식인 경우$$ 다음 중 하나라고 명시되어 있다.

• f(x)의 모든 계수는 p, 또는
• f(x) ≡ 0(mod p)에는 최대로 f(x) 부적합 용액이 있음

여기서 deg f(x)는 f(x)의 수준이다.해결책은 p의 배수로 차이가 나지 않으면 "불합치"이다.계수가 primary가 아닐 경우 deg f(x) 이상의 용액이 있을 수 있다.

라그랑주의 정리 증명

두 가지 핵심 아이디어는 다음과 같다.g(x) ∈ (Z/p)[x]를 계수 mod p를 취하여 f(x)에서 얻은 다항식이 되게 한다.지금:

1. f(k)는 g(k) = 0인 경우에만 p로 구분되며,
2. g(x)는 deg g(x) 루트를 초과하지 않는다.

보다 엄격하게 f(x)의 각 계수가 p로 구분되는 경우에만 g(x) = 0이라는 점을 주목하십시오.g(x) ≠ 0을 가정한다. 그 정도는 따라서 잘 정의된다.dg g(x) ≤ deg f(x)를 쉽게 볼 수 있다.(1)을 증명하기 위해, 먼저 g(k)를 직접 계산할 수 있다는 것을 주목한다. 즉, (의 잔류 등급) k를 연결하고 Z/p로 산술을 수행하거나, f(k) mod p를 줄여서 계산한다.따라서 g(k)는 f(k) ) 0(mod p)인 경우에만 0, 즉 f(k)가 p로 구분되는 경우에만 0이다.(2)를 증명하기 위해, Z/p는 표준 사실인 필드(p가 prime이기 때문에 Z/p는 유한 적분 영역이므로 필드라는 것을 주목하는 것이 빠른 증거임)라는 점에 주목한다.또 다른 표준적인 사실은 한 필드 위에 0이 아닌 다항식은 그 정도만큼의 뿌리를 가지고 있다는 것이다. 이것은 분할 알고리즘에서 따온 것이다.

마지막으로, 두 솔루션 f(k₁) ≡ f(k₂) ≡ 0(mod p)은 $k{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {k\mathrm{}}_{}}$ 2 ${\$mod p)인 경우에만 부적합하다는 점에 유의하십시오.모든 것을 종합하면 (1)에 의한 부조화 용액의 수는 g(x)의 뿌리 수와 같으며, (2)에 의한 용액의 수는 최대 deg g(x)이며, 최대 deg f(x)이다.

참조

• LeVeque, William J. (2002) [1956]. Topics in Number Theory, Volumes I and II. New York: Dover Publications. p. 42. ISBN 978-0-486-42539-9. Zbl 1009.11001.
• Tattersall, James J. (2005). Elementary Number Theory in Nine Chapters (2nd ed.). Cambridge University Press. p. 198. ISBN 0-521-85014-2. Zbl 1071.11002.