Қазақстан республикасы білім және ғылым министрлігі алматы облыстық білім департаменті қапшағай қалалық білім, дене тәрбиесі және спорт бөлімі қапшағай қаласы «№12 орта мектеп мектепке дейінгі шағын орталығымен»

Евклид алгоритмі қолданылатын мәселелердің бірі – жай бөлшекті тізбекті бөлшек түрінде жазу.

а_{1 =} q₁ + 1

а₂ q₂ + 1

q₃ + .

.

.

q_n

Осындай өрнек тізбекті (шекті үздіксіз) бөлшек деп аталады. Мұндағы q₁, q₂, ..., q_n сандары а₁ және а₂ сандарының ең үлкен ортақ бөлгішін табу кезіндегі бөлінділері.

Мысалы:

1577 1577 1577 2 + 437 2 + 1 .

570 570 1 + 133

437

2 + 1 . 2 + 1 . 2 + 1 .

1 + 1 . 1 + 1 . 1 + 1 .

3 + 38 3 + 1 . 3 + 1 .

133 3 + 19 3 + 1

38 2

Мысалы:

93 93 93 1 ₊ 31 1 ₊ 1 3 3 3

62 62 2 2

Сондықтан, қысқаратын бөлшекті (әсіресе 47, 59, 83 сияқты тек жай сандарға ғана қысқаратын бөлшектерді) қандай санға қысқартуға болатынын көрмей тұрған жағдайда бұл әдіс өте тиімді болып табылады.

Практикалық мағынасы бар алуан түрлі есептерді шешу кезінде түбірлері бүтін сандар болатын теңдеулерді шешуге келіп тіреледі. Бүтін сандардағы теңдеулер ежелгі замандарда қарастырылған. Әсіресе онымен александриялық математик Диофант көп айналысқан. Сондықтан оларды Диофант теңдеулері деп атайды.

Диофант теңдеулерінің ең қарапайым түрі ах + ву= с. Мұндағы а, в, с коэффициенттері де бүтін сандар, ал а және в сандары өзара жай сандар. Бұл теңдеу әртүрлі тәсілдермен шығарыла береді. Бірақ олардың ішінде Евклид алгоритмі көмегімен шығару тиімдірек. Себебі тек берілген дайын алгоритм бойынша белгілі амалдар орындалып отырады.

Егер х пен у және х₀ мен у₀ ах + ву= с теңдеуінің шешімдері болсын. Сонда ах + ву= с= ах₀ + ву₀ теңдігін жазуға болады. Бұдан

Сонда х – х₀ = в(у – у₀)/а, у₀ – у = а(х – х₀)/в теңдіктерінің екі жағы да бүтін сандар. Олай болса к= (у – у₀)/а деп белгілеу енгізейік. Сонда

Мысалы:

53x + 74 y = 1 теңдеуінің жалпы шешімін табу керек.

_- 74 53

53

_- 53 21 1

42

_- 21 11 2

11

_- 11 10 1

10

_- 10 1 1

10

0 10

74 = 53 * 1 + 21 21 = 74 – 53 * 1

53 = 21 * 2 + 11 11 = 53 – 21 * 2

21 = 11 * 1 + 10 10 = 21 – 11 * 1

11 = 10 * 1 + 1 1 = 11 – 10 * 1

10 = 1 * 10

Сонда 1=11-10·1=11-(21-11·1)·1=11·2-21·1=(53-21·2)·2-21·1=53·2-21·2=53·2-(74-53·1) ·5=53·7-74·5= 53·7+74· (-5).

Ал Диофант теңдеуіміз 53x + 74 y = 1

Бұдан х₀ =7, у₀ =-5.

Жалпы шешімі: х=7-74к, у=-5+53к.

Тексеру: к=1, х=7-74=-67, у=-5+53=48.

53*(-67)+74*58= -3551+3552 =1.

Практикалық мағынасы бар есептерде осы жалпы шешімнің ішінен х және у есептің шартын қанағаттандыратындай к-ның мәнін таңдап, х пен у-тің нақты шешімін табуға болады.