Đơn giản hóa quy trình làm việc của bạn: Tìm kiếm miniwebtool.
Thêm
Trang chủ > Toán học > Phép toán toán học nâng cao > Máy tính Thuật toán Euclid Mở rộng
 

Máy tính Thuật toán Euclid Mở rộng

Tính GCD của hai số nguyên và tìm các hệ số Bézout bằng Thuật toán Euclid Mở rộng, với bảng từng bước, phép thế ngược và nghịch đảo modulo.

Máy tính Thuật toán Euclid Mở rộng

Ví dụ nhanh — nhấp để điền:

gcd(252, 105) gcd(35, 15) gcd(1071, 462) Nguyên tố cùng nhau: gcd(17,13) gcd(48, 18) gcd(100, 75)
Bất kỳ số nguyên khác không nào
Bất kỳ số nguyên khác không nào

Embed Máy tính Thuật toán Euclid Mở rộng Widget

Giới thiệu về Máy tính Thuật toán Euclid Mở rộng

Máy tính Thuật toán Euclid mở rộng tính Ước chung lớn nhất (GCD) của hai số nguyên và tìm các hệ số Bézout — các số nguyên s và t thỏa mãn gcd(a, b) = s·a + t·b. Ngoài việc tính GCD, công cụ này còn cung cấp bảng chia từng bước hoàn toàn tự động, thế ngược và tính nghịch đảo modulo, lý tưởng cho các khóa học lý thuyết số, nghiên cứu mật mã và lập trình thi đấu.

Thuật toán Euclid mở rộng là gì?

Thuật toán Euclid mở rộng (EEA) là một phần mở rộng của thuật toán Euclid tìm GCD cổ điển. Trong khi thuật toán cơ bản tìm gcd(a, b) bằng cách chia liên tiếp, phiên bản mở rộng đồng thời theo dõi hai dãy số nguyên ghi lại cách mỗi số dư có thể được biểu diễn dưới dạng tổ hợp tuyến tính của các đầu vào ban đầu.

Đồng nhất thức Bézout
$$\gcd(a, b) = s \cdot a + t \cdot b$$

trong đó s và t là các hệ số Bézout (số nguyên, có thể âm)

Cách thuật toán hoạt động

EEA duy trì ba cặp giá trị — (r, s, t) — qua mỗi bước chia:

  1. Khởi tạo: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
  2. Mỗi bước: tính thương số q = ⌊rₙ₋₁ / rₙ⌋, sau đó cập nhật rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
  3. Dừng lại khi số dư = 0; số dư trước đó là gcd(a, b)
  4. Các giá trị s và t tương ứng là các hệ số Bézout

Ví dụ từng bước: gcd(252, 105)

BướcSố bị chiaSố chiaThương sốSố dưst
125210524210
21054222101
34221201-2

Kết quả: gcd(252, 105) = 21, với đồng nhất thức Bézout: 21 = (1) × 252 + (−2) × 105. Hãy tự mình thử với máy tính ở trên để có các hệ số chính xác.

Ứng dụng của Thuật toán Euclid mở rộng

1. Nghịch đảo modulo (Mật mã học)

Ứng dụng quan trọng nhất là tính nghịch đảo modulo. Nếu gcd(a, m) = 1, thì hệ số Bézout s thỏa mãn:

Nghịch đảo Modulo
$$a^{-1} \equiv s \pmod{m}$$

Nghịch đảo modulo là thiết yếu trong mã hóa RSA (tính số mũ khóa bí mật d), trao đổi khóa Diffie-Hellman và mật mã đường cong elliptic.

2. Giải phương trình Diophantine tuyến tính

Phương trình ax + by = c có nghiệm nguyên khi và chỉ khi gcd(a, b) chia hết c. Nếu vậy, một nghiệm cụ thể là x₀ = s·(c/d), y₀ = t·(c/d) trong đó d = gcd(a, b) và s, t là các hệ số Bézout.

3. Định lý số dư Trung Hoa

EEA được sử dụng trong chứng minh kiến tạo và tính toán Định lý số dư Trung Hoa — tìm x sao cho x ≡ a₁ (mod m₁) và x ≡ a₂ (mod m₂) — bằng cách tính nghịch đảo modulo của các mô-đun.

4. Rút gọn phân số và LCD

gcd(a, b) = 1 xác nhận rằng a/b đã ở dạng tối giản. BCNN là lcm(a, b) = |a·b| / gcd(a, b).

Các hệ số Bézout không phải là duy nhất

Các hệ số Bézout s và t không phải là duy nhất. Nếu (s, t) là một nghiệm, thì (s + k·(b/d), t − k·(a/d)) cũng là một nghiệm cho bất kỳ số nguyên k nào, trong đó d = gcd(a, b). EEA trả về nghiệm mà |s| ≤ |b/d| và |t| ≤ |a/d|.

Độ phức tạp thời gian

Thuật toán Euclid mở rộng chạy trong O(log min(a, b)) lần lặp — tương tự như thuật toán Euclid cơ bản. Theo định lý Lamé, số bước không bao giờ vượt quá 5 lần số chữ số thập phân của số đầu vào nhỏ hơn. Điều này làm cho nó cực kỳ hiệu quả ngay cả đối với các số nguyên lớn được sử dụng trong các ứng dụng mật mã.

Câu hỏi thường gặp

Thuật toán Euclid mở rộng là gì?

Thuật toán Euclid mở rộng là bản mở rộng của thuật toán GCD của Euclid để tính thêm các hệ số Bézout s và t thỏa mãn gcd(a, b) = s·a + t·b. Nó theo dõi cách mỗi số dư có thể được biểu diễn dưới dạng tổ hợp tuyến tính của a và b trong suốt quá trình chia.

Hệ số Bézout là gì?

Hệ số Bézout là các số nguyên s và t được đảm bảo tồn tại bởi đồng nhất thức Bézout (một định lý trong lý thuyết số). Chúng thỏa mãn gcd(a, b) = s·a + t·b và được tính toán hiệu quả bởi Thuật toán Euclid mở rộng. Chúng được sử dụng trong tính nghịch đảo modulo, giải phương trình Diophantine và Định lý số dư Trung Hoa.

Làm thế nào để tìm nghịch đảo modulo bằng Thuật toán Euclid mở rộng?

Nếu gcd(a, b) = 1 (a và b nguyên tố cùng nhau), hệ số Bézout s thỏa mãn s·a ≡ 1 (mod b). Nghịch đảo modulo của a mod b là s mod b (được điều chỉnh để dương). Máy tính này hiển thị trực tiếp điều này trong kết quả.

Khi nào nghịch đảo modulo không tồn tại?

Nghịch đảo modulo của a theo mô-đun m tồn tại khi và chỉ khi gcd(a, m) = 1. Nếu gcd(a, m) > 1, không có số nguyên x nào thỏa mãn a·x ≡ 1 (mod m).

Độ phức tạp thời gian của Thuật toán Euclid mở rộng là bao nhiêu?

O(log min(a, b)) phép chia, tương tự như thuật toán Euclid cơ bản. Theo định lý Lamé, số bước bị giới hạn bởi 5 lần số chữ số thập phân của số đầu vào nhỏ hơn, giúp nó hoạt động rất hiệu quả.

Tài nguyên bổ sung

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy tính Thuật toán Euclid Mở rộng" tại https://MiniWebtool.com/vi/máy-tính-thuật-toán-euclid-mở-rộng/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 18/02/2026

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.

Các công cụ liên quan khác:

Máy tính Định lý Số dư Trung QuốcMới
Máy tính Ước số chung lớn nhấtNổi bật
Máy tính Nghịch đảo Nhân theo Mô-đunMới
Máy tính ModuloNổi bật

Phép toán toán học nâng cao:

Công cụ nổi bật:

Máy tính tuổiCông cụ đổi Pound sang KilogramCông cụ chuyển đổi kg sang lbsTrình Trích Xuất Ảnh từ VideoMáy tính giảm giá phần trămMáy tính thương và số dưTrình tạo oẳn tù tìMáy tính phân số tối giảnCông cụ chuyển đổi chữ số La MãMáy tính nhị phânCông cụ Mã hóa CaesarTrình Tạo Mã MorseBộ chuyển đổi thập phân sang nhị phânMáy tính HEXMáy tính căn bậc haiTrình tạo chuỗi ngẫu nhiênMáy tính Phân tích Thừa số Nguyên tốCông cụ đếm hàngParaphraser AICông cụ chuyển đổi kPa sang psiMáy tính thập phân sang phân sốCông cụ chuyển đổi nhị phân sang thập phânĐảo ngược văn bản📅 Máy tính ngàyTrình tạo tên ngẫu nhiênMáy tính thời gianCông cụ chuyển đổi cm sang feet và inchTrình chuyển đổi SRT sang TXTXóa dấu cáchBộ chuyển đổi Thập phân sang Thập lục phânCông cụ xáo trộn chữ cáiSắp xếp sốMáy tính Cạnh huyềnmáy-tính-số-mũ-độ-chính-xác-caoBộ chuyển đổi Nhị phân sang HexBộ chuyển đổi Feet và Inch sang CmCon số may mắn của tôi là gì?Máy tính Kiểm tra Chia hếtMáy tính ngày trong năm - Hôm nay là ngày thứ mấy trong nămMáy tính So sánh Phân sốĐây có phải là Số Nguyên Tố?Công cụ chuyển đổi hệ thập lục phân sang nhị phânBộ chuyển đổi Hex sang RGBGhép VideoCông cụ chia ảnhMáy tính khoảng cách giữa hai điểmMáy tính tuổi thọ pinMáy tính giá trị tương laiTung đồng xuTuổi của bạn tính bằng năm, tháng, ngày, giờ, phút, giâyBộ Chuyển Đổi Số Sang ChữTạo Trò Chơi Tìm TừCông cụ chuyển đổi Phần trăm sang PPMMáy Tính Độ Lệch Chuẩn Tương ĐốiSắp xếp theo thứ tự bảng chữ cáiBộ chuyển đổi hex sang thập phânCông cụ chuyển đổi psi sang kPaBộ chuyển đổi HEXTrình tạo mê cungMáy tính Cung Mặt trời, Mặt trăng & Cung mọc 🌞🌙✨Công cụ tạo nhóm ngẫu nhiênTrình tạo ngày sinh ngẫu nhiênSo sánh hai chuỗiTrình nén VideoTrình tạo bài tây ngẫu nhiênTrình trích xuất âm thanhBộ chuyển đổi FPSMáy tính giai thừaMáy tính Ước số chung lớn nhấtTra cứu ID người dùng InstagramCông cụ chuyển đổi centimet sang inchMáy Tính Giờ Làm ViệcMáy tính độ lệch chuẩn - Độ chính xác caoCông cụ chuyển đổi gam sang poundTrình tạo nhánh giải đấu ngẫu nhiênMáy tính Cầu thangMáy tính Modulotra-cứu-địa-chỉ-MACCông cụ chuyển đổi inch sang centimetTrình chuyển đổi HTML sang văn bảnMáy tính One Rep Max (1RM)Máy tính nhânBộ Chuyển Đổi Mã Nhị Phân Sang Mã XámBộ Chuyển Đổi Nhị PhânCông cụ chuyển đổi bát phân sang nhị phânCông cụ chuyển đổi pound sang gamBộ chuyển đổi mã Gray sang nhị phânBộ chuyển đổi RGB sang HexTrình tạo số xổ sốBộ Chia Âm ThanhChuyển đổi Nhị phân sang Bát phânChọn tên ngẫu nhiênMáy Tính Chia Đa ThứcMáy tính CAGRMáy tính LogaritCông cụ chuyển đổi thập phân sang bát phânLịch trăng non và trăng trònMáy tính Bội số chung nhỏ nhất (BCNN)Kiểm tra liên kết hỏngTrình tạo thẻ HreflangKiểm tra Chuyển hướngKiểm tra độ tin cậy tên miềnKiểm tra tốc độ trangCông cụ Phân tích Tiêu đềTra cứu DNSTra cứu WHOISCông cụ Kiểm tra Tuổi Tên miềnTrình kiểm tra Open GraphTrình tạo Sơ đồ trang XMLTrình tạo robots.txtTrình tạo Schema MarkupTrình kiểm tra WebhookBảng mã ASCIICông cụ Kiểm tra APIMáy tính Mạng con IPTrình tạo Box Shadow CSSCông cụ chuyển đổi hình ảnh sang Base64Bộ chuyển đổi HTML sang MarkdownTrình soạn thảo MarkdownChuyển đổi CSV sang JSONTrình Định dạng & Xác thực YAMLLàm đẹp HTMLLàm Đẹp CSSCông cụ nén/làm đẹp JavaScriptKiểm tra sự khác biệtTrình kiểm tra RegexTrình Định dạng và Xác thực JSONMáy tính Tuổi thọ của ChóMáy tính Bảo hiểm Thú cưngMáy tính khẩu phần ăn sốngMáy tính Thai kỳ ChóMáy tính độc tính sô-cô-laCông cụ Dự đoán Cân nặng Chó conMáy tính nhiều phân sốMáy tính khẩu phần thức ăn cho chóBộ chuyển đổi rau thơm tươi sang khôTrình chuyển đổi bơ sang dầuBộ chuyển đổi lò nướng sang nồi chiên không dầuMáy tính Sous VideMáy tính SourdoughMáy tính bột pizzaMáy tính thời gian nấu gà tâyMáy tính thời gian xông khói thịtCông cụ chuyển đổi cốc sang gramMáy tính dinh dưỡng công thức nấu ănBộ chuyển đổi đơn vị nấu ănCông cụ Điều chỉnh Công thứcMáy tính Calo Thai kỳMáy tính Tuổi thaiMáy tính Calo cho bà mẹ cho con búMáy tính phần trăm tăng trưởng của béMáy Tính Tăng Cân Thai KỳMáy tính Vùng tốc độMáy tính Nhảy caoMáy Tính Handicap GolfMáy tính điểm BowlingMáy tính Tốc độ Ba môn Phối hợpMáy tính Pace MarathonMáy tính Tiêu chuẩn Sức mạnhMáy tính mỡ cơ thể Quân độiMáy tính bước chân sang khoảng cáchMáy tính Nhịp độ BơiMáy tính Tốc độ Đạp xeMáy tính nguy cơ bệnh timMáy tính Carb ròngMáy tính CarbohydrateMáy tính Khối lượng Cơ thể Không mỡMáy tính Loại Cơ thểMáy tính nhóm máuMáy tính tuổi sinh họcMáy tính Tuổi thọ Trung bìnhMáy tính Phân vị Chiều caoTrình phiên dịch Huyết ápMáy tính Độ thanh thải CreatinineMáy tính GFRMáy Tính Giảm CânMáy tính nhịn ăn gián đoạnMáy tính KetoMáy tính Lượng ProteinMáy tính Nồng độ Cồn trong MáuMáy tính Cân nặng Lý tưởngMáy tính Vốn chủ sở hữu NhàMáy tính Lợi nhuận Lật nhàMáy tính hoa hồng bất động sảnMáy tính Chi phí Đóng Giao dịchMáy Tính Bất Động Sản Cho ThuêMáy tính Thuê vs MuaMáy tính Lợi suất Tương đương ThuếMáy tính Trợ cấp Ly hônMáy tính tiền cấp dưỡng conMáy tính Thuế Thừa kếMáy tính Thuế Tài sảnMáy tính Khấu trừ Thuế W-4Máy tính thuế 1099Máy tính Thuế Tự kinh doanhMáy tính Thuế Lợi tức VốnƯớc tính hoàn thuếMáy tính Bậc thuếMáy tính thuế thu nhậpMáy tính Đầu tư BitcoinMáy tính Lãi Lỗ Tiền Điện TửMáy tính Chi phí Nhân viênMáy tính Định giá Doanh nghiệpMáy tính Điểm Hòa vốnMáy tính HELOCMáy tính khoản vay FHAMáy tính tiền đặt cọcMáy tính Trả hết Thế chấpMáy tính Quỹ khẩn cấpMáy tính Mục tiêu Tiết kiệmMáy tính ngân sáchMáy tính Giá trị ròngMáy tính Hợp nhất NợMáy tính trả nợMáy tính khoản vay cá nhânMáy tính vay kinh doanhMáy tính Bình quân giáMáy tính Tái đầu tư Cổ tứcMáy tính lãi lỗ cổ phiếuMáy tính Quỹ tương hỗMáy tính SIPMáy tính RMDMáy tính lương hưuMáy tính Quyền lợi Bảo hiểm Xã hộiMáy tính Hưu tríMáy tính Roth IRAMáy tính 401kCông cụ chuyển đổi tiền tệMáy tính tiền tipTrình tạo Nối các ChấmTrình tạo thẻ BingoTrình tạo chuỗi từ (Word Ladder Generator)Công cụ tạo mật mã chữTạo Ô ChữTạo SlitherlinkTạo Hashi Cầu NốiTạo FutoshikiTạo Killer SudokuMáy tính Căn nguyên thủyMô phỏng mã hóa RSA từng bướcMáy tính đặc trưng EulerMáy tính đường chéo đa giácTrình tạo mẫu hình nón trải phẳngKiểm tra hàm chẵn lẻMáy tính Hệ số Chuỗi FourierMáy tính Phương pháp Runge-Kutta (RK4)Máy tính WronskianMáy tính Vết Ma trậnMáy tính Hạng Ma trậnTrình tạo tần số âm thanh ngẫu nhiênTrình tạo hợp âm ngẫu nhiênTrình tạo loadout ngẫu nhiênTrình tạo bài Poker ngẫu nhiênTrình tạo khai cuộc cờ vua ngẫu nhiênTrình tạo nhân vật RPG ngẫu nhiênMáy tính Phân tích Giá trị Kỳ dị (SVD)Máy tính Hệ số GiniMáy tính Phân phối Dừng Chuỗi MarkovMáy tính Nguyên lý Chuồng bồ câuMáy tính số StirlingMáy tính Hoán vị lệch (Giai thừa phụ)Trình tạo Số CatalanTrình xác thực dãy bậc đồ thịMáy tính Cây khung nhỏ nhấtMáy tính Đường đi Ngắn nhất DijkstraTrình tạo Ma phươngMáy tính Số Hạnh phúcMáy tính Phỏng đoán CollatzMáy tính Độ congMáy tính Bán kính Hội tụMáy tính Phân tích LU Ma trậnMáy tính Phép chiếu VectorMáy tính Gram-SchmidtMáy tính Phương trình Hình cầuMáy tính khoảng cách từ điểm đến mặt phẳngMáy tính Trực tâm Tam giácMáy tính Trọng tâm Tam giácMáy tính Công thức Dây giàyMáy tính Phân số liên tụcMáy tính Nghịch đảo Nhân theo Mô-đunMáy tính Thuật toán Euclid Mở rộngMáy tính Hàm Phi EulerMáy tính Định lý Số dư Trung QuốcCông cụ tạo Biểu đồ Venn (3 Tập hợp)Máy tính lý thuyết tập hợpCông cụ tạo bảng chân trịCông cụ chuyển đổi cân nặng người sang kiếnMáy tính Calo cho MèoMáy tính tiết kiệm bóng đènMáy tính Chi phí TắmMáy tính chi phí điện đào BitcoinMáy tính Giá trị Giấy vệ sinhMáy tính Quãng đường Bàn phímTrình tạo Bingo từ thông dụngMáy tính Xác suất Ngày nghỉ ốmMáy tính lương thực tế theo giờMáy tính Cà phê vs. Giấc ngủMáy tính thời gian trả lời emailMáy tính FIRE - Tự do Tài chính, Nghỉ hưu sớmMáy tính thời gian lãng phí đi làmBộ đếm Chi phí Cuộc họpMáy tính lương trong nhà vệ sinhTrình tạo KakuroTrình tạo KenKen (Calcudoku)trình-tạo-nonogram-picrossGiải và luyện trò chơi 24Tạo và giải SudokuMáy tính khay phô maiMáy tính đài phun sô cô laMáy tính ABV CocktailMáy tính khẩu phần mì SpaghettiMáy tính thời gian làm lạnh biaMáy tính Taco BarMáy tính BBQMáy tính quá liều CaffeineCông cụ lập kế hoạch tiệc pizzaMáy tính rượu tiệc cướiMáy tính Nhà gạch LegoMáy tính Lấp đầy Phòng Bỏng ngôMáy tính va chạm đồng xu rơiMáy tính rơi xuyên Trái đấtMáy tính bức xạ chuốiMáy tính năng lượng Chuột HamsterMáy tính Tỷ lệ Lỗi Dịch chuyển Tức thờiMáy tính nấu gà bằng năng lượng động năngMáy tính lực nâng bóng bay HeliMáy tính Thời gian Sống sót ZombieTrình Kiểm Tra Kích Thước Thu Thập GooglebotMáy tính tỷ lệ bãi đỗ xeMáy tính Cây thông NoelMáy Tính Ngày Tận Thế Ma Cà RồngMáy tính giá trị PizzaMáy tính Quầy nước chanhTrình tạo tiểu bang Mỹ ngẫu nhiênTrình tạo lý do ngẫu nhiênTrình tạo hoạt động ngẫu nhiênTrình tạo công thức cocktail ngẫu nhiênCông cụ chọn phim ngẫu nhiênTrình tạo tên miền ngẫu nhiênTrình tạo siêu năng lực ngẫu nhiênTrình tạo Haiku ngẫu nhiênTrình tạo lời nhắc viết ngẫu nhiênTrình tạo IMEI Ngẫu nhiên