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

Tháng Tám 23, 2016Tháng Tám 23, năm 2016 huynhduyidolchinese remainder theorem, crt, diophante, inveres modulo, math, num theory

Tác giả: Huỳnh Văn Duy

Có thể nói trong lập trình thống kê giám sát thì những bài toán về số học tập chiếm một trong những phần khá lớn. Trong đó, trong những thuật toán được biết đến nhiều tuyệt nhất là giải mã euclid mở rộng, thuật toán này rất có thể giải quyết không hề ít bài toán tương quan đến số học. Nên bây giờ chúng ta sẽ mày mò về nó.

Bạn đang xem: Thuật toán euclid mở rộng

ĐẦU TIÊN TA CẦN TÌM HIỂU MỘT CHÚT VỀ THUẬT TOÁN EUCLID NGUYÊN THỦY

Lịch sử thuật toán Euclid:

Thuật toán Euclid là trong những thuật toán cổ nhất được biết thêm đến, từ lúc nó xuất hiện trong cuốn Euclid’s Elements khoảng tầm năm 300 trước công nguyên. Euclid mở đầu đã trình bày rõ ràng vấn đề về góc nhìn hình học, như vụ việc tìm ra một thước đo thông thường cho độ dài hai tuyến đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn. Mặc dù nhiên, thuật toán đã đa số không được phát hiện tại ra vày Euclid và nó đã có thể được biết đến sớm hơn 200 năm. Nó cũng đã được nghe biết bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên).

Mô tả thuật toán:

Cho 2 số tự nhiên và thoải mái a và b, ko đồng thời bằng 0: chất vấn nếu b bởi 0, thì a là mong chung lớn số 1 (UCLN). Giả dụ không, lặp lại xử lý thực hiện b cùng phần còn lại sau thời điểm lấy a phân chia cho b. Phần còn lại sau thời điểm chia a đến b thường xuyên được viết là a mod b.

Các thuật toán này hoàn toàn có thể sử dụng trong bất kì hoàn cảnh nào lúc còn phần dư. Điều này bao gồm các nhóm nhiều thức như đội số nguyên Gauxơ. Thuật toán không những áp dụng đến số tự nhiên và thoải mái mà còn vận dụng cho những trường hợp tổng thể khác sẽ được mô tả chi tiết sau.

Xem thêm: Cô Nàng Bướng Bỉnh - Co Nang Buong Binh Tap 11

Thuật toán có thể được thiết lập rất 1-1 giản:

#include #include using namespace std;#define builtin_gcd __gcdint gcd(int a, int b) if(b==0) return a; else return gcd(b,a%b);int main(){ cout

Dĩ nhiên, ngôn từ lập trình C++ cũng cung ứng cho bọn họ một hàm tất cả sẵn nhằm tìm mong chung lớn số 1 của hai số bởi thuật toán euclid, đó là hàm __gcd(a, b) đang trả về mong chung lớn số 1 của hai số a và b.

THUẬT TOÁN EUCLID MỞ RỘNG

Phương trình diophantine:

(1)

Theo định lí Bézout (Bézout’s indentify): đến hai số nguyên a, b lúc đó luôn luôn tồn tại nhị số x, y chang cho:

Người ta cũng chứng tỏ được phương trình trên gồm nghiệm khi và chỉ còn khi gcd(a, b) = c. Và như thế có nghĩa là phương trình diophante rất có thể có rất nhiều nghiệm, cùng từ từng một nghiệm ta hoàn toàn có thể sinh ra đầy đủ nghiệm khác.

Định nghĩa số nguyên k sao cho:

. Phân tách vế theo vế phương trình đến ta được phương trình mới

Dễ thấy

với đó là một nghiệm của phương trình (1). đưa sử là 1 trong nghiệm khác của phương trình (1), ta có:

Suy ra:

(3), nghĩa là a là ước của , và là mong của . Yêu cầu ta có: cùng với r là một số nguyên. Nạm vào (3), ta được:

Trong đó:

hay

Như vây, trường hợp

tất cả một nghiệm bất kì thì tất cả các nghiệm sẽ có được dạng:

Ví dụ: Tìm tất cả các nghiệm của phương trình

.

Xem thêm: Bảng Báo Cáo Kết Quả Hoạt Đông Kinh Doanh Của Công Ty, Bảng Báo Cáo Kết Quả Hoạt Động Kinh Doanh

Đầu tiên, ta xét , do cần phương trình chắc chắn rằng có nghiệm.Áp dụng thuật toán Euclid, ta có:Bây giờ, ta tra cứu cách biểu diễn 3 bằng một quan hệ tuyến tính thân 258 với 147. Dựa vào trên, ta có:Tiếp theo, ta viết , với nhân phương trình mang đến 123 vì . Ta được:.Vậy một nghiệm của phương trình là: , và những nghiệm khác gồm dạng:

Cài đặt cầm thể:

// Extended euclid solve diophantine linear equation#include #define x first#define y secondusing namespace std;typedef long long ll;typedef pair ii;ll a, b, c;ii extended_gcd(ll a, ll b) if (b == 0) return ii(1, 0); ii qr = ii(a / b, a % b); ii st = extended_gcd(b, qr.y); return ii(st.y, st.x - qr.x*st.y);void extended_gcd2(ll a, ll b, ll &X, ll &Y) // another version ll d = __gcd(a, b); ll m = a, n = b; ll xm = 1; // (ym = 0) m = a = a*1 + b*0 ll xn = 0; // (yn = 1) n = a = a*0 + b*1 while (n) ll q = m / n; ll r = m - q*n; ll xr = xm - q*xn; m = n, xm = xn; n = r, xn = xr; X = xm * (c/d); Y = ((d - a*xm) / b) * (c/d);int main() freopen("in.txt", "r", stdin); scanf("%lld %lld %lld", &a, &b, &c); ll d = __gcd(a, b); ii ex = extended_gcd(a, b); printf("%lld %lldn", c/d*ex.x, c/d*ex.y); ll X, Y; extended_gcd2(a, b, X, Y); printf("%lld %lldn", X, Y); assert(c/d*ex.x == X && c/d*ex.y == Y); return 0;NGHỊCH ĐẢO MODULO

Một trong số những ứng dụng đặc trưng nhất của thuật toán Euclid không ngừng mở rộng đó đó là dùng để tìm nghịch hòn đảo modulo:

Nhận xét: nếu , giải phương trình

Ta có:

Khi kia

được call là nghịch hòn đảo của a theo modulo m (ký hiệu )

Ví dụ: a = 7, m = 10, Xét phương trình

Nghiệm

Khi đó:

TỔNG KẾT:

Thuật toán Euclid mở rộng hoàn toàn có thể dùng nhằm giải phương trình Diophantine Họ nghiệm của phương trình Diophantine khi đã gồm nghiệm x, y là:

BONUS: ĐỊNH LÍ THẶNG DƯ trung hoa (CHINESE REMAINDER THEOREM)

Định lý thặng dư nước trung hoa là tên bạn phương tây đặt mang lại định lý này. Người china gọi nó là việc Hàn Tín điểm binh. Hàn Tín là 1 danh tướng tá thời Hán Sở, từng được phong tước vương thời Hán Cao Tổ giữ Bang đang dựng nghiệp. Sử ký tứ Mã Thiên viết rằng Hàn Tín là tướng mạo trói con gà không nổi, nhưng rất có tài quân sự. Tương truyền rằng khi Hàn Tín điểm quân số, ông mang đến quân bộ đội xếp sản phẩm 3, sản phẩm 5, mặt hàng 7 rồi báo cáo số dư. Từ đó ông tính đúng chuẩn quân số cho từng người.

Gần đây, định lý số dư Trung Quốc có tương đối nhiều ứng dụng trong số bài toán về số nguyên lớn vận dụng vào triết lý mật mã. – Wikipedia

Bản hóa học của câu hỏi Hàn Tín điểm binh là giải phương trình đồng dư nhảy nhất được tế bào tả tổng quát như sau: