Nghịch đảo bậc hai

Định luật nghịch đảo bậc hai, mà Gauss gọi là định lý vàng, liên hệ việc một số nguyên tố p có phải là bình phương modulo q hay không với việc q có phải là bình phương modulo p hay không, đưa ra một tiêu chí mạnh mẽ và đối xứng bất ngờ cho khả năng giải được.

Definition

Một số nguyên là thặng dư bậc hai modulo một số nguyên tố p nếu nó đồng dư với một số chính phương mod p. Nghịch đảo bậc hai là định lý liên hệ, đối với các số nguyên tố lẻ p và q khác nhau, khả năng giải được của x bình phương đồng dư với q mod p với khả năng giải được của x bình phương đồng dư với p mod q.

Scope

Chủ đề này bao gồm các thặng dư bậc hai và không thặng dư modulo một số nguyên tố, tiêu chí Euler, ký hiệu Legendre và tính nhân của nó, ký hiệu Jacobi, hai định luật bổ sung (cho số âm một và cho số hai), và bản thân định luật nghịch đảo chính, bao gồm vai trò của nó như là trường hợp đầu tiên của các định luật nghịch đảo của lý thuyết trường lớp.

Core questions

• Cho một số nguyên tố lẻ p, những thặng dư nào là bình phương, và tiêu chí Euler quyết định điều này như thế nào?
• Các ký hiệu Legendre và Jacobi mã hóa thông tin thặng dư và hoạt động nhân như thế nào?
• Định luật nghịch đảo khẳng định chính xác điều gì, và các bổ sung xử lý số âm một và số hai như thế nào?
• Tại sao nghịch đảo bậc hai được coi là nguyên mẫu của các định luật nghịch đảo cao hơn của lý thuyết trường lớp?

Key theories

Tiêu chí Euler và ký hiệu Legendre

Một số nguyên a là thặng dư bậc hai mod một số nguyên tố lẻ p chính xác khi a lũy thừa (p trừ một)/2 đồng dư với một; ký hiệu Legendre ghi lại dấu này và hoàn toàn nhân tính trong đối số trên cùng của nó.

Định luật nghịch đảo bậc hai

Đối với các số nguyên tố lẻ p và q khác nhau, tích của hai ký hiệu Legendre bằng âm một lũy thừa ((p trừ một)/2)((q trừ một)/2), vì vậy nghịch đảo chỉ thất bại khi cả hai số nguyên tố đều đồng dư với ba mod bốn.

Các định luật bổ sung và ký hiệu Jacobi

Các quy tắc riêng biệt xác định khi nào âm một và hai là thặng dư, và ký hiệu Jacobi mở rộng ký hiệu Legendre cho các mô-đun hợp số, cho phép tính toán hiệu quả mà không cần phân tích thừa số.

Clinical relevance

Nghịch đảo và ký hiệu Jacobi cung cấp các thuật toán nhanh để quyết định tính thặng dư bậc hai, được sử dụng trong các phép thử tính nguyên tố (Solovay-Strassen), trong việc tính căn bậc hai modulo các số nguyên tố, và trong các sơ đồ mật mã mà tính bảo mật của chúng dựa trên giả định thặng dư bậc hai.

History

Được Euler và Legendre phỏng đoán, định luật này lần đầu tiên được Gauss chứng minh đầy đủ vào năm 1796, người đã nhiều lần quay lại với nó và đưa ra tám bằng chứng khác nhau; hiện nay có hơn hai trăm bằng chứng được biết đến. Sự tổng quát hóa của nó lên các lũy thừa cao hơn đã thúc đẩy Eisenstein, Kummer, và cuối cùng là các định luật nghịch đảo của lý thuyết trường lớp.

Key figures

• Carl Friedrich Gauss
• Adrien-Marie Legendre
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

Tại sao Gauss lại chứng minh cùng một định lý tám lần?

Mỗi bằng chứng làm sáng tỏ các cấu trúc khác nhau (tổng Gauss, đếm điểm lưới, cyclotomy), và Gauss tìm kiếm một bằng chứng có thể tổng quát hóa cho các định luật nghịch đảo cao hơn, điều này sau đó đã thúc đẩy sự phát triển của lý thuyết số đại số.

Sự khác biệt giữa ký hiệu Legendre và Jacobi là gì?

Ký hiệu Legendre được định nghĩa cho một mô-đun nguyên tố lẻ và phát hiện chính xác các thặng dư bậc hai; ký hiệu Jacobi tổng quát hóa nó cho các mô-đun hợp số lẻ để tính toán, nhưng giá trị một không còn đảm bảo số đó là thặng dư.