Chuẩn euclid

Bài viết này trích từ bài giảng "Lý thuyết số từ cổ điển đến hiện đại" ở Viện nghiên cứu cao cấp về toán, hè 2015. Nội dung của bài viết tập trung vào khái niệm chuẩn Euclid trong vành số nguyên, vành số nguyên Gauss và các hệ quả số học của nó. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Chuẩn euclid CHUẨN EUCLID Ngô Bảo Châu (Viện nghiên cứu cao cấp về toán - VIASM) Bài viết này trích từ bài giảng Lý thuyết số từ cổ điển đến hiện đại ở Viện nghiên cứu cao cấp về toán, hè 2015. Nội dung của bài viết tập trung vào khái niệm chuẩn Euclid trong vành số nguyên, vành số nguyên Gauss và các hệ quả số học của nó.1. Nguyên lý trật tự của tập các số tự nhiênĐối tượng nghiên cứu của lý thuyết số về cơ bản là tập các số tự nhiên N D f0; 1; 2; : : :g. Vì cácsố tự nhiên dường như quá quen thuộc, chúng ta ít có ý thức rằng bản thân các số tự nhiên cũngcần được định nghĩa, được xây dựng, một cách chặt chẽ. Xây dựng các số tự nhiên một cách chặtchẽ là một vấn đề trung tâm hóc búa của cơ sở toán học. Ở đây ta sẽ không đề cập đến vấn đềnày một cách có hệ thống mà chỉ điểm lại một số tính chất của tập các số tự nhiên mà ta sẽ côngnhận như những tiên đề.Tập số tự nhiên N chứa ít nhất hai phần tử 0 và 1. Tập này được trang bị phép cộng .x; y/ 7! xCy.Quan hệ thứ tự x < y, cho bởi x < y khi và chỉ khi tồn tại z 2 N với z ¤ 0 sao cho x C z D y,là một quan hệ thứ tự tuyến tính theo nghĩa với mọi x ¤ y, hoặc x < y hoặc y < x. Tập N,với quan hệ thứ tự tuyến tính, thoả mãn nguyên lý trật tự (well-ordering principle): mọi tập conkhông rỗng S N đều chứa một phần tử cực tiểu i.e. tồn tại a 2 S sao cho a x với mọix 2 S. Nguyên lý trật tự thực chất là một phiên bản của nguyên lý quy nạp quen thuộc.2. Ước chung lớn nhấtPhép chia có dư của Euclid là một phép toán cơ bản của số học. Sự tồn tại của phép toán này dựavào khẳng định: cho a; b là hai số nguyên với b ¤ 0, khi đó tồn tại duy nhất q; r 2 Z với a D bq C rI (2.1)sao cho r thoả mãn 0 r < jbj.Để chứng minh khẳng định này, ta xét tập S tất các số tự nhiên x 2 N sao cho x a mod b(ta theo quy ước 0 là số tự nhiên). Tập S chứa a cho nên nó là tập không rỗng. Theo nguyên lýtrật tự, S chứa một phần tử cực tiểu mà ta sẽ ký hiệu là r. Ta sẽ chứng minh r < jbj bằng phảnchứng. Thật vậy, nếu r jbj thì r jbj sẽ là một phần tử của S, nhỏ hơn hẳn r và do đó mâuthuẫn với giả thiết r là phần tử cực tiểu của S. Vì r a mod b, tồn tại duy nhất q 2 Z sao chophương tình (2.1) thoả mãn.Với mọi cặp số nguyên a; b 2 Z, ước chung lớn nhất gcd.a; b/ là số nguyên dương d lớn nhấtsao cho cả a và b đều là bội của d . 7 Tạp chí Epsilon, Số 05, 10/2015Thực hiện nhiều lần phép chia có dư của Euclid là một phương pháp hiệu quả để tính ướcchung lớn nhất. Nếu a D bq C r như trong phương trình (2.1), ta dễ dàng kiểm tra gcd.a; b/ Dgcd.b; r/. Thay vì tính ước chúng lớn nhất của a D a0 và b D b0 , ta chỉ cần tính ước chunglớn nhất của b D a1 và r D b1 với 0 < r < jbj. Tiếp tục như vậy, ta sẽ có các cặp số nguyên.a0 ; b0 /, .a1 ; b1 /, ... sao cho gcd.a0 ; b0 / D gcd.a1 ; b1 / D với jb0 j > b1 > b2 > > 0. Dãy số này bắt buộc phải dừng ở một thời điểm nào đó, giả sử nódừng ở .an ; bn /. Ta chỉ không thực hiện được phép chia Euclid nữa khi số chia bằng không, cónghĩa là bn D 0. Hiển nhiên nếu bn D 0 thì ta có gcd.an ; bn / D an , cho nên gcd.a; b/ D D gcd.an ; bn / D an :Giải thuật trình bày ở trên gọi là thuật toán Euclid. Nhìn từ góc độ thực hành, thuật toán Euclidlà một giải thuật hiệu quả để tính ước chung lớn nhất của hai số nguyên lớn. Nhìn từ góc độ lýthuyết, thuật toán Euclid kéo theo định lý sau, thường gọi là định lý Bezout:Định lý 2.1. Với mọi số nguyên a; b 2 Z, ước chung lớn nhất d D gcd.a; b/ biểu diễn được dướidạng d D xa C yb với x; y 2 Z.Thật vậy, theo quy nạp, tất cả các số a0 ; b0 ; a1 ; b1 ; : : : ; an ; bn D 0 xuất hiện trong thuật toánEuclid trình bày ở trên đều biểu diễn được dưới dạng xa C yb và đăc biệt d D an có dạng này.Có một chứng minh hơi khác trong đó sử dụng nguyên lý trật tự thay cho thuật toán Euclid. Xéttập S các số nguyên dương n có dạng n D xa C yb với x; y 2 Z. Tập này có một phần tử cựctiểu ký hiệu là e 2 S . Ta cần chứng minh rằng d D e.Vì d ja và d jb cho nên d jn với mọi n 2 S . Vì vậy d je. Để chứng minh d D e, ta chỉ cần chứngminh rằng bản thân e cũng là một ước chung của a và b. Giả sử không phải như thế, chẳng hạnnhư e không là ước của a. Khi đó thực hiện phép chia có dư Euclid của a chia cho e ta sẽ cóa D qe C r với 0 < r < e. Hiển nhiên r 2 S vì cũng có dạng xa C yb cho nên điểu này sẽ mâuthuẫn với tính cực tiểu của e. Vì vậy e phải là ước chung của a và b.Định lý 2.2. Nếu d jab và gcd.d; a/ D 1 thì d jb.Nếu gcd.d; a/ D 1 thì sẽ tồn tại x; y 2 Z sao cho xd C ya D 1. Khi đó b D .xd C ya/b hiểnnhiên là bội của d .Định lý 2.3 (Định lý cơ bản của ...