Евклидийн алгоритмын олон хувилбар байдаг. Жишээ нь ХИЕХ(f, g)-гээс гадна f*u+g*υ=ХИЕХ(f, g) байх u, υ бүхэл тоонуудыг олж болно. Энэ нь k*x+l*y=m гэсэн тэгшитгэлийн ямар нэг бүхэл тоон шийдийг олоход хэрэгтэй. Энд k, l, m нь бүхэл тоо ба k, l нь нэг зэрэг тэгтэй тэнцүү биш, m нь d=ХИЕХ(|k|, |l|)-д хуваагддаг тоо байна. k*|u|+l*|υ|=d байг. Тэгвэл |k|*u*m/d+|l|*υ*m/d=m болох ба үүнээс k*(c1*u*m/d)+l*(c2*υ*m/d)=m гэж гарна. Энд cj нь -1 эсвэл 1 утгатай байна (j=1, 2). f*u+g*υ=ХИЕХ(f, g) байх u, υ бүхэл тоонуудыг олох алгоритмыг тайлбарлая. f-ийг f0-оор, g-г f1-ээр түр тэмдэглэе. Евклидийн алгоритмыг хэрэглэх үед үүсэх үлдэгдлүүдийг f2, ..., fn-ээр, f0-г f1-д, f1-г f2-д, ..., fn-1-г fn-д хуваасны бүхэл хэсгийг a1, a2, ..., an гэж тэмдэглэж болно:
f0=a1*f1+f2,
f1=a2*f2+f3,
...
f_{n-2}=a_{n-1}*f_{n-1}+fn,
f_{n-1}=an*fn;
Энд ХИЕХ(f0, f1)=fn. Ямар нэг i ≤ n-2 тооны хувьд fi, fi+1 тоонуудаас гадна f0*p+f1*q=fi, f0*s+f1*t=fi+1 байх p, q, s, t коэффициентүүд нь мэдэгдэж байг. Иймд бид fi-г f_{i+1}-д хувааж бүхэл хэсэг a_{i+1} болон үлдэгдэл f_{i+2}-г олсны дараа f_{i+2}-т харгалзах коэффициентүүдийг олж чадна. Учир нь fi-a_{i+1}*f_{i+1}=f_{i+2} тул f0*(p-a_{i+1}*s)+f1*(q-a_{i+1}*t)=f_{i+2} юм.
Иймд f*u+g*υ=ХИЕХ(f, g) байх u, υ бүхэл тоонуудыг олохын тулд f, g тоонууд дээр Евклидийн алгоритмыг хэрэглэх явцдаа алхам бүрд өмнөх алхмынхаа хоёр тоог хадгалахаас гадна эдгээр тоонд харгалзах коэффициентүүд болох p, q, s, t тоонуудыг хадгалж байх хэрэгтэй болж байна. Эхний алхамд f, g тоонуудад харгалзах коэффициентүүдийг харгалзан 1, 0 болон 0, 1 гэж авна. Хуваалт хийгээд бүхэл хэсэг а болон ямар нэг тэгтэй тэнцүү биш үлдэгдэл олсны дараа үлдэгдлийнхээ коэффициентүүдийг p-a*s, q-a*t томъёонуудаар олно. Хамгийн сүүлийн тэг биш үлдэгдэлд харгалзах коэффициентүүд нь f*u+g*υ=ХИЕХ(f, g) тэгшитгэлийн шийдүүд болно.
No comments:
Post a Comment