Fotools
vi

Công Cụ Giải Phương Trình Đồng Dư

Tham Số Đầu Vào

Ví Dụ Nhanh:

Kết Quả Tính Toán

Nhập tham số và nhấn "Giải Phương Trình"

Giải Thích Thuật Toán:

1. Phương trình đồng dư tuyến tính ax ≡ b (mod m):
  • Điều Kiện Có Nghiệm:Phương trình có nghiệm khi và chỉ khi gcd(a, m) chia hết b (tức là b chia hết cho gcd(a, m))
  • Số Lượng Nghiệm:Nếu có nghiệm, phương trình có đúng d = gcd(a, m) nghiệm phân biệt theo modulo m
  • Phương Pháp Giải:
    1. Tính d = gcd(a, m)
    2. Kiểm tra d có chia hết b không; nếu không thì vô nghiệm
    3. Chia cả hai vế cho d: (a/d)x ≡ (b/d) (mod m/d)
    4. Dùng thuật toán Euclid mở rộng để tìm nghịch đảo của a/d theo modulo m/d'
    5. Tính x₀ = a' × (b/d) mod (m/d)
    6. Nghiệm tổng quát: x = x₀ + k(m/d), với k = 0, 1, ..., d-1
2. Phương trình đồng dư mũ a^x ≡ b (mod m) (Bài toán Logarithm Rời Rạc):
  • Mô tả bài toán:Cho a, b, m, tìm số nguyên không âm nhỏ nhất x sao cho a^x ≡ b (mod m)
  • Điều Kiện Có Nghiệm:
    • Nếu gcd(a, m) = 1 và b là phần tử của nhóm vòng sinh bởi a theo modulo m thì có nghiệm
    • Phương pháp kiểm tra: liệt kê các lũy thừa của a cho đến khi tìm thấy b hoặc hoàn thành một chu kỳ
  • Phương Pháp Giải:
    • Tìm kiếm vét cạn trong phạm vi nhỏ:Liệt kê x = 0, 1, 2, ... cho đến khi tìm được nghiệm hoặc đạt giới hạn tìm kiếm
    • Thuật toán Baby-step Giant-step:Độ phức tạp O(√m), phù hợp với bài toán cỡ vừa
    • Thuật toán Pollard's rho:Áp dụng cho modulus nguyên tố lớn
  • Tính Tuần Hoàn:Nếu x₀ là nghiệm thì x = x₀ + kφ(m) cũng là nghiệm (φ(m) là hàm Euler)
3. Ứng dụng thực tế:
  • Mật mã học:RSA, trao đổi khóa Diffie-Hellman, mã hóa ElGamal
  • Nghiên cứu lý thuyết số:Căn nguyên thủy, Thặng dư bậc hai, Định lý phần dư Trung Hoa
  • Sinh Số Ngẫu Nhiên:Bộ sinh số ngẫu nhiên tuyến tính (LCG)
  • Hàm Băm:Ứng dụng số học modular trong bảng băm
  • Lập Trình Thi Đấu:Lũy thừa nhanh, nghịch đảo modular, bài toán lý thuyết số

Độ Phức Tạp Thuật Toán:

  • Phương trình đồng dư tuyến tính:O(log m) (độ phức tạp của thuật toán Euclid mở rộng)
  • Phương trình đồng dư mũ (vét cạn):O(n), với n là giới hạn tìm kiếm
  • Phương trình đồng dư mũ (BSGS):O(√m), cần thêm bộ nhớ

Các Định Lý Quan Trọng:

  • Định Lý Bézout:Phương trình ax + my = gcd(a, m) luôn có nghiệm nguyên
  • Định Lý Fermat Nhỏ:Nếu p là số nguyên tố và gcd(a, p) = 1, thì a^(p-1) ≡ 1 (mod p)
  • Định Lý Euler:Nếu gcd(a, m) = 1, thì a^φ(m) ≡ 1 (mod m)
  • Định Lý Phần Dư Trung Hoa:Có thể giải hệ phương trình đồng dư