Định lý cơ bản của số học

Trong toán học, định lý cơ bản của số học (tiếng Anh: Fundamental theorem of arithmetic) hay định lý phân tích thừa số nguyên tố (tiếng Anh: Prime factorization theorem) phát biểu rằng mọi số nguyên lớn hơn 1 đều có thể dược biểu diễn bằng một tích của các số nguyên tố duy nhất, ví dụ: 1200 = 2 4 .3 1 .5 2 {\displaystyle 1200=2^{4}.3^{1}.5^{2}} Điều này có hai ý nghĩa: Thứ nhất, số 1200 có thể được biểu diễn bằng tích của các số nguyên tố, và thứ hai - không quan trọng cách làm hay hướng đi, số 1200 này sẽ luôn là tích của 4 số 2 - 1 số 3 và 2 số 5. Việc phân tích ra thừa số nguyên tố là rất quan trọng, vì nếu như phân tích ra các hợp số, kết quả này không đồng nhất, ví dụ: 16 = 2.8 = 4.4 = 1.16 {\displaystyle 16=2.8=4.4=1.16} Định lý này cũng là một trong những lý do để khẳng định 1 không phải số nguyên tố, vì nếu 1 là số nguyên tố - việc phân tích thừa số nguyên tố của một số khi đó sẽ trở nên không thể đồng nhất, khi mà ta có thể viết: 2 = 2.1 = 2.1.1 = . . . {\displaystyle 2=2.1=2.1.1=...} Định lý này góp phần xây dựng nên các cấu trúc đại số, đặc biệt là với vành đa thức và trường. Trong bộ sách Cơ sở của Euclid, ông đã nêu ra định lý này và đưa ra chứng minh cho định lý như sau: Nếu hai số nhân với nhau ra một số mới, và hai số đó được cấu thành bởi những số nguyên tố - số mới đó sẽ được cấu thành bởi những số nguyên tố ban đầu. - Euclid, cuốn 7 - Cơ sở, câu 30. Ta có thể hiểu câu này theo ngôn ngữ toán học hiện đại: Nếu như tích số ab chia hết cho số nguyên tố p, thì hoặc số a - hoặc số b sẽ chia hết cho p, hoặc là cả hai. Câu này cũng thường được biết tới là Bổ đề Euclid, và cũng chính là chìa khóa quan trọng để chứng minh Định lý cơ bản của số học. Mọi hợp số đều được cấu thành bởi một vài số nguyên tố. - Euclid, cuốn 7 - Cơ sở, câu 31. Ngôn ngữ Toán học hiện đại: Mọi số nguyên lớn hơn 1 đều có ước số là các số nguyên tố. Mệnh đề này có thể được chứng minh bằng phản chứng. Một số bất kì hoặc là số nguyên tố, hoặc là được tạo bởi các số nguyên tố. - Euclid, cuốn 7 - Cơ sở, câu 32. Câu 32 này là hệ quả của câu 31 đã được đề cập, từ đó chứng minh rằng sự phân tích thừa số nguyên tố là hoàn toàn khả thi với mọi số tự nhiên lớn hơn 1. Nếu như một số được cấu thành bởi một số các số nguyên tố, nó sẽ không thể được cấu thành bởi một bộ các số nguyên tố khác - trừ chính bộ số nguyên tố tạo ra nó. - Euclid, cuốn 9 - Cơ sở, câu 14. Ngôn ngữ Toán học hiện đại: Bội số chung nhỏ nhất của một số các số nguyên tố không thể là tích của một số các số nguyên tố khác. Câu 14 này được rút ra từ câu 30 của cuốn thứ 7 đã nêu trên, chứng minh rằng sự phân tích này cho ra một kết quả duy nhất - một điều được nhà toán học André Weil đặc biệt chỉ ra. Mọi số tự nhiên lớn hơn 1 có thể viết một cách duy nhất (không kể sự sai khác về thứ tự các thừa số) thành tích các thừa số nguyên tố. Mọi số tự nhiên n lớn hơn 1, có thể viết duy nhất dưới dạng: n = p 1 α 1 p 2 α 2 … p k α k {\displaystyle n={p_{1}}^{\alpha _{1}}{p_{2}}^{\alpha _{2}}{\dots }{p_{k}}^{\alpha _{k}}} trong đó p 1 , p 2 , , … , p k {\displaystyle {p_{1}},{p_{2}},,{\dots },{p_{k}}} là các số nguyên tố và α 1 , α 2 , … , α k {\displaystyle \alpha _{1},\alpha _{2},\dots ,\alpha _{k}} là các số tự nhiên dương. Tuy nhiên do tính giao hoán của phép nhân các số tự nhiên, tính duy nhất bỏ qua các sai khác về thứ tự các thừa số. Vế phải của đẳng thức này được gọi là dạng phân tích tiêu chuẩn của n. Chẳng hạn 6936 = 2 3 × 3 × 17 2 , {\displaystyle 6936=2^{3}\times 3\times 17^{2},\,\!} 1200 = 2 4 × 3 × 5 2 . {\displaystyle 1200=2^{4}\times 3\times 5^{2}.\,\!} Người ta cho rằng định lý được Euclid chứng minh, tuy nhiên nó được trình bày đầy đủ lần đầu tiên trong Disquisitiones Arithmeticae bởi Carl Friedrich Gauss. Chứng minh gồm hai phần. Phần một chứng minh mọi số có thể viết dưới dạng tích của một hoặc nhiều số nguyên tố. Phần thứ hai chứng tỏ rằng biểu diễn đó là duy nhất. Trước hết, mỗi số nguyên tố là tích của một thừa số là chính nó. Giả sử rằng có các số nguyên dương lớn hơn 1 không biểu diễn được thành tích các số nguyên tố. Khi đó gọi n là số nhỏ nhất trong các số đó. Số n này khác 1 và là hợp số. Do đó n = ab trong đó cả a và b là các số nguyên dương nhỏ hơn n. Vì n là số nhỏ nhất không thể phân tích thành tích các số nguyên tố nên cả a và b phân tích được thành tích các số nguyên tố. Nhưng khi đó n = ab lại phân tích được. Điều này mâu thuẫn với giả thiết. Ta giả sử rằng tồn tại số nguyên lớn hơn 1 mà có 2 cách biểu diễn dưới dạng tích các thừa số nguyên tố. Khi đó giả sử s là số nhỏ nhất trong các số như vậy, tức là s = p 1 p 2 . . . p m = q 1 q 2 . . . q n {\displaystyle s=p_{1}p_{2}...p_{m}=q_{1}q_{2}...q_{n}} với p i , q j {\displaystyle p_{i},q_{j}} là các số nguyên tố. Do p 1 {\displaystyle p_{1}} chia hết q 1 q 2 . . . q n {\displaystyle q_{1}q_{2}...q_{n}} suy ra tồn tại q j {\displaystyle q_{j}} mà p 1 {\displaystyle p_{1}} chia hết q j {\displaystyle q_{j}} . Từ đó ta có p i = q j {\displaystyle p_{i}=q_{j}} , bỏ 2 số nguyên tố ra khỏi đẳng thức ta được 2 vế là 2 khai triển khác nhau của số s chia cho p 1 {\displaystyle p_{1}} , mà theo giả thuyết s là số nhỏ nhất như vậy, mâu thuẫn này chứng tỏ giả thiết là sai. vậy mỗi số nguyên lớn hơn một chỉ có một biểu diễn duy nhất dưới dạng tích thừa số nguyên tố (không kể đến thứ tự các thừa số). Bảng các phân tích tiêu chuẩn của 1000 số tự nhiên đầu tiên ^ Weil, André (2007). Number theory : an approach through history from Hammurapi to Legendre. Boston: Birkhäuser. ISBN 978-0-8176-4571-7. OCLC 612306237. ^ Long (1972, tr. 44) ^ Pettofrezzo & Byrkit (1970, tr. 53) ^ Hardy & Wright (2008, Thm 2)Lỗi harv: không có mục tiêu: CITEREFHardyWright2008 (trợ giúp) ^ Gauss & Clarke (1986, Art. 16) The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes. Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 978-0-387-96254-2 Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 The two monographs Gauss published on biquadratic reciprocity have consecutively numbered sections: the first contains §§ 1–23 and the second §§ 24–76. Footnotes referencing these are of the form "Gauss, BQ, § n". Footnotes referencing the Disquisitiones Arithmeticae are of the form "Gauss, DA, Art. n". Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima, Göttingen: Comment. Soc. regiae sci, Göttingen 6 Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda, Göttingen: Comment. Soc. regiae sci, Göttingen 7 These are in Gauss's Werke, Vol II, pp. 65–92 and 93–148; German translations are pp. 511–533 and 534–586 of the German edition of the Disquisitiones. Baker, Alan (1984), A Concise Introduction to the Theory of Numbers, Cambridge, UK: Cambridge University Press, ISBN 978-0-521-28654-1 Euclid (1956), The thirteen books of the Elements, 2 (Books III-IX), Translated by Thomas Little Heath , New York: Dover, ISBN 978-0-486-60089-5 Bản mẫu:Hardy and Wright A. Kornilowicz; P. Rudnicki (2004), “Fundamental theorem of arithmetic”, Formalized Mathematics, 12 (2): 179–185 Long, Calvin T. (1972), Elementary Introduction to Number Theory (ấn bản 2), Lexington: D. C. Heath and Company, LCCN 77-171950. Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766. Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5 Weisstein, Eric W., "Abnormal number", MathWorld. Weisstein, Eric W., "Fundamental Theorem of Arithmetic", MathWorld.