Lemma Euklidean

Dalam teori bilangan, Lemma Euklidean adalah lemma yang menangkap properti dasar bilangan prima, yaitu:^{[note 1]}

Lemma Euklidean — Jika bilangan prima $p$ membagi produk $ab$ dari dua bilangan bulat $a$ dan $b$ , maka $p$ harus membagi setidaknya satu dari bilangan bulat tersebut $a$ dan $b$ .

Misalnya, jika $p = 19$ , $a = 133$ , $b = 143$ , then $ab = 133 \times 143 = 19019$ , dan karena ini habis dibagi 19, lemma menyiratkan bahwa satu atau keduanya dari 133 atau 143 pasti juga. Faktanya, $133 = 19 \times 7$ .

Secara inheren, jika premis lemma tidak berlaku, yaitu, $p$ adalah bilangan komposit, konsekuensinya bisa benar atau salah. Contohnya, dalam kasus $p = 10$ , $a = 4$ , $b = 15$ , bilangan komposit 10 membagi $ab = 4 \times 15 = 60$ , tapi 10 tidak membagi 4 atau 15.

Properti ini adalah kunci dalam pembuktian teorema fundamental aritmetika.^{[note 2]} Ini digunakan untuk mendefinisikan elemen utama s, generalisasi dari bilangan prima ke sembarang cincin komutatif. Lemma Euclid menunjukkan bahwa dalam bilangan bulat elemen tak tereduksi juga merupakan elemen prima. Pembuktiannya menggunakan induksi sehingga tidak berlaku untuk semua integral domain.

Formulasi

Jika $p$ menjadikan bilangan prima dan asumsi $p$ jadi membagi hasil kali dua bilangan bulat $a$ dan $b$ . (Dalam simbol ini tertulis $p\mid ab$ . Negasinya, $p$ tidak membagi $ab$ ditulis $p\nmid ab$ .) Kemudian $p\mid a$ atau $p\mid b$ (atau keduanya). Pernyataan Setara adalah:

Bila $p\nmid a$ dan $p\nmid b$ , kemudian $p\nmid ab$ .
Bila $p\nmid a$ dan $p\mid ab$ , kemudian $p\mid b$ .

Lemma Euklidean dapat digeneralisasikan dari bilangan prima ke bilangan bulat apa pun:

Teorema — If $n\mid ab$ , dan $n$ adalah relatif prima menjadi $a$ $n\mid b$ .

Ini adalah generalisasi karena jika $n$ adalah bilangan prima

$n\mid a$ atau
$n$ relatif prima dari $a$ .

Dalam kemungkinan kedua ini, $n\nmid a$ jadi $n\mid b$ .

Sejarah

Lemma pertama kali muncul sebagai proposisi 30 dalam Buku VII dari Elemen Euklides. Ini termasuk dalam hampir setiap buku yang mencakup teori bilangan dasar.^[4]^[5]^[6]^[7]^[8]

Generalisasi lemma ke bilangan bulat muncul di buku teks Jean Prestet Nouveaux Elémens de Mathématiques pada tahun 1681.^[9]

Dalam risalah Carl Friedrich Gauss Disquisitiones Arithmeticae , pernyataan lemma adalah Euclid's Proposition 14 (Bagian 2), yang ia gunakan untuk membuktikan keunikan dekompositio, mengakui keberadaannya sebagai "jelas." Dari keberadaan dan keunikan ini ia kemudian menyimpulkan generalisasi bilangan prima menjadi bilangan bulat.^[10] Untuk alasan ini, generalisasi lemma Euklid kadang-kadang disebut sebagai lemma Gauss, tetapi beberapa percaya penggunaan ini salah.^[11] karena kebingungan dengan Lemma Gauss pada residu kuadrat.

Bukti menggunakan Lemma Bézout

Pembuktian biasanya melibatkan lemma lain yang disebut identitas Bézout.^[12] This states that if $x$ dan $y$ adalah bilangan bulat prima relatif (yaitu mereka tidak berbagi pembagi umum selain 1 dan -1) ada bilangan bulat $r$ dan $s$ seperti yang

rx+sy=1.

Maka $a$ dan $n$ menjadi relatif prima, dan asumsikan bahwa $n | ab$ . Dengan identitas Bézout, ada $r$ dan $s$ penyusunan

rn+sa=1.

Kalikan kedua sisi dengan $b$ :

rnb+sab=b.

Suku pertama di kiri habis dibagi $n$ , dan suku kedua habis dibagi $ab$ , yang dengan hipotesis habis dibagi $n$ . Oleh karena itu jumlah mereka, $b$ , juga habis dibagi $n$ . Ini adalah generalisasi dari lemma Euklid yang disebutkan di atas.

Lihat pula

Catatan Kaki

Catatan

^ It is also called Euclid's first theorem^[1]^[2] meskipun nama itu lebih tepat termasuk dalam kondisi sisi-sudut-sisi untuk menunjukkan bahwa segitiga adalah kongruen.^[3]
^ Secara umum, untuk menunjukkan bahwa domain adalah domain faktorisasi unik, itu cukup untuk membuktikan lemma Euclid dan kondisi rantai naik pada cita-cita prinsipal (ACCP)

Kutipan

^ Bajnok 2013, Theorem 14.5
^ Joyner, Kreminski & Turisco 2004, Proposition 1.5.8, p. 25
^ Martin 2012, hlm. 125
^ Gauss 2001, hlm. 14
^ Hardy, Wright & Wiles 2008, Theorem 3
^ Ireland & Rosen 2010, Proposition 1.1.1
^ Landau & Goodman 1999, Theorem 15
^ Riesel 1994, Theorem A2.1
^ Euclid 1994, hlm. 338–339
^ Gauss 2001, Article 19
^ Weisstein, Eric W. "Euclid's Lemma". MathWorld.
^ Hardy, Wright & Wiles 2008, §2.10

Pranala luar

(Inggris) Weisstein, Eric W. "Euclid's Lemma". MathWorld.

[4] It is also called Euclid's first theorem^[1]^[2] meskipun nama itu lebih tepat termasuk dalam kondisi sisi-sudut-sisi untuk menunjukkan bahwa segitiga adalah kongruen.^[3]

[5] Secara umum, untuk menunjukkan bahwa domain adalah domain faktorisasi unik, itu cukup untuk membuktikan lemma Euclid dan kondisi rantai naik pada cita-cita prinsipal (ACCP)

[1] Bajnok 2013, Theorem 14.5

[2] Joyner, Kreminski & Turisco 2004, Proposition 1.5.8, p. 25

[3] Martin 2012, hlm. 125

[DA1-6] Gauss 2001, hlm. 14

[7] Hardy, Wright & Wiles 2008, Theorem 3

[8] Ireland & Rosen 2010, Proposition 1.1.1

[9] Landau & Goodman 1999, Theorem 15

[10] Riesel 1994, Theorem A2.1

[11] Euclid 1994, hlm. 338–339

[DA2-12] Gauss 2001, Article 19

[13] Weisstein, Eric W. "Euclid's Lemma". MathWorld.

[14] Hardy, Wright & Wiles 2008, §2.10

[note 1]

[note 2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[1]

[2]

[3]