Pengguna:Klasüo/bak pasir/khusus

Dalam *Disquisitiones Arithmeticae* (1801) Gauss membuktikan teorema faktorisasi unik ^[1] dan menggunakannya untuk membuktikan hukum timbal balik kuadratik.^[2]

Dalam matematika, teorema dasar aritmetika, disebut juga teorema faktorisasi unik dan teorema faktorisasi prima menyatakan bahwa setiap bilangan bulat lebih besar dari 1 dapat direpresentasikan secara unik sebagai produk dari bilangan prima, urutan faktor hingga.^[3]^[4]^[5] Misalnya,

1200=2^{4}\cdot 3^{1}\cdot 5^{2}=(2\cdot 2\cdot 2\cdot 2)\cdot 3\cdot (5\cdot 5)=5\cdot 2\cdot 5\cdot 2\cdot 3\cdot 2\cdot 2=\ldots

Teorema mengatakan dua hal tentang contoh ini: pertama, bahwa 1200 bisa direpresentasikan sebagai produk bilangan prima, dan kedua, tidak peduli bagaimana hal ini dilakukan, akan selalu ada tepat empat ke-2, satu ke-3, dua ke-5, dan tidak ada bilangan prima lainnya dalam produk.

Persyaratan bahwa faktor-faktor menjadi prima diperlukan: faktorisasi yang mengandung bilangan komposit mungkin tak unik (misalnya, $12=2\cdot 6=3\cdot 4$ ).

Teorema ini adalah salah satu alasan mengapa 1 bukan sebagai bilangan prima: jika 1 adalah bilangan prima, maka faktorisasi menjadi bilangan prima tak unik; misalnya $2=2\cdot 1=2\cdot 1\cdot 1=\ldots$

Teorema ini digeneralisasikan ke struktur aljabar lainnya, khususnya untuk gelanggang polinomial di atas medan. Struktur ini disebut ranah faktorisasi unik.

Versi asli Euklides

Buku VII, proposisi 30, 31 dan 32, dan Buku IX, proposisi 14 dari Elemen Euklides pada dasarnya adalah pernyataan dan bukti teorema dasar.

Jika dua angka dengan mengalikan satu sama lain membuat beberapa nomor, dan setiap bilangan prima mengukur produk, itu akan juga mengukur salah satu nomor asli.

— Euklides, Elemen Buku VII, Proposisi 30

(Dalam terminologi modern: jika sebuah bilangan prima p membagi hasil kali ab, lalu p membagi a atau b atau keduanya.) Proposisi 30 disebut sebagai lema Euklides, dan merupakan kunci dalam pembuktian teorema dasar aritmetika.

Setiap bilangan komposit diukur dengan beberapa bilangan prima.

— Euklides, Elemen Buku VII, Proposisi 31

(Dalam terminologi modern: setiap bilangan bulat lebih besar dari satu dibagi secara merata oleh beberapa bilangan prima.) Proposisi 31 dibuktikan langsung oleh penurunan tak hingga.

Setiap nomor baik prima atau diukur dengan beberapa bilangan prima.

— Euklides, Elemen Buku VII, Proposisi 32

Proposisi 32 diturunkan dari proposisi 31, dan membuktikan bahwa dekomposisi itu mungkin.

Jika suatu bilangan terkecil yang diukur dengan bilangan prima, itu tidak akan diukur dengan apapun bilangan prima lainnya kecuali yang semula mengukurnya.

— Euklides, Elemen Buku IX, Proposisi 14

(Dalam terminologi modern: kelipatan persekutuan terkecil dari beberapa bilangan prima bukanlah kelipatan dari bilangan prima lainnya.) Buku IX, proposisi 14 diturunkan dari Buku VII, proposisi 30, dan membuktikan sebagian bahwa dekomposisi itu unik – sebuah poin yang secara kritis dicatat oleh André Weil.^[6] Memang, dalam proposisi ini semua eksponennya sama dengan satu, jadi tidak ada yang dikatakan untuk kasus umum.

Pasal 16 dari Gauss Disquisitiones Arithmeticae adalah pernyataan dan bukti modern awal yang menggunakan aritmetika modular.^[1]

Aplikasi

Representasi kanonik dari bilangan bulat positif

Setiap bilangan bulat positif n > 1 dapat direpresentasikan dengan tepat satu cara sebagai hasil kali pangkat prima:

n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}

dimana p₁ < p₂ < ... < p_k adalah bilangan prima dan n_i adalah bilangan bulat positif. Representasi ini biasanya diperluas ke semua bilangan bulat positif, termasuk 1, dengan konvensi bahwa produk kosong sama dengan 1 (produk kosong sesuai dengan k = 0).

Representasi ini disebut representasi kanonik^[7] dari n, atau bentuk standar^[8]^[9] dari n. Contohnya,

999 = 3³×37,

1000 = 2³×5³,

1001 = 7×11×13.

Faktor p⁰ = 1 dapat dimasukkan tanpa mengubah nilai n (misalnya, 1000 = 2³×3⁰×5³). Faktanya, bilangan bulat positif apa pun dapat direpresentasikan secara unik sebagai produk tak hingga yang diambil dari semua bilangan prima positif:

n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},

dimana sebuah bilangan berhingga dari n_i adalah bilangan bulat positif, dan sisanya nol. Membiarkan eksponen negatif memberikan bentuk kanonik untuk bilangan rasional positif.

Operasi aritmetika

Representasi kanonik dari produk, faktor persekutuan terbesar (GCD) atau (FPB), dan kelipatan persekutuan terkecil (LCM) atau (KPK) dari dua bilangan a dan b dapat dinyatakan secara sederhana dalam bentuk representasi kanonik dari a dan b itu sendiri:

{\begin{alignedat}{2}a\cdot b&=2^{a_{1}+b_{1}}3^{a_{2}+b_{2}}5^{a_{3}+b_{3}}7^{a_{4}+b_{4}}\cdots &&=\prod p_{i}^{a_{i}+b_{i}},\\\gcd(a,b)&=2^{\min(a_{1},b_{1})}3^{\min(a_{2},b_{2})}5^{\min(a_{3},b_{3})}7^{\min(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\min(a_{i},b_{i})},\\\operatorname {lcm} (a,b)&=2^{\max(a_{1},b_{1})}3^{\max(a_{2},b_{2})}5^{\max(a_{3},b_{3})}7^{\max(a_{4},b_{4})}\cdots &&=\prod p_{i}^{\max(a_{i},b_{i})}.\end{alignedat}}

Namun, faktorisasi bilangan bulat, terutama bilangan terbesar, jauh lebih sulit dibanding menghitung produk, FPB, atau KPK. Jadi formula ini memiliki penggunaan yang terbatas dalam praktiknya.

Fungsi aritmetika

Banyak fungsi aritmetika didefinisikan menggunakan representasi kanonik. Secara khusus, nilai fungsi tambahan dan perkalian ditentukan oleh nilainya pada pangkat bilangan prima.

Bukti

Pembuktiannya menggunakan lema Euklides (Elemen VII, 30): Jika suatu prima membagi hasil kali dua bilangan bulat, maka harus membagi setidaknya satu dari bilangan bulat ini.

Eksistensi

It must be shown that every integer greater than $1$ is either prime or a product of primes. First, $2$ is prime. Then, by strong induction, assume this is true for all numbers greater than $1$ and less than $n$ . If $n$ is prime, there is nothing more to prove. Otherwise, there are integers $a$ and $b$ , where $n = a b$ , and $1 < a \leq b < n$ . By the induction hypothesis, $a = p 1 p 2 \cdot\cdot\cdot p j$ and $b = q 1 q 2 \cdot\cdot\cdot q k$ are products of primes. But then $n = a b = p 1 p 2 \cdot\cdot\cdot p j q 1 q 2 \cdot\cdot\cdot q k$ is a product of primes.

Uniqueness

Suppose, to the contrary, there is an integer that has two distinct prime factorizations. Let $n$ be the least such integer and write $n = p 1 p 2 ... p j = q 1 q 2 ... q k$ , where each $p i$ and $q i$ is prime. We see that $p 1$ divides $q 1 q 2 ... q k$ , so $p 1$ divides some $q i$ by Euclid's lemma. Without loss of generality, say $p 1$ divides $q 1$ . Since $p 1$ and $q 1$ are both prime, it follows that $p 1 = q 1$ . Returning to our factorizations of $n$ , we may cancel these two factors to conclude that $p 2 ... p j = q 2 ... q k$ . We now have two distinct prime factorizations of some integer strictly smaller than $n$ , which contradicts the minimality of $n$ .

Uniqueness without Euclid's lemma

The fundamental theorem of arithmetic can also be proved without using Euclid's lemma.^[10] The proof that follows is inspired by Euclid's original version of the Euclidean algorithm.

Assume that $s$ is the smallest positive integer which is the product of prime numbers in two different ways. Incidentally, this implies that $s$ , if it exists, must be a composite number greater than $1$ . Now, say

{\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}

Every $p_{i}$ must be distinct from every $q_{j}.$ Otherwise, if say $p_{i}=q_{j},$ then there would exist some positive integer $t=s/p_{i}=s/q_{j}$ that is smaller than $s$ and has two distinct prime factorizations. One may also suppose that $p_{1}<q_{1},$ by exchanging the two factorizations, if needed.

Setting $P=p_{2}\cdots p_{m}$ and $Q=q_{2}\cdots q_{n},$ one has $s=p_{1}P=q_{1}Q.$ Also, since $p_{1}<q_{1},$ one has $Q<P.$ It then follows that

s-p_{1}Q=(q_{1}-p_{1})Q=p_{1}(P-Q)<s.

As the positive integers less than $s$ have been supposed to have a unique prime factorization, $p_{1}$ must occur in the factorization of either $q_{1}-p_{1}$ or $Q$ . The latter case is impossible, as $Q$ , being smaller than $s$ , must have a unique prime factorization, and $p_{1}$ differs from every $q_{j}.$ The former case is also impossible, as, if $p_{1}$ is a divisor of $q_{1}-p_{1},$ it must be also a divisor of $q_{1},$ which is impossible as $p_{1}$ and $q_{1}$ are distinct primes.

Therefore, there cannot exist a smallest integer with more than a single distinct prime factorization. Every positive integer must either be a prime number itself, which would factor uniquely, or a composite that also factors uniquely into primes, or in the case of the integer $1$ , not factor into any prime.

Generalizations

The first generalization of the theorem is found in Gauss's second monograph (1832) on biquadratic reciprocity. This paper introduced what is now called the ring of Gaussian integers, the set of all complex numbers a + bi where a and b are integers. It is now denoted by $\mathbb {Z} [i].$ He showed that this ring has the four units ±1 and ±i, that the non-zero, non-unit numbers fall into two classes, primes and composites, and that (except for order), the composites have unique factorization as a product of primes.^[11]

Similarly, in 1844 while working on cubic reciprocity, Eisenstein introduced the ring $\mathbb {Z} [\omega ]$ , where $\omega ={\frac {-1+{\sqrt {-3}}}{2}},$ $\omega ^{3}=1$ is a cube root of unity. This is the ring of Eisenstein integers, and he proved it has the six units $\pm 1,\pm \omega ,\pm \omega ^{2}$ and that it has unique factorization.

However, it was also discovered that unique factorization does not always hold. An example is given by $\mathbb {Z} [{\sqrt {-5}}]$ . In this ring one has^[12]

6=2\cdot 3=(1+{\sqrt {-5}})(1-{\sqrt {-5}}).

Examples like this caused the notion of "prime" to be modified. In $\mathbb {Z} [{\sqrt {-5}}]$ it can be proven that if any of the factors above can be represented as a product, for example, 2 = ab, then one of a or b must be a unit. This is the traditional definition of "prime". It can also be proven that none of these factors obeys Euclid's lemma; for example, 2 divides neither (1 + √−5) nor (1 − √−5) even though it divides their product 6. In algebraic number theory 2 is called irreducible in $\mathbb {Z} [{\sqrt {-5}}]$ (only divisible by itself or a unit) but not prime in $\mathbb {Z} [{\sqrt {-5}}]$ (if it divides a product it must divide one of the factors). The mention of $\mathbb {Z} [{\sqrt {-5}}]$ is required because 2 is prime and irreducible in $\mathbb {Z} .$ Using these definitions it can be proven that in any integral domain a prime must be irreducible. Euclid's classical lemma can be rephrased as "in the ring of integers $\mathbb {Z}$ every irreducible is prime". This is also true in $\mathbb {Z} [i]$ and $\mathbb {Z} [\omega ],$ but not in $\mathbb {Z} [{\sqrt {-5}}].$

The rings in which factorization into irreducibles is essentially unique are called unique factorization domains. Important examples are polynomial rings over the integers or over a field, Euclidean domains and principal ideal domains.

In 1843 Kummer introduced the concept of ideal number, which was developed further by Dedekind (1876) into the modern theory of ideals, special subsets of rings. Multiplication is defined for ideals, and the rings in which they have unique factorization are called Dedekind domains.

There is a version of unique factorization for ordinals, though it requires some additional conditions to ensure uniqueness.

Notes

^ ^a ^b (Gauss & Clarke 1986, Art. 16)
^ (Gauss & Clarke 1986, Art. 131)
^ (Long 1972, hlm. 44)
^ (Pettofrezzo & Byrkit 1970, hlm. 53)
^ (Hardy & Wright 2008, Thm 2)
^ (Weil 2007, hlm. 5): "Bahkan dalam Euclid, kita gagal menemukan pernyataan umum tentang keunikan faktorisasi suatu bilangan bulat menjadi bilangan prima; tentunya dia mungkin telah menyadarinya, tetapi yang dia miliki hanyalah sebuah pernyataan (Eukl.IX.I4) tentang l.c.m. dari sejumlah bilangan prima yang diberikan."
^ (Long 1972, hlm. 45)
^ (Pettofrezzo & Byrkit 1970, hlm. 55)
^ (Hardy & Wright 2008, § 1.2)
^ Dawson, John W. (2015), Why Prove it Again? Alternative Proofs in Mathematical Practice., Springer, hlm. 45, ISBN 9783319173689
^ Gauss, BQ, §§ 31–34
^ (Hardy & Wright 2008, § 14.6)

References

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 (1986), Disquisitiones Arithemeticae (Second, corrected edition), diterjemahkan oleh Clarke, Arthur A., New York: Springer, ISBN 978-0-387-96254-2
Gauss, Carl Friedrich (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition) (dalam bahasa Jerman), diterjemahkan oleh Maser, H., 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 (edisi ke-Second Edition Unabridged), New York: Dover, ISBN 978-0-486-60089-5
Hardy, G. H.; Wright, E. M. (2008), An Introduction to the Theory of Numbers, Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (edisi ke-6th), Oxford: Oxford University Press, ISBN 978-0-19-921986-5, MR 2445243, Zbl 1159.11001
A. Kornilowicz; P. Rudnicki (2004), "Fundamental theorem of arithmetic", Formalized Mathematics, 12 (2): 179–185
Long, Calvin T. (1972), Elementary Introduction to Number Theory (edisi ke-2nd), 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
Weil, André (2007) [1984], Number Theory: An Approach through History from Hammurapi to Legendre, Modern Birkhäuser Classics, Boston, MA: Birkhäuser, ISBN 978-0-817-64565-6
Weisstein, Eric W. "Abnormal number". MathWorld.
Weisstein, Eric W. "Fundamental Theorem of Arithmetic". MathWorld.

External links

Why isn’t the fundamental theorem of arithmetic obvious?
GCD and the Fundamental Theorem of Arithmetic at cut-the-knot.
PlanetMath: Proof of fundamental theorem of arithmetic
Fermat's Last Theorem Blog: Unique Factorization, a blog that covers the history of Fermat's Last Theorem from Diophantus of Alexandria to the proof by Andrew Wiles.
"Fundamental Theorem of Arithmetic" by Hector Zenil, Wolfram Demonstrations Project, 2007.
Grime, James, "1 and Prime Numbers", Numberphile, Brady Haran, diarsipkan dari versi asli tanggal 2021-12-11

Templat:Divisor classes

[Gauss1801.loc=16-1] (Gauss & Clarke 1986, Art. 16)

[2] (Gauss & Clarke 1986, Art. 131)

[3] (Long 1972, hlm. 44)

[4] (Pettofrezzo & Byrkit 1970, hlm. 53)

[5] (Hardy & Wright 2008, Thm 2)

[6] (Weil 2007, hlm. 5): "Bahkan dalam Euclid, kita gagal menemukan pernyataan umum tentang keunikan faktorisasi suatu bilangan bulat menjadi bilangan prima; tentunya dia mungkin telah menyadarinya, tetapi yang dia miliki hanyalah sebuah pernyataan (Eukl.IX.I4) tentang l.c.m. dari sejumlah bilangan prima yang diberikan."

[7] (Long 1972, hlm. 45)

[8] (Pettofrezzo & Byrkit 1970, hlm. 55)

[9] (Hardy & Wright 2008, § 1.2)

[10] Dawson, John W. (2015), Why Prove it Again? Alternative Proofs in Mathematical Practice., Springer, hlm. 45, ISBN 9783319173689

[11] Gauss, BQ, §§ 31–34

[12] (Hardy & Wright 2008, § 14.6)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]