Thuật toán Euclide và phương trình Diophante

Thuật toán Euclide và phương trình Diophante
Định lý 1: phương trình (1) có nghiệm nguyên khi và chỉ khi A,B nguyên tố cùng nhau.
Định lý 2: phương trình (1) có nghiệm nguyên là (x0,y0) thì có vô số nghiệm nguyên đó là tập nghiệm có dạng x=x0+B*t
                                     y=y0-A*t
(không chứng minh định lý)
Xét ví dụ: USCLN (162,47) theo thuật toán chia Euclide.
USCLN(162,47)=1 ta phân tích như sau:
162=47*3+21
47=21*2+5
21=5*4+1
Vậy USCLN(162,47)=1. Khi đó ta có thể viết 162/47=3+21/47(a)
47/21=2+5/21   (b)
21/5=4+1/5 (c)
Từ (a) suy ra 162/47=3+1/(47/21). Thay (b) vào (a) ta được 162/47=3+1/(2+1/(21/5))
Thay 21/5 vào ta được 162/47=3+1/(2+1/(4+1/5)) (d) do vậy ta có thể phân tích   phân số A/B như sau:
A/B=q0+1/(q1+1/(q2+1/(...+1/qn)...))
Cách phân tích như vậy gọi là liên phân số với qi nguyên dương (i thuộc N và qn>1).
Khi đó ta ký hiệu A/B={q0;q1,q2,...,qn}   (1.1)
Ta gọi dm=Pm/Qm gọi là giản phân bậc m của liên phân số A/B với:
Pm = qm*Pm-1+Pm-2
Qm = qm*Qm-1+Qm-2
2<=m<=n (1.2)
Nhận thấy giản phân bậc 0 d0 = P0/Q0 = q0
Giản phân bậc 1  d1 = P1/Q1 =(q1*q0+1)/q1 =q0+1/q1 ={q0;q1}
Qua phép quy nạp ta có dm ={q0;q1,q2,...,qm}là giản phân bậc m.
Từ (1.2) suy ra Pm-1*Qm-Qm-1*Pm =Pm-1*Qm-2-Qm-1ư*Pm-2.
Pm-1*Qm-Qm-2*Pm =-(Pm-2*Qm-1-Pm-1*Qm-2)
Đặt Dm =Pm-1*Qm-Qm-2*Pm
Nhận thấy Dm =-Dm-1 khi đó D1 =-1, D2 =1, D3 =-1. Tổng quát Dm =(-1)m
Nghĩa là: Pm-1*Qm-Pm*Qm-1 =(-1)m      (1.3)
Nhận xét: Từ (1.3) ta có Pm và Qm nguyên tố cùng nhau và mọi giản phân đều là những phân số tối giản. Do đó nếu A/B là phân số tối giản (A,B nguyên tố cùng nhau) và Pn/Qn là phân số cuối cùng của phép