Bổ đề Bezout - Vườn Toán

Trang chủ » định Lý Bezout » Bổ đề Bezout - Vườn Toán

Có thể bạn quan tâm

Trang

  • Trang nhà
  • Kỹ năng mềm
  • Giới thiệu

Bổ đề Bezout

Hôm nay chúng ta sẽ học về một kết quả rất hay trong số học, đó là bổ đề Bezout. Bổ đề này phát biểu như sau.
Bổ đề Bezout. Nếu $d$ là ước số chung lớn nhất của hai số nguyên $a$ và $b$ thì sẽ tồn tại hai số nguyên $x$ và $y$ sao cho $$d = a x + b y.$$
Muốn xác định giá trị của hai số $x$ và $y$ trong bổ đề Bezout, chúng ta có thể dùng thuật toán Euclid. Chúng ta sẽ học về thuật toán này vào kỳ sau. Trước tiên, chúng ta xem xét một vài ví dụ.
  • $a = 5$, $b = 7$, ước số chung lớn nhất là $d=1$, chúng ta có thể viết đẳng thức Bezout như sau $${\bf 1} = {\bf 5} \times 3 + {\bf 7} \times (-2).$$
  • $a = 16$, $b = 30$, ước số chung lớn nhất là $d=2$, $${\bf 2} = {\bf 16} \times 2 + {\bf 30} \times (-1).$$
  • $a = 45$, $b = 155$, ước số chung lớn nhất là $d=5$, $${\bf 5} = {\bf 45} \times 7 + {\bf 155} \times (-2).$$
Chứng minh Bổ đề Bezout
Nếu $d$ là ước số chung lớn nhất của hai số nguyên $a$ và $b$ thì sẽ tồn tại hai số nguyên $x$ và $y$ sao cho $$d = a x + b y.$$
Đầu tiên chúng ta nhận xét rằng nếu $a=0$ thì $d=b$, cho nên bổ đề Bezout hiển nhiên đúng. Chúng ta chỉ cần chứng minh cho trường hợp $a \neq 0$ và $b \neq 0$. Gọi $S$ là tập hợp tất cả các số nguyên có dạng $ax+by$ $$S = \{ ax + by : x \in Z, ~y \in Z \}.$$ Chúng ta có những nhận xét sau đây. Nhận xét 1. Các số $0$, $a$, $b$ thuộc tập hợp $S$. Từ nhận xét 1, chúng ta thấy tập hợp $S$ có chứa các số khác $0$. Vì vậy, trong tập hợp $S$, chúng ta có thể chọn ra một phần tử $s \neq 0$ sao cho $|s|$ có giá trị bé nhất. Vì $s$ là một phần tử của tập hợp $S$, cho nên chúng ta có thể viết $s$ dưới dạng $$s = a ~x_s + b ~y_s.$$ Nhận xét 2. $s$ là ước số của bất kỳ số nào nằm trong tập hợp $S$. Thật vậy, nếu chúng ta lấy bất kỳ một phần tử $u = a x_u + b y_u$ của tập hợp $S$, chúng ta chia nó cho $s$ sẽ có thương là $q$ và số dư là $r$. Chúng ta sẽ chứng minh rằng $r=0$. Số dư $r$ thoã mãn điều kiện $$0 \leq |r| < |s|.$$ Chúng ta sẽ có $$u = sq + r,$$ do đó $$r = u - sq = (a x_u + b y_u) - (a x_s + b y_s)q = (x_u - x_s q)a + (y_u - y_s q)b.$$ Từ đó suy ra $r$ là một phần tử của tập hợp $S$. Nhưng mà $0 \leq |r| < |s|$, trong khi đó $s$ là một phần tử khác không của tập hợp $S$ có giá trị tuyệt đối bé nhất. Từ đó suy ra $r=0$, tức là $u$ chia hết cho $s$. Như vậy chúng ta đã chứng minh xong Nhận xét 2 rằng $s$ là ước số của bất kỳ số nào nằm trong tập hợp $S$. Nhận xét 3. $s$ là ước số của $d$. Thật vậy, theo nhận xét 2, $s$ là ước số của bất kỳ số nào nằm trong tập hợp $S$, mà $a$ và $b$ nằm trong tập hợp $S$, do đó $s$ là ước số của $a$ và $b$. Trong khi đó $d$ là ước số lớn nhất của $a$ và $b$, cho nên $s$ phải là ước số của $d$. Nhận xét 4. $d$ là ước số của $s$. Thật vậy, vì $d$ là ước số của $a$ và $b$ cho nên $d$ là ước số của bất kỳ số nào có dạng $a x + b y$. Mà $s$ có dạng $ax + by$, do đó, $d$ là ước số của $s$. Từ hai nhận xét cuối cùng, chúng ta suy ra $d = \pm s$, và vì vậy $d$ có dạng $a x + b y$, và bổ đề Bezout đã được chứng minh. Ứng dụng của bổ đề Bezout Bài toán. Tìm tất cả các số nguyên $a$ và $b$ sao cho $5~a + 7~b = 1$ Lời giải. Chúng ta thấy rằng phương trình $5~a + 7~b = 1$ có dạng như phương trình Bezout cho hai số $5$ và $7$. Vì $5$ và $7$ có ước số chung lớn nhất là $1$ cho nên theo bổ đề Bezout sẽ tồn tại $x$ và $y$ để cho $$1 = 5 ~x + 7 ~y$$ Thử một vài số, chúng ta thấy $x=3$, $y=-2$ thõa mãn. Do đó $$1 = 5 \times 3 + 7 \times (-2)$$ Trừ hai vế cho phương trình $5~a + 7~b = 1$, chúng ta có $$5(a-3) + 7 (b+2) = 0$$ Tức là $$7(b+2) = 5(3-a)$$ Do đó $7(b+2)$ chia hết cho $5$. Suy ra $b+2$ chia hết cho $5$. Đặt $$b+2 = 5s,$$ chúng ta có $$b = 5s -2$$ và $$5(3-a) = 7(b+2) = 35s$$ Từ đó suy ra $$3-a = 7s$$ và $$a = 3-7s$$ Tóm lại chúng ta có nghiệm là $a = 3-7s$, $b=5s-2$. Bài toán. Có hai cái bình dạng 500 mili lít và 700 mili lít. Hãy chỉ cách dùng hai cái bình này để đong ra đúng 100 mili lít nước. Lời giải. Thực ra bài toán này có ý tưởng như bài toán ở trên. Chúng ta có $$1 = 5 \times 3 - 7 \times 2.$$ Do đó chỉ cần đong ba lần bình 500 ml trừ đi hai lần bình 700 ml chúng ta sẽ có chính xác 100 ml. Lời giải ở hình vẽ sau đây.
Lấy được 100ml bằng cách đong ba lần bình 500ml và làm đầy hai lần bình 700ml
Chúng ta tạm dừng ở đây. Kỳ sau chúng ta tiếp tục học về bổ đề Bezout và thuật toán Euclid. Hẹn gặp lại các bạn. Bài tập về nhà. 1. Cho hai số nguyên $a$ và $b$ nguyên tố cùng nhau. Chứng minh rằng tồn tại số nguyên $c$ sao cho $$ac = 1 \pmod{b}.$$ Số $c$ được gọi là nghịch đảo của số $a$ trong modulo $b$. 2. Tìm tất cả các số tự nhiên $n$ sao cho $1000 n - 1$ chia hết cho $2013$. 3. Cho ba số nguyên $a$, $b$, và $c$. Gọi $d$ là ước số chung lớn nhất của $a$, $b$, $c$. Chứng minh rằng tồn tại ba số nguyên $x$, $y$, $z$ sao cho $$d= a ~x + b ~y + c ~z .$$ Labels: algebra, Bézout, đại số, Euclidean algorithm, gcd, modulo, number theory, phương trình nghiệm nguyên, số học, ước số Bài đăng Mới hơn Bài đăng Cũ hơn Trang chủ

Ủng hộ Vườn Toán trên facebook

Facebook

Lưu trữ Blog

  • ▼  2012 (36)
    • ▼  tháng 11 (7)
      • Tổng luỹ thừa và định lý Wolstenholme
      • Tổng luỹ thừa
      • Thuật toán Euclid
      • Bổ đề Bezout
      • Chứng minh lại định lý Wilson
      • Modulo cho số hữu tỷ II
      • Modulo cho số hữu tỷ

English Version

English Version

Bài toán kết nối facebook

Phép nhân thời đồ đá

Mắt Biếc Hồ Thu

Lục giác kỳ diệu

Định lý Pitago

1 = 2012 = 2013

Dãy số Fibonacci và một bài toán xếp hình

James vẽ hình

Câu hỏi của James

Hình vuông số chính phương kỳ diệu của Vianney!

Câu đố mẹo về đo lường

Công thức lượng giác Gauss cho 17-giác đều

Chào năm mới 2014

Chào năm mới 2015

Chào năm mới 2016

Không gian 4 chiều là gì?

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Ngày số Pi (2015)

Ngày số Pi (2016)

0.9999999... có bằng 1 không? (2015)

Hình tam giác

Bàn cờ vua và kim tự tháp

Dãy số

Dãy số - Phần 1

Dãy số - Phần 2

Dãy số - Phần 3

Dãy số - Phần 4

Dãy số - Phần 5

Dãy số - Phần 6

Dãy số - Phần 7

Dãy số - Phần 8

Dãy số - Phần 9

Đại số

Tam giác Pascal

Quy nạp

Quy nạp II

Quy nạp III

Nhị thức Newton

1 = 2012 = 2013

Đa thức nội suy Newton

Đa thức nội suy Lagrange

Chứng minh Định lý Wilson bằng công thức nội suy

Tổng luỹ thừa

Số phức

Số phức

Công thức Moivre

Lượng giác

Công thức lượng giác cho góc bội

Công thức lượng giác Gauss cho 17-giác đều

Ngày số Pi (2016)

Radian là gì?

Số học

modulo - Phần 1

modulo - Phần 2

modulo - Phần 3

modulo - Phần 4

modulo - Phần 5

modulo - Phần 6

Số nguyên tố

Định lý Euclid về số nguyên tố

Một vài bài toán về số nguyên tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo cho số hữu tỷ II

Chứng minh lại định lý Wilson

Bổ đề Bezout

Thuật toán Euclid

Tổng luỹ thừa

Tổng luỹ thừa và định lý Wolstenholme

Câu đố mẹo về đo lường

Dựng đa giác đều 15 cạnh

Bò đi con bọ cạp!

Liên phân số Fibonacci

Hằng đẳng thức Pitago

Hình vuông số kỳ diệu của Euler

Tổ hợp

Bài toán kết nối facebook

Dãy số Fibonacci và một bài toán xếp hình

Hằng đẳng thức về dãy số Fibonacci

Dãy số Fibonacci và tam giác Pascal

Hình học

Định lý Pitago

Định lý đường cao tam giác vuông

Định lý Morley

Phương tích

Trục đẳng phương và tâm đẳng phương

Định lý Ceva và Định lý Menelaus

Lục giác kỳ diệu

Định lý Pascal

Định lý Pappus

Cánh bướm Pascal

Bài toán con bướm

Định lý Ngôi Sao Do Thái

Hãy xem xét trường hợp đặc biệt

Bài toán về tìm khoảng cách ngắn nhất và một tính chất của hình elíp

Điểm Fermat của hình tam giác

Điểm Fermat của hình tam giác II

Dựng hình

Dựng hình bằng thước và compa

Bài toán chia hình tứ giác

Dựng hình ngũ giác đều

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Định lý đường cao tam giác vuông

Thuật toán dựng hình

Công thức lượng giác Gauss cho 17-giác đều

Dựng hình chỉ bằng compa

Dùng compa chia đều đoạn thẳng

Giải tích

Ngày số Pi 2015

Chuỗi Taylor

Tổng nghịch đảo bình phương

Giúp bé thông minh

Xì-tin năng động

BBC - Học tiếng Anh Du học Hoa kỳ Học Bổng Hoa Kỳ VOA - Học tiếng Anh

Tạp chí toán học

Kỹ năng mềm

Tạo lập tài khoản google

Cách tạo blog toán học

Học toán trên Wolfram

Dịch tài liệu toán học

Viết văn bản toán học PDF trực tuyến bằng LaTeX

Chia xẻ tài liệu toán học trên Google Drive

Từ khóa » định Lý Bezout