Từ đại số đến Bitcoin: 26, Fermat và tôi
26 là một trong những con số mà tôi yêu thích nhất: nó là số tự nhiên duy nhất nằm kẹp giữa một số bình phương (25) và một số lập phương (27).
Đây là một trong những phát hiện của Fermat, nhà toán học vĩ đại người Pháp sống vào thế kỷ 17. Fermat viết bên lề cuốn Arithmetica của Diophantus rằng nghiệm nguyên duy nhất của phương trình $latex y^2 = x^3 - 2$ là $latex (3, \pm 5)$, nhưng ông không công bố bất kỳ chứng minh cụ thể nào cả (nghe quen không?!). Fermat còn thách thức các nhà toán học người Anh cùng thời chứng minh nó, nhưng ai cũng bó tay. Bẵng đi 80 năm sau, Euler công bố một chứng minh, nhưng ngặt nỗi, chứng minh của Euler sai. Bạn có thể tin được không? Euler vĩ đại đưa ra một chứng minh sai! Cho đến tận thế kỷ 19, gần 150 năm sau thời đại của Fermat, con người mới có đủ tri thức để chứng minh rằng Fermat đã đúng. Số 26 đúng là con số duy nhất nằm giữa một số bình phương và một số lập phương.
Đây là một trong những phát hiện của Fermat, nhà toán học vĩ đại người Pháp sống vào thế kỷ 17. Fermat viết bên lề cuốn Arithmetica của Diophantus rằng nghiệm nguyên duy nhất của phương trình $latex y^2 = x^3 - 2$ là $latex (3, \pm 5)$, nhưng ông không công bố bất kỳ chứng minh cụ thể nào cả (nghe quen không?!). Fermat còn thách thức các nhà toán học người Anh cùng thời chứng minh nó, nhưng ai cũng bó tay. Bẵng đi 80 năm sau, Euler công bố một chứng minh, nhưng ngặt nỗi, chứng minh của Euler sai. Bạn có thể tin được không? Euler vĩ đại đưa ra một chứng minh sai! Cho đến tận thế kỷ 19, gần 150 năm sau thời đại của Fermat, con người mới có đủ tri thức để chứng minh rằng Fermat đã đúng. Số 26 đúng là con số duy nhất nằm giữa một số bình phương và một số lập phương.
Chuyện này có liên quan gì đến tôi?
Tôi vô tình thấy bài toán này một vài năm trước và kể từ đó lâu lâu lại mất ăn mất ngủ vài buổi, vì chứng minh mãi không được. Tìm trên Internet cũng có vài chứng minh, nhưng mà chúng sử dụng kiến thức toán tôi không hiểu được. Tôi hầu như đã bỏ cuộc rồi, cho đến khi tôi bắt đầu học thêm toán vì muốn làm mật mã. Ai dè cái mớ toán mà tôi học lại có dây mơ rễ má với bài toán này.
Những kiến thức toán mà tôi sắp trình bày chẳng phải cao siêu gì, tôi nhớ không lầm thì chương trình năm nhất đại học của tôi có dạy hết, nhưng mà hồi xưa tôi không có chịu học, vì không có biết nó hay thế này :-).
Chứng minh của Euler
Đầu tiên Euler chuyển phương trình thành $latex x^3 = y^2 + 2$ (1). Ý tưởng chủ đạo là: a) phân tích vế phải của (1) thành tích hai thừa số nguyên tố cùng nhau; b) vế trái là một số luỹ thừa bậc ba, cho nên cả hai thừa số của vế phải đều là lũy thừa bậc ba; c) từ đó tìm ra nghiệm của phương trình.
Bài tập 1: cho $latex a, b, c \in \mathbf{Z}$ chứng minh rằng $latex a = x^3, b = y^3$ với $latex x, y \in \mathbf{Z}$ nếu như $latex c^3 = {ab}$ và $latex \gcd{(a, b)} = 1$, trong đó $latex \gcd{(a, b)}$ là ước số chung lớn nhất của $latex a$ và $latex b$.
Rõ ràng nếu chỉ xét trên $latex \mathbf{Z}$ thì không có cách nào phân tích được vế phải của (1) thành nhân tử cả. Nhưng toán học là trò chơi mà ở đó các nhà toán học đặt ra các luật chơi, càng ít càng tốt, rồi tự hỏi: cái thế giới mà chúng ta xây dựng từ những luật chơi này có gì hay ho và hữu dụng không? Khi mà nhóm luật chơi ban đầu không còn đem lại những kết quả thú vị nữa thì người ta sẽ thêm vào những luật chơi mới và lại đặt lại câu hỏi ở trên.
Tương tự như thế, để giải quyết những bài toán khó người ta thường thêm vào những luật chơi để tạo ra một thế giới mới, mạnh mẽ hơn, phổ quát hơn nhưng vẫn tương thích với thế giới cũ, rồi dùng những kết quả trong thế giới mới để giải quyết các bài toán trong thế giới cũ. Để giải quyết bài toán của Fermat, Euler thêm vào một luật chơi mới: tồn tại một số $latex \delta$ sao cho $latex \delta^2 = -2$. Nếu chúng ta chấp nhận luật chơi này thì vế phải của (1) sẽ phân tích được thành nhân tử với $latex x^3 = (y - \sqrt{-2}) (y + \sqrt{-2})$ (2).
Không đưa ra một chứng minh cụ thể, Euler chỉ lập luận rằng do $latex y - \sqrt{-2}$ và $latex y + \sqrt{-2}$ nguyên tố cùng nhau (Euler cũng không giải thích tại sao) nên mỗi thừa số phải là một lũy thừa bậc ba. Nghĩa là $latex \exists a, b, c, d \in \mathbf{Z}$ sao cho:
$latex y - \sqrt{-2} = (a + b\sqrt{-2})^3 = (a^3 - 6ab^2) + (3a^2b - 2b^3)\sqrt{-2} $ (3)
$latex y + \sqrt{-2} = (c + d\sqrt{-2})^3 = (c^3 - 6cd^2) + (3c^2d - 2d^3)\sqrt{-2}$ (4)
Vì $latex \sqrt{-2} \notin \mathbf{Z}$, nên từ (3) ta có $latex 3a^2b - 2b^3 = b(3a^2 - 2b^2) = -1$. Nghiệm của phương trình này là $latex a = \pm 1$ và $latex b = -1$. Tương tự như thế ta suy ra nghiệm của phương trình (4) là $latex c = \pm 1$ và $latex d = 1$. Từ đó tính được $latex y = \pm 5$. Do đó $latex (3, \pm 5)$ là nghiệm nguyên duy nhất của phương trình (1).
Để thấy thiếu sót trong lập luận của Euler, chúng ta hãy thử dùng phương pháp này để giải phương trình $latex x^2 = y^2 + 5$. Theo Euler thì $latex \exists a, b, c, d \in \mathbf{Z}$ sao cho:
$latex y - \sqrt{-5} = (a + b\sqrt{-5})^2 = (a^2 - 5b^2) + (2ab)\sqrt{-2} $ (3)
$latex y + \sqrt{-5} = (c + d\sqrt{-5})^2 = (c^2 - 5c^2) + (2cd)\sqrt{-2}$ (4)
Suy ra $latex 2ab = -1$ và $latex 2cd = 1$ (vô lý). Do đó theo Euler phương trình $latex x^2 = y^2 + 5$ không có nghiệm nguyên, nhưng có thể thấy rằng $latex (3, 2)$ là một nghiệm.
Vậy Euler sai ở chỗ nào? Để hiểu chỗ sai của Euler, chúng ta cần phải hiểu chuyện gì xảy ra khi luật chơi mới được thêm vào.
Đại số trừu tượng
Trước khi tìm hiểu luật chơi mới, chúng ta cần phải nhìn lại những luật chơi đã có. Do đề bài là tìm nghiệm nguyên, luật chơi mà chúng ta quan tâm là những luật chi phối các số nguyên và các phép toán giữa chúng. Xét phép toán cộng trên tập $latex \mathbf{Z}$ chúng ta có thể thấy những luật chơi sau đây:
Những luật chơi này chẳng có gì đặc biệt, nếu không muốn nói là hết sức tầm thường, nhưng tôi muốn nhấn mạnh: sự tầm thường của chúng chẳng qua là do chúng ta quá quen thuộc với phép cộng trên tập số nguyên. Bạn sẽ thấy 5 luật chơi này sâu sắc hơn nhiều, nếu biết rằng chúng vẫn đúng nếu chúng ta xét phép cộng hai điểm trên đường cong elliptic định nghĩa trên một trường hữu hạn - phép toán mà từ đó người ta xây dựng một thuật toán rất quan trọng trong Bitcoin.
Phép cộng trên $latex \mathbf{Z}$ chỉ là một ví dụ cụ thể của một cấu trúc đại số (algebraic structure) sâu sắc và tổng quát hơn nhiều, mà các nhà toán học gọi là nhóm Abel (Abelian group). Nếu phép toán trên một tập hợp không có tính giao hoán, nhưng vẫn thỏa đầy đủ các điều kiện còn lại (ví dụ như phép nhân hai ma trận) cấu trúc đại số được tạo ra vẫn được xem làm một nhóm, nhưng chúng ta chỉ xem xét nhóm Abel trong phạm vi bài viết này. Trừ khi có ghi chú cụ thể, từ đây về sau tôi sẽ dùng từ nhóm để chỉ nhóm Abel.
Một cách tổng quát, phép toán, ký hiệu là $latex +_{\mathbf{G}}$, trên tập $latex \mathbf{G}$ sẽ tạo thành một nhóm, nếu thỏa những điều kiện sau đây:
Bài tập 2: cho $latex \mathbf{G}$ là một nhóm, chứng minh rằng:
a) $latex \mathbf{G}$ chỉ có duy nhất một phần tử identity.
b) Mọi phần tử của $latex \mathbf{G}$ chỉ có duy nhất một nghịch đảo.
c) $latex a +_{\mathbf{G}} b = a +_{\mathbf{G}} c \Longleftrightarrow b = c, \ \forall a,b,c \in \mathbf{G}$.
Trên tập $latex \mathbf{Z}$ thì những thuộc tính trong bài tập ở trên được mặc nhiên thừa nhận như là một phần của luật chơi, nhưng bây giờ chúng ta thấy rằng có thể chứng minh được chúng. Nói cách khác nhóm luật chơi mà chúng ta chọn ra đã bao gồm luôn những thuộc tính này. Do đó chọn lựa những luật chơi nào để tổng quát hóa lên là một vấn đề quan trọng. Nếu chọn thiếu thì chúng ta không thể xây dựng được những kết quả hữu ích, còn chọn thừa thì chúng ta lại sẽ không nhìn thấy được bức tranh toàn cảnh. Tại sao những luật chơi ở trên được chọn? Câu trả lời đơn giản là vì người ta thấy chúng vừa đủ.
Nhóm xuất hiện ở khắp nơi. Những thuật toán mã hóa khóa công khai phổ biến nhất được xây dựng dựa trên nhóm. Hàng xóm của tôi làm machine learning, tập trung vào nhận dạng giọng nói, một lĩnh vực tưởng chừng như chẳng liên quan gì đến nhóm hay đại số, nhưng một lần tôi thấy anh ấy đọc sách đại số, hỏi ra thì mới biết có một nhánh nghiên cứu mới trong ngành của anh ấy sử dụng các công cụ và tri thức của đại số trừu tượng (abstract algebra), tức là nhóm và các cấu trúc đại số khác, để giải quyết các vấn đề của machine learning.
Đây chính là sức mạnh của đại số trừu tượng. Chúng ta có thể quên đi bản chất của những phần tử và phép toán giữa chúng, mà chỉ cần tìm hiểu những tính chất của một nhóm tổng quát, suy ra từ tập luật chơi ban đầu, nhưng những tính chất này sẽ đúng trên tất cả các nhóm. Ví dụ như các định lý ở bài tập số 2 đúng với nhóm phép cộng trên $latex \mathbf{Z}$, nhóm phép nhân của trường hữu hạn $latex \mathbf{F}_p$ (sẽ nói đến sau), hay nhóm các điểm trên đường cong elliptic trên một trường hữu hạn, v.v. Nói cách khác, chúng ta chỉ cần tìm hiểu một lần và có thể dùng đi dùng lại tri thức về nhóm cho các ứng dụng rất khác nhau.
Ngoài phép cộng ra trên tập $latex \mathbf{Z}$ còn có phép nhân thỏa mãn các luật chơi sau đây:
Một tập hợp với hai phép toán thỏa mãn các tính chất tương tự như phép cộng và nhân trên $latex \mathbf{Z}$ được gọi là vành (ring). $latex \mathbf{Z}$ là vành số nguyên. Tập hợp các số hữu tỉ $latex \mathbf{Q}$ với các tính chất thông thường của phép cộng và phép nhân tạo thành một vành. Tập hợp các số hữu tỉ $latex \mathbf{R}$ với các tính chất thông thường của phép cộng và phép nhân tạo thành một vành.
Lưu ý: tương tự như nhóm, tồn tại những vành mà phép nhân không có tính giao hoán. Cũng có vành mà phần tử identity của phép nhân không tồn tại. Do đó nói một cách chính xác vành mà chúng ta xét ở đây là vành giao hoán với phần tử identity của phép nhân, nhưng do tất cả các vành mà chúng ta quan tâm đều ở dạng này cho nên từ đây về sau tôi chỉ gọi chúng là vành.
Quay trở lại chứng minh của Euler. Nhắc lại, Euler thêm vào một luật chơi mới: tồn tại phần tử $latex \delta$ sao cho $latex \delta^2 = -2$. Xét tập $latex \mathbf{Z}[\sqrt{-2}] = \{a + b\delta: \ a, b \in \mathbf{Z}\}$.
Cho $latex x = a + b\delta, \ x' = a' + b'\delta$, tổng và tích của $latex x$ và $latex x'$ được định nghĩa như sau:
Dễ dàng thấy rằng $latex \mathbf{Z} \subset \mathbf{Z}[\sqrt{m}]$, trong đó $latex m < 0$. Người ta gọi $latex \mathbf{Z}$ là một vành con của $latex \mathbf{Z}[\sqrt{m}]$. Đây là điểm mấu chốt để thấy được chỗ sai trong lập luận của Euler: vì $latex \mathbf{Z}$ là vành con của $latex \mathbf{Z}[\sqrt{m}]$, một số tính chất của $latex \mathbf{Z}$ có thể không còn đúng trên $latex \mathbf{Z}[\sqrt{m}]$.
Sự khác biệt đó là: mọi số nguyên trên vành $latex \mathbf{Z}$ có thể được phân tích thành tích của các số nguyên tố và sự phân tích này là duy nhất. Đây là định lý cơ bản của số học. Định lý này có vẻ hiển nhiên, nhưng lưu ý rằng nó không thuộc vào tập luật chơi ban đầu trong định nghĩa của một vành. Nói cách khác, từ tập luật chơi này, với một số vành nhất định, ta có thể chứng minh hoặc phủ định tính chất phân tích nhân tử duy nhất (unique factorization).
Trong phần sau chúng ta sẽ tìm hiểu tính chất phân tích nhân tử duy nhất và chứng minh rằng nó đúng trên $latex \mathbf{Z}$ và $latex \mathbf{Z}[\sqrt{-2}]$, nhưng lại sai trên $latex \mathbf{Z}[\sqrt{-5}]$.
[1] Tôi không biết nên dịch identity element ra tiếng Việt sao cho hay. Ai biết chỉ giùm.
Những kiến thức toán mà tôi sắp trình bày chẳng phải cao siêu gì, tôi nhớ không lầm thì chương trình năm nhất đại học của tôi có dạy hết, nhưng mà hồi xưa tôi không có chịu học, vì không có biết nó hay thế này :-).
Chứng minh của Euler
Đầu tiên Euler chuyển phương trình thành $latex x^3 = y^2 + 2$ (1). Ý tưởng chủ đạo là: a) phân tích vế phải của (1) thành tích hai thừa số nguyên tố cùng nhau; b) vế trái là một số luỹ thừa bậc ba, cho nên cả hai thừa số của vế phải đều là lũy thừa bậc ba; c) từ đó tìm ra nghiệm của phương trình.
Bài tập 1: cho $latex a, b, c \in \mathbf{Z}$ chứng minh rằng $latex a = x^3, b = y^3$ với $latex x, y \in \mathbf{Z}$ nếu như $latex c^3 = {ab}$ và $latex \gcd{(a, b)} = 1$, trong đó $latex \gcd{(a, b)}$ là ước số chung lớn nhất của $latex a$ và $latex b$.
Rõ ràng nếu chỉ xét trên $latex \mathbf{Z}$ thì không có cách nào phân tích được vế phải của (1) thành nhân tử cả. Nhưng toán học là trò chơi mà ở đó các nhà toán học đặt ra các luật chơi, càng ít càng tốt, rồi tự hỏi: cái thế giới mà chúng ta xây dựng từ những luật chơi này có gì hay ho và hữu dụng không? Khi mà nhóm luật chơi ban đầu không còn đem lại những kết quả thú vị nữa thì người ta sẽ thêm vào những luật chơi mới và lại đặt lại câu hỏi ở trên.
Tương tự như thế, để giải quyết những bài toán khó người ta thường thêm vào những luật chơi để tạo ra một thế giới mới, mạnh mẽ hơn, phổ quát hơn nhưng vẫn tương thích với thế giới cũ, rồi dùng những kết quả trong thế giới mới để giải quyết các bài toán trong thế giới cũ. Để giải quyết bài toán của Fermat, Euler thêm vào một luật chơi mới: tồn tại một số $latex \delta$ sao cho $latex \delta^2 = -2$. Nếu chúng ta chấp nhận luật chơi này thì vế phải của (1) sẽ phân tích được thành nhân tử với $latex x^3 = (y - \sqrt{-2}) (y + \sqrt{-2})$ (2).
Không đưa ra một chứng minh cụ thể, Euler chỉ lập luận rằng do $latex y - \sqrt{-2}$ và $latex y + \sqrt{-2}$ nguyên tố cùng nhau (Euler cũng không giải thích tại sao) nên mỗi thừa số phải là một lũy thừa bậc ba. Nghĩa là $latex \exists a, b, c, d \in \mathbf{Z}$ sao cho:
$latex y - \sqrt{-2} = (a + b\sqrt{-2})^3 = (a^3 - 6ab^2) + (3a^2b - 2b^3)\sqrt{-2} $ (3)
$latex y + \sqrt{-2} = (c + d\sqrt{-2})^3 = (c^3 - 6cd^2) + (3c^2d - 2d^3)\sqrt{-2}$ (4)
Vì $latex \sqrt{-2} \notin \mathbf{Z}$, nên từ (3) ta có $latex 3a^2b - 2b^3 = b(3a^2 - 2b^2) = -1$. Nghiệm của phương trình này là $latex a = \pm 1$ và $latex b = -1$. Tương tự như thế ta suy ra nghiệm của phương trình (4) là $latex c = \pm 1$ và $latex d = 1$. Từ đó tính được $latex y = \pm 5$. Do đó $latex (3, \pm 5)$ là nghiệm nguyên duy nhất của phương trình (1).
Để thấy thiếu sót trong lập luận của Euler, chúng ta hãy thử dùng phương pháp này để giải phương trình $latex x^2 = y^2 + 5$. Theo Euler thì $latex \exists a, b, c, d \in \mathbf{Z}$ sao cho:
$latex y - \sqrt{-5} = (a + b\sqrt{-5})^2 = (a^2 - 5b^2) + (2ab)\sqrt{-2} $ (3)
$latex y + \sqrt{-5} = (c + d\sqrt{-5})^2 = (c^2 - 5c^2) + (2cd)\sqrt{-2}$ (4)
Vậy Euler sai ở chỗ nào? Để hiểu chỗ sai của Euler, chúng ta cần phải hiểu chuyện gì xảy ra khi luật chơi mới được thêm vào.
Đại số trừu tượng
Trước khi tìm hiểu luật chơi mới, chúng ta cần phải nhìn lại những luật chơi đã có. Do đề bài là tìm nghiệm nguyên, luật chơi mà chúng ta quan tâm là những luật chi phối các số nguyên và các phép toán giữa chúng. Xét phép toán cộng trên tập $latex \mathbf{Z}$ chúng ta có thể thấy những luật chơi sau đây:
Nhóm phép cộng trên $latex \mathbf{Z}$
i) Đóng: $latex a + b \in \mathbf{Z}, \ \forall a, b \in \mathbf{Z}$
ii) Kết hợp: $latex a + (b + c) = (a + b) + c , \ \forall a, b, c \in \mathbf{Z}$
iii) Giao hoán: $latex a + b = b + a, \ \forall a, b \in \mathbf{Z}$
iv) Phần tử identity [1]: tồn tại một phần tử identity, ký hiệu là $latex 0_{\mathbf{Z}}$ thỏa điều kiện $latex a + 0_{\mathbf{Z}} = a, \ \forall a \in \mathbf{Z}$. Dễ dàng thấy rằng đối với phép cộng trên $latex \mathbf{Z}$ thì $latex 0_{\mathbf{Z}}$ chính là số 0.
v) Phần tử nghịch đảo: $latex \forall a \in \mathbf{Z}, \ \exists b \in \mathbf{Z}: a + b = 0_{\mathbf{Z}}$. Đối với phép cộng trên $latex \mathbf{Z}$ thì phần tử nghịch đảo của $latex a$ chính là $latex -a$.
Phép cộng trên $latex \mathbf{Z}$ chỉ là một ví dụ cụ thể của một cấu trúc đại số (algebraic structure) sâu sắc và tổng quát hơn nhiều, mà các nhà toán học gọi là nhóm Abel (Abelian group). Nếu phép toán trên một tập hợp không có tính giao hoán, nhưng vẫn thỏa đầy đủ các điều kiện còn lại (ví dụ như phép nhân hai ma trận) cấu trúc đại số được tạo ra vẫn được xem làm một nhóm, nhưng chúng ta chỉ xem xét nhóm Abel trong phạm vi bài viết này. Trừ khi có ghi chú cụ thể, từ đây về sau tôi sẽ dùng từ nhóm để chỉ nhóm Abel.
Một cách tổng quát, phép toán, ký hiệu là $latex +_{\mathbf{G}}$, trên tập $latex \mathbf{G}$ sẽ tạo thành một nhóm, nếu thỏa những điều kiện sau đây:
Định nghĩa nhóm
i) Đóng: $latex a +_{\mathbf{G}} b \in \mathbf{G}, \ \forall a, b \in \mathbf{G}$Lưu ý: tôi dùng ký hiệu $latex +_{\mathbf{G}}$ để chỉ phép toán trên nhóm, nhưng không có nghĩa phép toán đó tương tự như phép cộng hai số nguyên.
ii) Kết hợp: $latex a +_{\mathbf{G}}(b +_{\mathbf{G}} c) = (a +_{\mathbf{G}} b) +_{\mathbf{G}} c , \ \forall a, b, c \in \mathbf{G}$
iii) Giao hoán: $latex a +_{\mathbf{G}} b = b +_{\mathbf{G}} a, \ \forall a, b \in \mathbf{G}$
iv) Phần tử identity: tồn tại một phần tử identity, ký hiệu $latex 0_{\mathbf{G}}$ thỏa điều kiện $latex a +_{\mathbf{G}} 0_{\mathbf{G}} = a, \ \forall a \in \mathbf{G}$.
v) Phần tử nghịch đảo: $latex \forall a \in \mathbf{G}, \ \exists b \in \mathbf{G}: a +_{\mathbf{G}} b = 0_{\mathbf{G}}$.
Bài tập 2: cho $latex \mathbf{G}$ là một nhóm, chứng minh rằng:
a) $latex \mathbf{G}$ chỉ có duy nhất một phần tử identity.
b) Mọi phần tử của $latex \mathbf{G}$ chỉ có duy nhất một nghịch đảo.
c) $latex a +_{\mathbf{G}} b = a +_{\mathbf{G}} c \Longleftrightarrow b = c, \ \forall a,b,c \in \mathbf{G}$.
Trên tập $latex \mathbf{Z}$ thì những thuộc tính trong bài tập ở trên được mặc nhiên thừa nhận như là một phần của luật chơi, nhưng bây giờ chúng ta thấy rằng có thể chứng minh được chúng. Nói cách khác nhóm luật chơi mà chúng ta chọn ra đã bao gồm luôn những thuộc tính này. Do đó chọn lựa những luật chơi nào để tổng quát hóa lên là một vấn đề quan trọng. Nếu chọn thiếu thì chúng ta không thể xây dựng được những kết quả hữu ích, còn chọn thừa thì chúng ta lại sẽ không nhìn thấy được bức tranh toàn cảnh. Tại sao những luật chơi ở trên được chọn? Câu trả lời đơn giản là vì người ta thấy chúng vừa đủ.
Nhóm xuất hiện ở khắp nơi. Những thuật toán mã hóa khóa công khai phổ biến nhất được xây dựng dựa trên nhóm. Hàng xóm của tôi làm machine learning, tập trung vào nhận dạng giọng nói, một lĩnh vực tưởng chừng như chẳng liên quan gì đến nhóm hay đại số, nhưng một lần tôi thấy anh ấy đọc sách đại số, hỏi ra thì mới biết có một nhánh nghiên cứu mới trong ngành của anh ấy sử dụng các công cụ và tri thức của đại số trừu tượng (abstract algebra), tức là nhóm và các cấu trúc đại số khác, để giải quyết các vấn đề của machine learning.
Đây chính là sức mạnh của đại số trừu tượng. Chúng ta có thể quên đi bản chất của những phần tử và phép toán giữa chúng, mà chỉ cần tìm hiểu những tính chất của một nhóm tổng quát, suy ra từ tập luật chơi ban đầu, nhưng những tính chất này sẽ đúng trên tất cả các nhóm. Ví dụ như các định lý ở bài tập số 2 đúng với nhóm phép cộng trên $latex \mathbf{Z}$, nhóm phép nhân của trường hữu hạn $latex \mathbf{F}_p$ (sẽ nói đến sau), hay nhóm các điểm trên đường cong elliptic trên một trường hữu hạn, v.v. Nói cách khác, chúng ta chỉ cần tìm hiểu một lần và có thể dùng đi dùng lại tri thức về nhóm cho các ứng dụng rất khác nhau.
Ngoài phép cộng ra trên tập $latex \mathbf{Z}$ còn có phép nhân thỏa mãn các luật chơi sau đây:
Tính chất của phép nhân trên $latex \mathbf{Z}$Lưu ý rằng không có phần tử nào của $latex \mathbf{Z}$, ngoại trừ $latex \pm{1}$, có phần tử nghịch đảo theo phép nhân.
i) Đóng: $latex ab \in \mathbf{Z}, \ \forall a, b \in \mathbf{Z}$
ii) Kết hợp: $latex a(bc) = (ab)c, \ \forall a, b \in \mathbf{Z}$.
iii) Giao hoán: $latex ab = ba, \ \forall a, b \in \mathbf{Z}$.
iv) Phần tử identity: tồn tại phần tử identity, ký hiệu là $latex 1_{\mathbf{Z}}$, thỏa điều kiện $latex a1_{\mathbf{Z}} = a, \ \forall a \in \mathbf{Z}$. Dễ dàng thấy rằng đối với phép nhân trên $latex \mathbf{Z}$ thì $latex 1_{\mathbf{Z}}$ chính là số 1.
v) Phân phối trên phép cộng: $latex a(b + c) = ab + ac, \ \forall a, b, c \in \mathbf{Z}$.
Một tập hợp với hai phép toán thỏa mãn các tính chất tương tự như phép cộng và nhân trên $latex \mathbf{Z}$ được gọi là vành (ring). $latex \mathbf{Z}$ là vành số nguyên. Tập hợp các số hữu tỉ $latex \mathbf{Q}$ với các tính chất thông thường của phép cộng và phép nhân tạo thành một vành. Tập hợp các số hữu tỉ $latex \mathbf{R}$ với các tính chất thông thường của phép cộng và phép nhân tạo thành một vành.
Lưu ý: tương tự như nhóm, tồn tại những vành mà phép nhân không có tính giao hoán. Cũng có vành mà phần tử identity của phép nhân không tồn tại. Do đó nói một cách chính xác vành mà chúng ta xét ở đây là vành giao hoán với phần tử identity của phép nhân, nhưng do tất cả các vành mà chúng ta quan tâm đều ở dạng này cho nên từ đây về sau tôi chỉ gọi chúng là vành.
Quay trở lại chứng minh của Euler. Nhắc lại, Euler thêm vào một luật chơi mới: tồn tại phần tử $latex \delta$ sao cho $latex \delta^2 = -2$. Xét tập $latex \mathbf{Z}[\sqrt{-2}] = \{a + b\delta: \ a, b \in \mathbf{Z}\}$.
Cho $latex x = a + b\delta, \ x' = a' + b'\delta$, tổng và tích của $latex x$ và $latex x'$ được định nghĩa như sau:
Phép cộng và nhân trên $latex \mathbf{Z}[\sqrt{-2}] $Bài tập 3: Chứng minh rằng tập $latex \mathbf{Z}[\sqrt{-2}]$ với hai phép toán định nghĩa như trên tạo thành một vành.
$latex x + y = (a + a') + (b + b')\delta$
$latex xy = (aa' - bb') + (ab' + a'b)\delta$
Dễ dàng thấy rằng $latex \mathbf{Z} \subset \mathbf{Z}[\sqrt{m}]$, trong đó $latex m < 0$. Người ta gọi $latex \mathbf{Z}$ là một vành con của $latex \mathbf{Z}[\sqrt{m}]$. Đây là điểm mấu chốt để thấy được chỗ sai trong lập luận của Euler: vì $latex \mathbf{Z}$ là vành con của $latex \mathbf{Z}[\sqrt{m}]$, một số tính chất của $latex \mathbf{Z}$ có thể không còn đúng trên $latex \mathbf{Z}[\sqrt{m}]$.
Sự khác biệt đó là: mọi số nguyên trên vành $latex \mathbf{Z}$ có thể được phân tích thành tích của các số nguyên tố và sự phân tích này là duy nhất. Đây là định lý cơ bản của số học. Định lý này có vẻ hiển nhiên, nhưng lưu ý rằng nó không thuộc vào tập luật chơi ban đầu trong định nghĩa của một vành. Nói cách khác, từ tập luật chơi này, với một số vành nhất định, ta có thể chứng minh hoặc phủ định tính chất phân tích nhân tử duy nhất (unique factorization).
Trong phần sau chúng ta sẽ tìm hiểu tính chất phân tích nhân tử duy nhất và chứng minh rằng nó đúng trên $latex \mathbf{Z}$ và $latex \mathbf{Z}[\sqrt{-2}]$, nhưng lại sai trên $latex \mathbf{Z}[\sqrt{-5}]$.
[1] Tôi không biết nên dịch identity element ra tiếng Việt sao cho hay. Ai biết chỉ giùm.
Comments
Unit là các phần tử có nghịch đảo đối với phép nhân trong một vành.