Máy tính Định lý Số dư Trung Quốc

Chào mừng bạn đến với Máy tính Định lý Số dư Trung Quốc, một công cụ lý thuyết số mạnh mẽ giúp giải các hệ phương trình đồng dư đồng thời bằng Định lý Số dư Trung Quốc (CRT). Cho dù bạn đang học số học mô-đun, chuẩn bị cho các kỳ thi toán học, làm việc trên các bài toán mã hóa hay khám phá lý thuyết số, máy tính này cung cấp một lời giải đầy đủ từng bước với hình ảnh trực quan tương tác cho thấy các lớp đồng dư căn chỉnh tại nghiệm duy nhất như thế nào.

Định lý Số dư Trung Quốc là gì?

Định lý Số dư Trung Quốc (CRT) là một kết quả cơ bản trong lý thuyết số đảm bảo sự tồn tại và tính duy nhất của một nghiệm cho một hệ phương trình đồng dư đồng thời, với điều kiện các mô-đun nguyên tố cùng nhau từng đôi một. Định lý được mô tả lần đầu tiên bởi nhà toán học Trung Quốc Tôn Tử (孫子) trong tác phẩm Tôn Tử Toán Kinh (孫子算經) vào khoảng thế kỷ thứ 3 CN.

Về mặt hình thức, cho hệ phương trình:

Nếu tất cả các mô-đun \(m_1, m_2, \ldots, m_k\) là nguyên tố cùng nhau từng đôi một (tức là \(\gcd(m_i, m_j) = 1\) với mọi \(i \neq j\)), thì tồn tại một nghiệm duy nhất \(x\) theo mô-đun \(M = m_1 \times m_2 \times \cdots \times m_k\).

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

Chứng minh mang tính xây dựng cung cấp thuật toán được sử dụng bởi máy tính này:

Bước 1: Tính M

Tính tích của tất cả các mô-đun:

Bước 2: Tính từng Mᵢ

Đối với mỗi phương trình đồng dư \(i\), tính \(M_i = M / m_i\). Đây là tích của tất cả các mô-đun ngoại trừ \(m_i\).

Bước 3: Tìm Nghịch đảo Mô-đun

Đối với mỗi \(i\), tìm \(y_i\) sao cho \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) bằng cách sử dụng Thuật toán Euclid mở rộng. Vì \(M_i\) và \(m_i\) nguyên tố cùng nhau (tất cả các mô-đun đều nguyên tố cùng nhau từng đôi một), nghịch đảo này luôn tồn tại.

Bước 4: Xây dựng Nghiệm

Nghiệm tổng quát là \(x + k \cdot M\) với mọi số nguyên \(k\), nghĩa là nghiệm lặp lại sau mỗi \(M\) số nguyên.

Cách sử dụng Máy tính này

1. Nhập các phương trình đồng dư của bạn: Đối với mỗi phương trình \(x \equiv a \pmod{m}\), nhập số dư \(a\) và mô-đun \(m\). Bắt đầu với 2 phương trình và nhấp vào "Thêm phương trình" để thêm nhiều hơn (tối đa 10).
2. Kiểm tra các mô-đun: Tất cả các mô-đun phải là số nguyên dương ≥ 2 và nguyên tố cùng nhau từng đôi một. Máy tính xác minh điều này tự động.
3. Nhấp vào "Giải hệ phương trình": Máy tính áp dụng thuật toán CRT và hiển thị nghiệm duy nhất cùng với các bước thực hiện.
4. Xem lại trực quan hóa: Trục số cho thấy cách các lớp đồng dư từ mỗi phương trình giao nhau tại nghiệm.
5. Xác minh: Phần xác minh xác nhận nghiệm thỏa mãn mọi phương trình đồng dư ban đầu.

Hiểu kết quả

• Nghiệm không âm nhỏ nhất (x₀): Nghiệm duy nhất trong phạm vi [0, M−1]
• Nghiệm tổng quát: Tất cả các số nguyên có dạng x₀ + kM với k là số nguyên bất kỳ
• Bảng xác minh: Xác nhận x₀ mod mᵢ = aᵢ cho mỗi phương trình đồng dư
• Phân tích từng bước: Hiển thị Mᵢ, nghịch đảo mô-đun yᵢ và tổng riêng phần aᵢ·Mᵢ·yᵢ cho mỗi phương trình
• Trục số: Đại diện trực quan về cách các lớp thặng dư căn chỉnh tại nghiệm

Ứng dụng của Định lý Số dư Trung Quốc

Bài toán Tôn Tử cổ điển

Bài toán ban đầu trong Tôn Tử Toán Kinh hỏi: "Có những vật không biết số lượng. Đếm theo bộ ba thì thừa hai; đếm theo bộ năm thì thừa ba; đếm theo bộ bảy thì thừa hai. Hỏi có bao nhiêu vật?"

Bài toán này dịch sang: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Sử dụng CRT, câu trả lời là x = 23 (và tổng quát hơn là 23 + 105k cho bất kỳ số nguyên không âm k nào).

Khi nào CRT không áp dụng?

• Các mô-đun không nguyên tố cùng nhau: Nếu bất kỳ cặp mô-đun nào chia sẻ một thừa số chung lớn hơn 1, CRT tiêu chuẩn không đảm bảo một nghiệm. Một nghiệm vẫn có thể tồn tại nếu các số dư tương thích, nhưng máy tính này yêu cầu các mô-đun nguyên tố cùng nhau từng đôi một cho thuật toán tiêu chuẩn.
• Một phương trình đồng dư duy nhất: CRT yêu cầu ít nhất 2 phương trình đồng dư. Một phương trình đơn lẻ \(x \equiv a \pmod{m}\) đã có nghiệm hiển nhiên x = a.

Thuật toán Euclid mở rộng

Thuật toán Euclid mở rộng rất cần thiết cho CRT vì nó tìm thấy nghịch đảo mô-đun. Cho các số nguyên \(a\) và \(b\), nó tìm các số nguyên \(x\) và \(y\) sao cho:

Khi \(\gcd(a, b) = 1\), thì \(x\) là nghịch đảo mô-đun của \(a\) theo mô-đun \(b\), tức là \(a \cdot x \equiv 1 \pmod{b}\).

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

Định lý Số dư Trung Quốc là gì?

Định lý Số dư Trung Quốc (CRT) phát biểu rằng nếu bạn có một hệ phương trình đồng dư đồng thời x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), trong đó tất cả các mô-đun nguyên tố cùng nhau từng đôi một, thì tồn tại một nghiệm duy nhất theo mô-đun M = m₁ × m₂ × ... × mₖ. Định lý này được mô tả lần đầu tiên bởi nhà toán học Trung Quốc Tôn Tử vào thế kỷ thứ 3.

Nguyên tố cùng nhau từng đôi một nghĩa là gì?

Nguyên tố cùng nhau từng đôi một có nghĩa là mọi cặp mô-đun không chia sẻ thừa số chung nào khác ngoài 1. Ví dụ, {3, 5, 7} nguyên tố cùng nhau từng đôi một vì gcd(3,5)=1, gcd(3,7)=1 và gcd(5,7)=1. Tuy nhiên, {4, 6, 5} KHÔNG nguyên tố cùng nhau từng đôi một vì gcd(4,6)=2.

Làm thế nào để giải một hệ phương trình đồng dư từng bước một?

Để giải bằng CRT: (1) Xác minh tất cả các mô-đun nguyên tố cùng nhau từng đôi một. (2) Tính M = tích của tất cả các mô-đun. (3) Đối với mỗi phương trình đồng dư, tính Mᵢ = M/mᵢ. (4) Tìm nghịch đảo mô-đun yᵢ của Mᵢ theo mô-đun mᵢ bằng Thuật toán Euclid mở rộng. (5) Tính nghiệm x = Σ(aᵢ × Mᵢ × yᵢ) mod M. Nghiệm tổng quát là x + k×M với mọi số nguyên k.

Các ứng dụng của Định lý Số dư Trung Quốc là gì?

CRT có nhiều ứng dụng thực tế: Mã hóa RSA sử dụng CRT để giải mã hiệu quả. Khoa học máy tính sử dụng nó cho số học số lớn bằng cách chia nhỏ các phép tính thành các phần mô-đun nhỏ hơn. Xử lý tín hiệu áp dụng CRT trong các mã sửa lỗi. Các bài toán lập lịch và lịch trình nơi các sự kiện lặp lại ở các khoảng thời gian khác nhau cũng sử dụng CRT.

Điều gì xảy ra nếu các mô-đun không nguyên tố cùng nhau?

Nếu các mô-đun không nguyên tố cùng nhau từng đôi một, Định lý Số dư Trung Quốc tiêu chuẩn không áp dụng trực tiếp. Trong một số trường hợp, nghiệm vẫn có thể tồn tại nếu đáp ứng các điều kiện tương thích nhất định (số dư phải nhất quán theo mô-đun ƯCLN của các mô-đun không nguyên tố cùng nhau). Tuy nhiên, nếu không có nghiệm nào tồn tại, hệ phương trình đồng dư là không nhất quán.

Tài nguyên bổ sung

• Định lý Số dư Trung Quốc - Wikipedia
• Thuật toán Euclid mở rộng - Wikipedia