Евклидийн алгоритм

Эерэг бүхэл a>b тоонуудын хувьд

a=bq+r, \qquad 0\leq r<b

байг. Мөн a,b тоонуудын хамгийн их ерөнхий хуваагчийг \mathrm{gcd}(a,b) гэж тэмдэглэе. Хэрэв r=0 бол \mathrm{gcd}(a,b)=b байх нь тодорхой. Нөгөө талаас хэрэв r>0 бол

\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)

байна. Учир нь a,b хоёуланг хуваадаг тоонууд мөн r-ийг хуваах ба b,r хоёуланг хуваадаг тоонууд мөн a-г хуваана. Евклидийн алгоритм нь энэ процессийг 0 үлдэгдэл өгтөл нь давтаж \mathrm{gcd}(a,b)-г олох алгоритм юм. Дээрх (a,b) хосоос (b,r) хосыг гаргах үйлдлийг (b,r)=E(a,b) гэвэл, Евклидийн алгоритмийг (r_n,0)=E^n(a,b) гэж бичиж болох ба эндээс \mathrm{gcd}(a,b)=r_n байхыг харж болно. Одоо энэ алгоритм нь төгсгөлөг алхмын дараа зогсоно гэдгийг харуулъя. Үүний тулд r_0=a ба r_1=b гэсэн тэмдэглэгээг оруулбал r_i\neq0 үед

(r_i,r_{i+1})=E(r_{i-1},r_i) гэж бичиж болно.

Үлдэгдлийн чанараар i\geq1 үед r_{i}>r_{i+1}, өөрөөр хэлбэл r_1,r_2,\ldots нь эрс буурдаг сөрөг биш бүхэл тоон дараалал тул ямар нэг төгсгөлөг n-ийн хувьд r_{n+1}=0 болж алгоритм зогсоно.

Энэ алгоритмийн чанарыг ашиглан дараах чухал үр дүнгүүдийг баталж болно.

Безугийн лемм. Эерэг бүхэл a,b тоонуудын хувьд

ax+by=\mathrm{gcd}(a,b)

тэгшитгэл бүхэл шийдтэй.

Баталгаа. b|a үед баталгаа илэрхий тул Евклидийн алгоритм эхний давталтан дээрээ зогсдоггүй гэж үзье. Евклидийн алгоритмийн i дэх давталтыг

r_{i-1}=r_iq_i+r_{i+1} буюу r_{i+1}=r_{i-1}-q_ir_{i}

гэж бичиж болно. Өөрөөр хэлбэл r_{i+1} нь r_i ба r_{i-1} хоёрын бүхэл коэффициенттэй шугаман эвлүүлэг байна. Тэгэхээр индукцээр r_{n} нь r_1=b ба r_0=a хоёрын бүхэл коэффициенттэй шугаман эвлүүлэг болно.

Тэмдэглэл. Дурын тэг биш a,b бүхэл тооны хувьд \mathrm{gcd}(a,b)=\mathrm{gcd}(|a|,|b|) гэж тодорхойлбол дээрх лемм эдгээр тоонуудын хувьд мөн хүчинтэй болохыг хялбархан харж болно.

Дасгал. a ба n>1 бүхэл тоонууд харилцан анхны байх (ө.х. \mathrm{gcd}(a,n)=1) гарцаагүй бөгөөд хүрэлцээтэй нөхцөл нь

ax=1\quad (\mathrm{mod}\, n)

тэгшитгэл бүхэл шийдтэй байх явдал гэдгийг батал.

Анхны тоо гэдэгт 1-ээс их бөгөөд 1 болон өөрөөсөө өөр эерэг бүхэл тоонд хуваагддаггүй (ө.х. p>1 ба, k|p гэдгээс k=1 эсвэл k=p гэж гардаг p) бүхэл тоог ойлгоно.

Евклидийн лемм. Хэрэв a,b эерэг бүхэл тоонууд ба p анхны тооны хувьд p|ab бол p|a эсвэл p|b байна.

Баталгаа. Эсрэгээр нь p нь a тооны хуваагч биш гэж үзье. Тэгэхээр p нь анхны тоо учир a-тай харилцан анхны, ө.х. \mathrm{gcd}(p,a)=1 гэсэн үг. Безугийн лемм ёсоор

ax+py=1

байх x,y бүхэл тоонууд олдоно. Дээрх тэгшитгэлийн хоёр талыг b-ээр үржүүлбэл

abx+pby=b

болох ба p|ab учир тэнцэтгэлийн зүүн гар тал p-д хуваагдана.

Тэмдэглэл. Дээрх леммийг a,b эерэг бүхэл тоо болгоны хувьд үнэн байлгадаг тийм p тоо бүр анхны байна. Энд ямар ч анхны биш p тооны хувьд леммийг зөрчдөг a,b тоонууд олдоно гэж харуулахад хангалттай.

Advertisements
This entry was posted in Тооны онол, алгоритм, теорем and tagged , , . Bookmark the permalink.

2 Responses to Евклидийн алгоритм

  1. uug хэлдэг:

    harsan chine RSA algorithmuud sanaand orchloo.
    Er ni huvaah uildliig urjiheer yaj hiivel zohiltoi ve?
    jishee ni:
    C= A/B gesniig A*(1/B) geed B-gee yamar neg algorithmaar zadalmaar bdag(olon gishuunt esvel yamar neg tsuvaand)
    eniig mash “oiroltsoo&#8221;goor ooroor helbel aldaa baga baihaar herhen shiideh ve? material bval helj ogooch
    ene huvaah, vrjih argiig sudalj yavsaar Microsoft Office(Excel) ene tal deer muu boddogiig ajiglasan(matlabtai haritsuulahad).

Хариулт үлдээх

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Өөрчлөх )

Twitter picture

You are commenting using your Twitter account. Log Out / Өөрчлөх )

Facebook photo

You are commenting using your Facebook account. Log Out / Өөрчлөх )

Google+ photo

You are commenting using your Google+ account. Log Out / Өөрчлөх )

Connecting to %s