Lagranges sats (talteori)

I talteorin är Lagranges teorem ett uttalande som är uppkallat efter Joseph-Louis Lagrange om hur ofta ett polynom över heltal kan utvärderas till en multipel av ett fast primtal . Mer exakt anger den att om p är ett primtal, ${\displaystyle x\in \mathbb {Z} /p\mathbb {Z} } ,$ och $\textstyle f(x)\in \mathbb {Z} [x]$ är ett polynom med heltalskoefficienter, då antingen:

varje koefficient för $f (x)$ är delbar med p , eller
$f (x) \equiv 0 (mod p)$ har som mest $grader f (x)$ lösningar

där $grader f (x)$ är graden av $f (x)$ . Om modulen inte är primtal, är det möjligt att det finns fler än $deg f (x)$ lösningar.

Ett bevis på Lagranges sats

De två nyckelidéerna är följande. Låt $g (x) \in (Z / p) [x]$ vara polynomet som erhålls från $f (x)$ genom att ta koefficienterna $mod p$ . Nu:

$f (k)$ är delbart med $p$ om och endast om $g (k) = 0$ ; och
$g (x)$ har inte mer än $deg g (x)$ rötter.

Mer rigoröst, börja med att notera att $g (x) = 0$ om och endast om varje koefficient för $f (x)$ är delbar med $p$ . Antag $g (x) \neq 0$ ; dess grad är således väldefinierad. Det är lätt att se $deg g (x) \leq deg f (x)$ . För att bevisa (1), notera först att vi kan beräkna $g (k)$ antingen direkt, dvs genom att plugga in ( restklassen av) $k$ och utföra aritmetik i $Z / p$ , eller genom att reducera $f (k) mod p$ . Därför $g (k) = 0$ om och endast om $f (k) \equiv 0 (mod p)$ , dvs om och endast om $f (k)$ är delbart med $p$ . För att bevisa (2), notera att $Z / p$ är ett fält , vilket är ett standardfaktum (ett snabbt bevis är att notera att eftersom $p$ är primtal, är $Z / p$ en finit integral domän , alltså ett fält). Ett annat standardfaktum är att ett polynom som inte är noll över ett fält har högst lika många rötter som dess grad; detta följer av divisionsalgoritmen .

Observera slutligen att två lösningar $f (k 1) \equiv f (k 2) \equiv 0 (mod p)$ är inkongruenta om och endast om $k_{1}\not \equiv k_{2}$ $(mod p)$ . Om man sätter ihop allt, är antalet inkongruenta lösningar med (1) detsamma som antalet rötter av $g (x)$ , som med (2) är högst $deg g (x)$ , vilket är högst $grader f (x)$ .

LeVeque, William J. (2002) [1956]. Ämnen i talteori, volym I och II . New York: Dover Publications. sid. 42 . ISBN 978-0-486-42539-9 . Zbl 1009.11001 .
Tattersall, James J. (2005). Elementär talteori i nio kapitel (2:a uppl.). Cambridge University Press . sid. 198. ISBN 0-521-85014-2 . Zbl 1071.11002 .