Xem mã nguồn của Bổ đề Euclid

{{short description|Một số nguyên tố chia hết một tích thì chia hết cho một trong các thừa số}}
{{Distinguish|Bổ đề phép chia Euclid|Định lý Euclid|Giải thuật Euclid}}

Trong [[lý thuyết số]], '''bổ đề Euclid''' là một [[bổ đề]] nắm một thuộc tính cơ bản của [[số nguyên tố]], đó là:{{Refn|Nó còn được gọi là '''Định lý đầu tiên của Euclid'''<ref>{{Harvnb|Bajnok|2013|loc=Theorem 14.5}}</ref><ref>{{Harvnb|Joyner|Kreminski|Turisco|2004|loc=Proposition 1.5.8, p.&nbsp;25}}</ref> mặc dù tên gọi đó phù hợp hơn với định lý về [[Giải tam giác|điều kiện cạnh-góc-cạnh]] dùng để chứng minh các [[tam giác]] là [[đồng dạng]].<ref>{{Harvnb|Martin|2012|p=125}}</ref>|group=note}}<blockquote>'''Bổ đề Euclid''' — Nếu một số nguyên tố {{math|''p''}} là ước của tích {{math|''ab''}} của hai số nguyên {{math|''a''}} và {{math|''b''}}, thì {{math|''p''}} phải chia được hết bởi tối thiểu một trong các số nguyên {{math|''a''}} và {{math|''b''}}.</blockquote>Ví dụ, nếu {{Math|''p'' {{=}} 19}}, {{Math|''a'' {{=}} 133}}, {{Math|''b'' {{=}} 143}}, thì {{Math|''ab'' {{=}} 133 &times; 143 {{=}} 19019}}, và vì tích này chia hết cho 19, theo bổ đề thì một trong hai hoặc cả hai số 133 hoặc 143 cũng phải chia hết cho 19. Thật vậy, {{Math|133 {{=}} 19 × 7}}.

Vốn dĩ, nếu điều kiện của bổ đề không được thỏa mãn, chẳng hạn như nếu {{math|''p''}} là một [[hợp số]], kết quả sẽ có thể là đúng hoặc sai. Ví dụ, trong trường hợp {{math|''p'' {{=}} 10}}, {{math|''a'' {{=}} 4}}, {{math|''b'' {{=}} 15}}, hợp số 10 chia hết tích {{math|''ab'' {{=}} 4 &times; 15 {{=}} 60}}, nhưng 10 không chia hết 4 hay 15.

Tính chất này cần thiết cho chứng minh của [[định lý cơ bản của số học]].{{refn|Tổng quát, việc chỉ ra rằng một [[miền nguyên|miền]] là một [[miền phân tích duy nhất]], là đủ để chứng minh bổ đề Euclid và [[điều kiện chuỗi tăng dần của các iđêan chính]] (ACCP)|group=note}} Nó được dùng để định nghĩa [[phần tử nguyên tố]], một tổng quát hóa của số nguyên tố cho các [[vành giao hoán]] bất kỳ. Bổ đề Euclid cho thấy rằng đối với tập số nguyên các [[phần tử tối giản]] cũng là phần tử nguyên tố. Chứng minh định lý sử dụng [[Quy nạp toán học|quy nạp]] nên nó không áp dụng với tất cả các miền nguyên.

== Công thức ==
Lấy <math>p</math> là một [[số nguyên tố]] và giả thiết rằng <math>p</math> chia hết (hay "đo được") tích của hai số nguyên <math>a</math> và <math>b</math>. (Trong cách viết ký hiệu, điều này được viết là <math>p \mid ab</math>. Mệnh đề phủ định của nó, <math>p</math> không chia hết <math>ab</math> được viết là <math>p \nmid ab</math>.) Vậy thì <math>p \mid a</math> hoặc <math>p \mid b</math> (hoặc cả hai). Các phát biểu [[Tương đương logic|tương đương]] bao gồm:

* Nếu <math>p \nmid a</math> và <math>p \nmid b</math>, thì <math>p \nmid ab</math>.
* Nếu <math>p \nmid a</math> và <math>p \mid ab</math>, thì <math>p \mid b</math>.

Bổ đề Euclid có thể được tổng quát hóa từ cho các số nguyên tố tới cho bất kỳ số nguyên nào:<blockquote>'''Định lý''' — Nếu <math>n \mid ab</math>, và <math>n</math> nguyên tố cùng nhau với <math>a</math>, thì <math>n \mid b</math>.</blockquote>Đây là một tổng quát hóa bởi vì nếu <math>n</math> cũng là số nguyên tố thì hoặc là

* <math>n \mid a</math>; hoặc là
* <math>n</math> nguyên tố cùng nhau với <math>a</math>. Trong khả năng thứ hai này, <math>n \nmid a</math> vì vậy <math>n \mid b</math>.

== Lịch sử ==
Bổ đề xuất hiện lần đầu dưới dạng mệnh đề số 30 trong Quyển VII của bộ ''[[Cơ sở (Euclid)|Cơ sở]]'' của [[Euclid]]. Nó được kèm trong trên thực tế tất cả cuốn sách viết về lý thuyết số cơ bản.<ref name="DA2">{{Harvard citation no brackets|Gauss|2001}}</ref><ref name="Hardy 2008">{{Harvard citation no brackets|Hardy|Wright|Wiles|2008}}</ref><ref>{{Harvard citation no brackets|Ireland|Rosen|2010}}</ref><ref>{{Harvard citation no brackets|Landau|Goodman|1999}}</ref><ref>{{Harvard citation no brackets|Riesel|1994}}</ref>

Sự tổng quát hóa của bổ đề lên với mọi số nguyên xuất hiện trong sách giáo khoa ''Nouveaux Elémens de Mathématiques của'' [[Jean Prestet]] năm 1681.<ref>{{Harvard citation no brackets|Euclid|1994}}</ref>

Trong chuyên luận ''[[Disquisitiones Arithmeticae|Disquisitiones Arithmeticae của]]'' [[Carl Friedrich Gauß|Carl Friedrich Gauss]], phát biểu của bổ đề là Định đề 14 của Euclid (Mục 2), mà ông sử dụng để chứng minh sự duy nhất của phân tích các thừa số nguyên tố của một số nguyên (Định lý 16), thừa nhận sự tồn tại là "hiển nhiên." Từ sự tồn tại và tính duy nhất này, sau đó, ông suy ra tổng quát hóa của bổ đề từ số nguyên tố thành số nguyên.<ref name="DA2"/> Vì lý do này, tổng quát hóa của bổ đề Euclid đôi khi còn được gọi là bổ đề Gauss, nhưng một số người tin rằng cách sử dụng này là không chính xác do sự nhầm lẫn<ref>{{mathworld|title=Euclid's Lemma|id=EuclidsLemma}}</ref> với [[Bổ đề Gauss (lý thuyết số)|bổ đề Gauss về thặng dư bậc hai]].

== Chứng minh ==

=== Chứng minh bằng bổ đề Bézout ===
Chứng minh thông thường liên quan tới một bổ đề khác được gọi là [[bổ đề Bézout]],<ref name="Hardy 2008"/> phát biểu rằng nếu {{Math|''x''}} và {{Math|''y''}} là [[Số nguyên tố cùng nhau|các số nguyên tố cùng nhau]] (tức là chúng không có ước số chung nào khác ngoài 1 và -1) thì tồn tại các số nguyên {{Math|''r''}} và {{Math|''s''}} sao cho

: <math>
rx+sy = 1.
</math>

Cho {{Math|''a''}} và {{Math|''n''}} nguyên tố cùng nhau, và giả thiết rằng {{Math|''n''&#124;''ab''}}. Theo bổ đề Bézout, tồn tại {{Math|''r''}} và {{Math|''s''}} thỏa

: <math>
rn+sa = 1.
</math>

Nhân cả hai vế với {{Math|''b''}}:

: <math>
rnb+sab = b.
</math>

Số hạng đầu tiên ở vế trái chia hết cho {{Math|''n''}} và số hạng thứ hai chia hết cho {{Math|''ab''}}, theo giả thiết thì số hạng này chia hết cho {{Math|''n''}}. Do đó tổng của chúng, {{Math|''b''}}, cũng chia hết cho {{Math|''n''}}. Đây là tổng quát hóa của bổ đề Euclid đã đề cập ở trên.

=== Chứng minh của bộ ''Cơ sở'' ===
Bổ đề Euclid được chứng minh ở Mệnh đề 30 trong Quyển VII của bộ sách ''[[Cơ sở (Euclid)|Cơ sở]]'' của [[Euclid]]. Chứng minh gốc khá khó để hiểu được, vì thế chúng tôi trích dẫn lời bình của {{Harvtxt|Euclid|1956|pp=319-332}}.

; Mệnh đề 19
: Nếu bốn số tỉ lệ thuận với nhau thì tích số bởi số thứ nhất và thứ tư bằng số thứ hai và thứ ba; và, nếu tích số từ số thứ nhất và thứ tư bằng tích số từ số thứ hai và thứ ba, thì bốn số đó là tỷ lệ thuận.{{Refn|Nếu ''a'' ：''b''＝''c'' ：''d'', thì ''ad''＝''bc''; và ngược lại.<ref>{{Harvnb|Euclid|1956|p=319}}</ref>|group=note}}
; Mệnh đề 20
: Các số bé nhất trong số những số có cùng tỉ lệ với chúng đo được những số có cùng tỉ lệ bằng cùng một số lần — càng lớn thì càng lớn và càng ít thì càng ít. {{Refn|Nếu ''a'' ：''b''＝''c'' ：''d'', và ''a'', ''b'' là các số bé nhất trong các số có cùng tỉ lệ, thì ''c''＝''na'', ''d''＝''nb'', với ''n'' là một số nguyên nào đó.<ref>{{Harvnb|Euclid|1956|p=321}}</ref>|group=note}}
; Mệnh đề 21
: Các số nguyên tố cùng nhau là các số nhỏ nhất trong số những số có cùng tỉ lệ với chúng.{{Refn|Nếu ''a'' ：''b''＝''c'' ：''d'', và ''a'', ''b'' nguyên tố cùng nhau, thì ''a'', ''b'' là các số bé nhất trong các số có cùng tỉ lệ.<ref>{{Harvnb|Euclid|1956|p=323}}</ref>|group=note}}
; Mệnh đề 29
: Bất kỳ số nguyên tố nào cũng là số nguyên tố cùng với một số bất kỳ mà nó không đo được.{{Refn|Nếu ''a'' là một số nguyên tố và không đo được ''b'' thì ''a'', ''b'' nguyên tố cùng nhau.<ref>{{Harvnb|Euclid|1956|p=331}}</ref>|group=note}}
; Mệnh đề 30
: Nếu hai số, bằng cách nhân với nhau, tạo ra một tích và với bất kỳ số nguyên tố nào đo được tích đó, thì nó cũng đo được một trong các số ban đầu.{{Refn|Nếu ''c'', một số nguyên tố, đo được ''ab'' thì ''c'' cũng đo được một trong hai số ''a'' hoặc ''b'' hoặc cả hai.<ref>{{Harvnb|Euclid|1956|p=332}}</ref>|group=note}}
; Chứng minh của mệnh đề 30
: Nếu ''c'' là số nguyên tố, đo được ''ab'', thì ''c'' đo được ''a'' hoặc ''b''.<br />Giả sử ''c'' không đo được ''a''.<br />Do đó ''c'', ''a'' nguyên tố cùng nhau. <span style="float: right;">［VII. 29］</span><br />Giả sử <span style="text-align: center;">''ab''＝''mc''.</span><br />Do đó <span style="text-align: center;">''c'': ''a'' ＝ ''b'' <span style="text-align: center;">:</span> ''m''.</span> <span style="float: right;">［VII. 19］</span><br />Do đó theo［VII. 20, 21］''b''＝''nc'', với ''n'' là một số nguyên.<br />Do đó <span style="text-align: center;">''c'' đo được ''b''.</span><br />Tương tự, nếu ''c'' không đo được ''b'' thì ''c'' đo được ''a''.<br />Do đó ''c'' là số đo được một số hoặc số kia trong hai số ''a'', ''b''.<br />QED.<ref>{{Harvard citation no brackets|Euclid|1956}}</ref>

== Xem thêm ==
{{Div col}}
*[[Bổ đề Bézout]]
*[[Thuật toán Euclide]]
*[[Định lý cơ bản của số học]]
*[[Phần tử tối giản]]
*[[Phần tử nguyên tố]]
*[[Số nguyên tố]]
{{Div col end}}

== Chú thích ==

=== Ghi chú ===
{{Tham khảo|group=note}}

=== Trích dẫn ===
{{Tham khảo|30em}}

== Tham khảo ==

* {{Chú thích|title=An Invitation to Abstract Mathematics|year=2013|isbn=978-1-4614-6636-9}}.
* {{Chú thích|year=1956|title=The Thirteen Books of the Elements|isbn=978-0-486-60089-5}}- [https://books.google.com/books?id=lxkPAAAAIAAJ vol. 2]
* {{Chú thích|year=1994|title=Les Éléments, traduction, commentaires et notes|language=fr|isbn=2-13-045568-9}}
* {{Chú thích|title=[[Disquisitiones Arithmeticae]]|isbn=978-0-300-09473-2}}
* {{Chú thích|title=Untersuchungen uber hohere Arithmetik|isbn=978-0-8284-0191-3}}
* {{Chú thích|title=An Introduction to the Theory of Numbers|isbn=978-0-19-921986-5}}
* {{Chú thích|title=A Classical Introduction to Modern Number Theory|isbn=978-1-4419-3094-1}}
* {{Chú thích|title=Applied Abstract Algebra|year=2004|isbn=978-0-8018-7822-0}}.
* {{Chú thích|title=Elementary Number Theory|isbn=978-0-821-82004-9}}
* {{Chú thích|title=The Foundations of Geometry and the Non-Euclidean Plane|year=2012|isbn=978-1-4612-5725-7}}.
* {{Chú thích|title=Prime Numbers and Computer Methods for Factorization|isbn=978-0-8176-3743-9}}.

== Liên kết ngoài ==
* {{MathWorld|title=Euclid's Lemma|id=EuclidsLemma}}

[[Thể loại:Bổ đề]]