Lagrange's theorem (number theory)

In number theory, Lagrange's theorem is a statement named after Joseph-Louis Lagrange about how frequently a polynomial over the integers may evaluate to a multiple of a fixed prime p. More precisely, it states that for all integer polynomials $\textstyle f\in \mathbb {Z} [x]$ , either:

every coefficient of $f$ is divisible by p, or
$p\mid f(x)$ has at most $deg f$ solutions in ${1, 2, ..., p}$ ,

where $deg f$ is the degree of $f$ .

This can be stated with congruence classes as follows: for all polynomials $\textstyle f\in (\mathbb {Z} /p\mathbb {Z} )[x]$ with p prime, either:

every coefficient of $f$ is null, or
$f(x)=0$ has at most $deg f$ solutions in $\mathbb {Z} /p\mathbb {Z}$ .

If p is not prime, then there can potentially be more than $deg f (x)$ solutions. Consider for example p=8 and the polynomial f(x)=x²-1, where 1, 3, 5, 7 are all solutions.

Proof

Let $\textstyle f\in \mathbb {Z} [x]$ be an integer polynomial, and write $g \in (Z / p Z)[x]$ the polynomial obtained by taking its coefficients $mod p$ . Then, for all integers x,

$f(x)\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad g(x)\equiv 0{\pmod {p}}$ .

Furthermore, by the basic rules of modular arithmetic,

$f(x)\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad f(x{\bmod {p}})\equiv 0{\pmod {p}}\quad \Longleftrightarrow \quad g(x{\bmod {p}})\equiv 0{\pmod {p}}$ .

Both versions of the theorem (over $Z$ and over $Z / p Z$ ) are thus equivalent. We prove the second version by induction on the degree, in the case where the coefficients of f are not all null.

If $deg f = 0$ then $f$ has no roots and the statement is true.

If $deg f \geq 1$ without roots then the statement is also trivially true.

Otherwise, $deg f \geq 1$ and $f$ has a root $k\in \mathbb {Z} /p\mathbb {Z}$ . The fact that $Z / p Z$ is a field allows to apply the division algorithm to $f$ and the polynomial $x - k$ (of degree 1), which yields the existence of a polynomial $\textstyle g\in (\mathbb {Z} /p\mathbb {Z} )[x]$ (of degree lower than that of $f$ ) and of a constant $\textstyle r\in \mathbb {Z} /p\mathbb {Z}$ (of degree lower than 1) such that

$f(x)=g(x)(x-k)+r.$

Evaluating at $x = k$ provides $r = 0$ .^[1] The other roots of f are then roots of g as well, which by the induction property are at most $deg g \leq deg f - 1$ in number. This proves the result.

Generalization

Let $p (X)$ be a polynomial over an integral domain $R$ with degree $n > 0$ . Then the polynomial equation $p (x) = 0$ has at most $n = deg(p (X))$ roots in $R$ .^[2]

References

^ Factor theorem#Proof_3
^ "Polynomials and rings Chapter 3: Integral domains and fields" (PDF). Theorem 1.7.

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.

Read other articles:

Daftar Menteri Badan Usaha Milik Negara Indonesia

Menteri Badan Usaha Milik Negara IndonesiaLogo Kementerian Badan Usaha Milik Negara IndonesiaBendera Kementerian Badan Usaha Milik Negara IndonesiaPetahanaErick Thohirsejak 23 Oktober 2019Kementerian Badan Usaha Milik Negara IndonesiaDitunjuk olehPresiden IndonesiaPejabat perdanaTanri AbengDibentuk16 Maret 1998; 25 tahun lalu (1998-03-16)Situs webbumn.go.id Menteri Badan Usaha Milik Negara Indonesia, umumnya disingkat Menteri BUMN adalah kepala Kementerian Badan Usaha Milik Negara I...

Buthidaung

Town in Rakhine State, MyanmarBusidaung ဘူးသီးတောင်မြို့TownButhidaungButhidaung in 2016BusidaungLocation in Myanmar (Burma)Coordinates: 20°52′08″N 92°31′41″E / 20.8690°N 92.528°E / 20.8690; 92.528Country MyanmarDivision Rakhine State(Arakan)DistrictMaungdaw DistrictTownshipButhidaung TownshipPopulation (2021) • Total55,545[1] • Ethnicities93% Rohingya6% Rakhine<1% Others ...

بطولة أم المعارك 2000

بطولة أم المعارك 2000 تاريخ الإنشاء 1991 الرياضة كرة القدم البلد العراق القارة آسيا المؤسس الاتحاد العراقي لكرة القدم النسخة الأولى 1991 عدد الفرق 8 أحدث بطل الشرطة تعديل مصدري - تعديل بطولة أم المعارك 2000 وهي بطولة كرة قدم نظمها اتحاد كرة القدم العراقي للفترة من 3 ديسمبر إ�...

Temple Israel (Tulsa, Oklahoma)

For other synagogues named Temple Israel, see Temple Israel. Temple IsraelReligionAffiliationReform JudaismEcclesiastical or organizational statusSynagogueLeadershipRabbi Michael Weinstein[1]StatusActiveLocationLocation2004 East 22nd Place, Tulsa, OklahomaCountryUnited StatesLocation in OklahomaGeographic coordinates36°07′50″N 95°57′46″W / 36.130579°N 95.962776°W / 36.130579; -95.962776ArchitectureArchitect(s)Percival GoodmanTypeSynagogueDate establ...

SOCATA Horizon

GY-80 Horizon A Socata Horizon Taking Off Role Four-seat light aircraftType of aircraft National origin France Manufacturer Sud Aviation SOCATA Designer Yves Gardan [fr] First flight 21 July 1960 Number built 273[1] Variants SOCATA ST-10 Diplomate The GY-80 Horizon is a French four-seat touring monoplane of the 1960s designed by Yves Gardan [fr] and built under licence, first by Sud Aviation, and later by that company's SOCATA subsidiary. Design and developm...

New Age travellers

Category of people in the UK living alternative lifestyles See also: crust punks and gutter punks New Age travellersVehicles used by New Age travellersRegions with significant populationsUnited KingdomReligionsNew Age New Age Travellers (synonymous with and otherwise known as New Travellers[1]) are people located primarily in the United Kingdom generally espousing New Age beliefs with hippie or Bohemian culture of the 1960s. New Age Travellers used to travel between free music festiva...

Transport en commun en Islande

Un bus Strætó à Reykjavik. Arrêt de bus à Reykjavík. Le système des transports en commun islandais est relativement peu développé et certaines zones ne sont que très peu desservies par les transports en commun. L'Islande ne possède aucun service de transport public à l'échelle nationale. Quelques transports sont disponibles dans la plupart des zones urbanisées, par exemple, les bus Strætó bs. desservent Reykjavik, et Strætisvagnar Akureyrar au nord de la ville d'Akureyri. Dan...

1. deild 1983 (Islanda)

1. deild 1983 Competizione 1. deild Sport Calcio Edizione 72ª Organizzatore KSI Date dal 18 maggio 1983all'11 settembre 1983 Luogo Islanda Partecipanti 10 Risultati Vincitore ÍA(11º titolo) Retrocessioni ÍBVÍBÍ Statistiche Miglior marcatore Ingi Björn Albertsson (14 goal) Cronologia della competizione 1982 1984 Manuale La 1. deild 1983 fu la 72ª edizione della massima serie del campionato di calcio islandese disputata tra il 18 maggio e il 11 settembre 1983 e conclusa ...

Martin Tabert

American man arrested and beaten to death by a prison labor supervisor in 1922 Martin TabertMartin Tabert (1921)Born1899Cavalier County, North Dakota, United StatesDiedFebruary 2, 1922(1922-02-02) (aged 22)Clara, Florida, United StatesNationalityAmericanCriminal chargesVagrancyCriminal penaltyFine of $25; later sentenced to convict leasingCriminal statusdied in prison Martin Tabert (1899 – February 2, 1922) was an American forced laborer. The circumstances of Tabert's death – being a...

Battle of Ayta ash-Shab

Battle during the 2006 Lebanon War Battle of Ayta ash-Sha'bPart of 2006 Lebanon WarDate12 July – 14 August 2006LocationAyta ash-Sha'b, Southern LebanonResult Hezbollah victory Israel failed to capture the town[1]Belligerents Israel Defense Forces HezbollahCommanders and leaders Brig.-Gen. Udi Adam, head of Northern CommandBrig.-Gen. Gal Hirsch,commander of the 91st Div.Col. Ilan Atias, commander of 2nd BrigadeCol. Hagai Mordechai, commander of 35th Brigade UnknownUnits involved 35th...

الدوري الفرنسي 2011–12

الدوري الفرنسي 2011–12 تفاصيل الموسم الدوري الفرنسي النسخة 74 البلد فرنسا التاريخ بداية:6 أغسطس 2011 نهاية:20 مايو 2012 المنظم اتحاد فرنسا لكرة القدم البطل نادي مونبلييه الهابطون نادي ديجون، ونادي أوكسير، ونادي كاين مباريات ملعوبة 380 عدد المشا�...

Directgov

Former British government website DirectgovScreenshot Type of siteGovernment informationAvailable inEnglish and WelshOwnerHM GovernmentCreated byUK government departmentsURLdirect.gov.uk (archive)CommercialNoRegistrationNoLaunched1 April 2004; 20 years ago (2004-04-01)Current statusOffline 17 October 2012; 11 years ago (2012-10-17)Content licenseCrown copyright See copyright page for licencing information. Directgov was the British government...

كورانة (صوماي برادوست)

كورانة تقسيم إداري البلد إيران إحداثيات 37°43′27″N 44°41′21″E / 37.72416667°N 44.68916667°E / 37.72416667; 44.68916667 تعديل مصدري - تعديل كورانة هي قرية في مقاطعة أرومية، إيران. عدد سكان هذه القرية هو 504 في سنة 2006.[1] مراجع ^ تعداد سكان جمهورية إيران الإسلامية، 1385 / 2006. جمهوري�...

Korean Air Lines Flight 902

Aircraft shot down by Soviet air defense Korean Air Lines Flight 902The plane after landing in the Soviet Union, with visible damage to its left wingShootdownDate20 April 1978 (1978-04-20)SummaryShot down by Soviet Union[1]Sitenear Loukhi, Karelian ASSR, Russian SFSR, Soviet Union 66°02′54″N 33°04′14″E / 66.04833°N 33.07056°E / 66.04833; 33.07056AircraftAircraft typeBoeing 707-321BOperatorKorean Air LinesIATA flight No.KE902ICAO ...

Chocobo (series)

Video game series Video game seriesChocoboThere is no unified logo for the series; this logo was used in Chocobo's Mystery Dungeon Every Buddy!Publisher(s)Square, Square EnixArtist(s)Toshiyuki ItahanaFirst releaseChocobo's Mysterious DungeonDecember 23, 1997Latest releaseChocobo GPMarch 10, 2022Parent seriesFinal Fantasy The Chocobo series is part of the Final Fantasy franchise owned by Square Enix. A spin-off series meant to have more child and casual gamer appeal than the main games, it spa...

Музыка

У этого термина существуют и другие значения, см. Музыка. Деталь краснофигурной росписи аттической гидрии. Ок. 510 г. до н. э. Изображает урок музыки Исполнительские искусства Акробатика Балет Цирк Клоунада Танец Гимнастика Иллюзионизм Мимы Музыка Опера Реслинг Те�...

Zecca (moneta)

Questa voce o sezione sull'argomento economia non cita le fonti necessarie o quelle presenti sono insufficienti. Commento: Assenza totale di note e bibliografia Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Un denario di T. Carisio con Giunone Moneta e gli strumenti per la Zecca. Una zecca è un'officina che produce monete, banconote, timbri e sigilli di uno Stato[...

Thomas J. McIntyre

American politician Senator McIntyre redirects here. For other uses, see Senator McIntyre (disambiguation). Thomas J. McIntyreThomas J. McIntyreMayor of Laconia, New HampshireIn office1949 (1949)–1951 (1951)Preceded byAlbert ParmentierSucceeded byRobinson W. SmithUnited States Senatorfrom New HampshireIn officeNovember 13, 1962 (1962-11-13) – January 3, 1979 (1979-01-03)Preceded byMaurice J. Murphy Jr.Succeeded byGordon J. Humphrey Personal...

Ramtane Lamamra

Ramtane Lamamra (2022) Ramtane Lamamra (arabisch رمطان لعمامرة; * 15. Juni 1952 in Amizour, Provinz Bejaia)[1] ist ein algerischer Politiker und Außenminister der Demokratischen Volksrepublik Algerien von September 2013 bis Mai 2017 sowie kurzzeitig im März 2019. Inhaltsverzeichnis 1 Leben 2 Auszeichnungen 3 Weblinks 4 Einzelnachweise Leben Lamamra besuchte die National School of Administration (Diplomatic Section). Er war algerischer Botschafter in Portugal, den USA...

Collège de la Marche

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Collège de la Marche – news · newspapers · books · scholar · JSTOR (February 2024) Collège de la Marche, also known as collège de la Marche-Winville, is a subdivision of the old University of Paris located at de la Montagne Sainte-Geneviève street...