Giải phương trình nghiệm nguyên dạng ax+by

a. Câu gcd dễ mà, UCLN(a, b) = UCLN(a-b, b).
b. Cái này tự suy dễ hơn là post lên áp dụng ngay chính thuật toán vừa nêu. Này nhé, bạn trừ theo đó sẽ ra UCLN, vậy thì phải trừ bao nhiêu lần mới ra được? Chính nó đấy còn đâu nữa.

anh nói rõ hơn giúp được ko em mới nhập môn với do hơi ngu toán :3

Gợi ý cho lần này nữa thôi nhé:

a = 1a + 0b
b = 0a + 1b

Có vô số cặp số (x, y) thoả mãn câu 2. Thuật toán dưới đây giúp tìm ra 1 cặp số.

k = ucln(a, b);
ta có a = km, b = kn
=> Đề bài chuyển thành tìm x và y sao cho
k = kmx + kny (k, m, n đã biết)
=> mx + ny = 1
=> x + ny/m = 1/m
=> x = (1-ny)/m
cho y chạy từ 1 chạy lên đến khi x là số nguyên, trả về kết quả (x, y)

Đây là phương thức viết bằng C# mình vừa test:

int[] Cau2(uint a, uint b)
{
    if (a == 0)
        return new int[] { 0, 1 };
    if (b == 0)
        return new int[] { 1, 0 };
    var k = UCLN(a, b);
    var m = a / k;
    var n = b / k;
    var y = 1;
    while ((1 - n * y) / m != ((double)1 - (double)n * (double)y) / (double)m)//kiểm tra tính nguyên của (1-ny)/m
        y += 1;
    var x = (1 - n * y) / m;
    return new int[] { (int)x, y };
}

^ Mò kiểu này là O(n), trong khi thớt đã giải theo UCLN O(logn) rồi, giờ ghép thêm vào nữa thôi

Có thử làm theo nhưng làm chưa được, tự dưng nghĩ ra cách này nên trước mắt làm cái đã

Mà đã mò rồi thì ax = k (mod b) sẽ chỉ toàn dùng số nguyên. Số thực có thể không làm tròn đúng.

Câu 1. gcd(a,b) lớn hơn hoặc bằng 1 và không quá a, b. Do vậy có thể làm vòng lặp theo một biến i từ a về 1. Mỗi lần lặp, kiểm tra xem a và b có cùng chia hết cho i không - nếu có thì trả về và đó chính là ước chung lớn nhất.
Câu 2. Câu này thì mình xài luôn công thức nghiệm (tìm được trong một quyển sách số học) nên không tối ưu đâu, khối lượng tính toán nhiều nữa.
Chia cả hai vế cho gcd(a,b) thì được phương trình cx + dy = 1. Theo định nghĩa của ước chung lớn nhất thì c, d nguyên tố cùng nhau.
Chọn nghiệm c = d^(phi© - 1) và d = (d^phi© - 1)/c . Trong đó phi(n) là số các số nguyên dương bé hơn n và nguyên tố cùng nhau với n.
Phương trình ax + by = c nếu có nghiệm (x_0,y_0) thì (x_0+bt,y_0-at) cũng là nghiệm - chỉ cần tìm được một nghiệm là kết luận được nó có vô số nghiệm.
Định lý. Phương trình ax + by = c có nghiệm khi và chỉ khi c chia hết cho ước chung lớn nhất của a và b.

Đó là công thức cho RSA với modulo đã biết trước bạn ạ.

Tìm hiểu thêm thuật toán extend_gcd để tìm 1 nghiệm của pt trên

Câu 1. gcd(a,b) lớn hơn hoặc bằng 1 và không quá a, b. Do vậy có thể làm vòng lặp theo một biến i từ a về 1. Mỗi lần lặp, kiểm tra xem a và b có cùng chia hết cho i không - nếu có thì trả về và đó chính là ước chung lớn nhất.

Cách này lâu quá bạn ơi :v dùng luôn thuật toán Euclid chỉ mất O(log n) thôi.