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: $ \displaystyle d\text{ }=\text{ }a\text{ }x\text{ } \text{ }b\text{ }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
1=5×3 7×(−2).
a=16, b=30, ước số chung lớn nhất là d=2,
2=16×2 30×(−1).
a=45, b=155, ước số chung lớn nhất là d=5,
5=45×7 155×(−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=ax by.
Đầ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≠0 và b≠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∈Z, y∈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≠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=axs + bys.
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=axu byu 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≤|r|<|s|.
Chúng ta sẽ có u=sq+r,
do đó
r=u−sq=(axu byu)−(axs bys)q=(xu−xsq)a (yu−ysq)b.
Từ đó suy ra r là một phần tử của tập hợp S. Nhưng mà 0≤|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 ax by. 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=±s, và vì vậy d có dạng ax+by, và bổ đề Bezout đã được chứng minh.
Ứng dụng của bổ đề Bezout
Bài toán 1. Tìm tất cả các số nguyên a và b sao cho 5a 7b=1
Lời giải. Chúng ta thấy rằng phương trình 5a 7b=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=5x 7y
Thử một vài số, chúng ta thấy x=3, y=−2 thõa mãn. Do đó
1=5×3 7×(−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 2. 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×3−7×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.
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(modb). Số c được gọi là nghịch đảo của số a trong modul b.
2. Tìm tất cả các số tự nhiên n sao cho 1000n−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=ax+by+cz.
(Theo Vuontoanblog)
Tin tức - Tags: Bezout, bộ đề, bổ đề Bezout, Euclid, thuật toán EuclidCâu đố mẹo về đo lường
Một số bài cảm thụ văn học tham khảo lớp 3 có giải
Chia sẻ bộ tài liệu trắc nghiệm Vật lý lớp 10, 11, 12
Cách chia đơn thức cho đơn thức, đa thức cho đơn thức, đa thức cho một biến
Có nên cho trẻ học sách công nghệ giáo dục?
5 cách để trẻ yêu thích và học tốt môn tiếng Việt
Một số dạng Toán thực tế cấp THCS