Giải thích giúp Giải thuật Euclid (tìm ƯSCLN)

[duoirong]

Mình có bài tập tìm ƯSCLN(a,b), mình search trên mạng thì tìm thấy thuật toán Euclid, có đoạn như thế này :

Tính ước số chung lớn nhất của 91 và 287.

Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:

287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)

Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:

91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)

Cuối cùng ta có: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).

bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14.
Cái này là dựa trên cơ sở toán học nào ? Mình nghĩ mãi mà không hiểu .


Mong các bác giải thích giúp. Cám ơn !



p/s: câu "...chia hết bởi..." là gì ?

[zkday2686]

1 - Bạn nhìn xuống cái "bổ đề" ở ngay dưới đó là hiểu mà
2 :
a chia hết bởi b ===> b%a == 0;

[duoirong]

ý mình là vì sao khi r # 0 thì : ƯSCLN(a,b)=ƯSCLN(b,r)


//cái "chia hết bởi" nghe có vẻ khó hiểu quá .
a chia hết bởi b : mình hiểu thì a là số bị chia, b là số chia.

khó quá !

[QuangHoang]

ý mình là vì sao khi r # 0 thì : ƯSCLN(a,b)=ƯSCLN(b,r)


//cái "chia hết bởi" nghe có vẻ khó hiểu quá .
a chia hết bởi b : mình hiểu thì a là số bị chia, b là số chia.

khó quá !

UCLN là số lớn nhất mà cả a và b cùng chia hết cho nó.

c là UCLN của 287 và 91 thì người ta nói. c được chia hết bởi 287 và 91. Và tất nhiên c cũng được chia hết bởi 91 và 14

Vậy dễ hiểu chứ bạn. Còn code thứ 2 trong chữ kí của mình chính là hàm tìm UCLN áp dụng thuật toán này đấy.

[duoirong]

c là UCLN của 287 và 91 thì người ta nói. c được chia hết bởi 287 và 91. Và tất nhiên c cũng được chia hết bởi 91 và 14.

Nếu c được chia hết bởi 287 và 91 thì cơ sở nào ta có thể kết luận c cũng được chia hết bởi 91 và 14. , 14 là số dư của phép chia 287/91 chẳng thấy gì liên quan cả .

em mới học C mà gặp cái code của anh thì ... đi ngũ luôn .

[meoconlongvang]

Mèng ơi, cần chứng minh thuật toán chi cho mệt vậy ko biết. Chuyện đó đã có mấy ông nhà toán học hói đầu lo. Cả mấy thế kỷ nay chưa nghe ai bác bỏ gì cả. Tụi mình là dân tin học thì cứ vui vẻ lấy thuật toán đó mà áp dụng thôi.

[QuangHoang]

Ẹc, mình sẽ chứng minh lại cho bạn, chán bạn quá, cái này là toán thuần túy đấy.

c là UCLN của a và b;

-> a chia hết cho c <=> a=c*i;
và b chia hết cho c <=> b=c*j;

vì c là UCLN nên i/j là phân số tối giản.

Coi như a> b đi cho máu a= b*k + m;

Cần chứng minh m chia hết cho c và sẽ có một phân số tối giản nào đó nữa.

Thay vào nhau: c*i = c*j*k + m <=> m = c*(i+j*k); <=> m chia hết cho c
(i+j*k)/j = i/j +k vậy là thằng này cũng tối giản.

Tất cả một mớ linh tinh cho thấy, c là UCLN của m và b

Đọc cái trên nếu bạn còn không hiểu thì công nhận luôn đi cho nhanh.

[duoirong]

ah' ah' hay quá .

Nhưng mà m = c(i-jk) mới đúng chứ anh,
tiếp theo là chứng minh (i-jk) & j là 2 số nguyên tố cùng nhau { (i-jk)/j tối giản}.

(i - jk)/j = i/j - k { i/j tối giản }


Hỏi 1 xíu nữa anh ơi , vì sao i/j tối giản thì i/j - k cũng là 1 phân số tối giản ???



//Em có tìm thấy 1 bài viết về ƯSCLN như sau :

Thuật Toán Euclid:
Không biết có nên gọi thuật toán này là định lý hay không?
Ước chung lớn nhất giữa 2 số a và b:

nếu a >b, thì lấy a:b.
+ Nếu phần dư bằng 0, thuật toán đến đây kết thúc vì chia hết.
+ Nếu phần dư khác 0, thì lấy b chia cho phần dư (làm được vì b lớn hơn phần dư. =>hiển nhiên).
Và cứ thế tiếp tục.
Tại sao ta có điều này: ta nhìn thử phần sau:

a = H[1]*b + M [1] (a chia b được H[1] dư M[1])
b = H[2]*M1 + M[2] (b chia M[1] được H[2] dư M[2])
M[1] = H[3]*M[2] +M[3]
.
.
.
.
cứ thế tiếp tục, đến phần tử thứ k là kết thúc thì:
M[k-2] = H[k]*M[k-1] + 0.

nếu ta thay kết quả này trở ngược lên trên thì sẽ thấy:
M[k-3] = H[k-1]*M[k-2] + M[k-1] = H[k-1]*H[k]*M[k-1] + M[k-1] = (H[k-1]*H[k]+1)*M[k-1]

(H[k-1]*H[k]+1) là một số nguyên, và cứ thế tiếp tục ta sẽ thấy a và b đều viết được dưới dạng một số nguyên nhân với M[k-1], có nghĩa là:
a = n*M[k-1]
b = m*M[k-1]
=> Bài toán đến đây là gần kết thúc rồi, chỉ việc chứng minh thêm một điều là n với m là 2 số nguyên tố cùng nhau(giữa chúng không có ước số chung khác 1.) => kết thúc.

cả 2 bài toán đều phải cm 2 số là nguyên tố cùng nhau, tới đây thì bí rồi .

[rox_rook]

Mèng ơi, cần chứng minh thuật toán chi cho mệt vậy ko biết. Chuyện đó đã có mấy ông nhà toán học hói đầu lo. Cả mấy thế kỷ nay chưa nghe ai bác bỏ gì cả. Tụi mình là dân tin học thì cứ vui vẻ lấy thuật toán đó mà áp dụng thôi.

- Không có toán là sao có thuật toán hả mèo ?
- Số học liên quan đến lập trình rất nhiều, cố mà làm cho quen đi cậu

[meoconlongvang]

- Không có toán là sao có thuật toán hả mèo ?
- Số học liên quan đến lập trình rất nhiều, cố mà làm cho quen đi cậu

Mình ko có ý bác bỏ toán học, tuy nhiên mình thích công nhận và áp dụng hơn là chứng minh