Evklid alqoritmi

## Ortaq bölən və ən böyük ortaq bölən
**TƏRİF.** a_{1}, a_{2},...,a_{n} tam ədədlərinin hər birinin eyni zamanda bölündüyü d ədədinə bu ədədlərin ortaq böləni deyilir.

Məsələn, 60, 25, 45 ədədləri üçün 5 ədədi ortaq böləndir.

**TƏRİF.**Verilən a_{1}, a_{2},...,a_{n} ədədlərinin ortaq bölənləri içərisindən ən böyüyünə bu ədədlərin ən böyük ortaq böləni (ƏBOB) deyib, onu (a_{1}, a_{2},...,a_{n}) kimi işarə edirlər.

ƏBOB-u D ilə (a_{1}, a_{2},...,a_{n})=D işarə edək. Xüsusi halda iki a və b ədədləri üçün: ƏBOB (a,b)=D.

Bu təriflərdən nəticə kimi alına bilən aşağıdakı iki teoremi isbat edək.

**TEOREM 1.**Verilən a və b ədədlərindən a:b isə, onda bunların bütün ortaq bölənləri b ədədinin bölənlərindən ibarət olur və xüsusi halda (a,b) = b olur.

**İSBATI.**Aşkardır ki, a və b-nin ortaq bölənləri eyni zamanda hər ikisinin, o cümlədən, b-nin ortaq bölənləridir.Digər tərəfdən a:b olduğundan b-nin hər bir böləni eyni zamanda a-nın da böləni olmalıdır. Bu isə o deməkdir ki, a və b-nin ortaq bölənlər çoxluğu b ədədinin bölənləri çoxluğu ilə üst-üstə düşür. b ədədinin ən böyük böləni özü olduğundan (a,b) = b olur.
Teorem isbat olundu.

**TEOREM 2.** a = bq + c münasibətində olan a və b ədədlərinin ortaq böləni b və c-nin ortaq bölənləri ilə eynidir və xüsusi halda (a,b) = (b,c).

**İSBATI.**a = bq + c və yaxud buradan alınan a - bq = c, a - c = bq bərabərlikləri göstərir ki, a və b-nin hər bir ortaq böləni eyni zamanda c-nin ortaq bölənləri olur; tərsinə, b ilə c-nin istənilən ortaq bölənləri a — nın da bölənləridir və deməli, a və b-nin ortaq bölənləri olurlar.Beləliklə alırıq ki, a və b-nin ortaq bölənləri eyni zamanda b ilə c-nin ortaq bölənləridir.ƏBOB da bu ortaq bölənlər içərisində olduğu üçün (a,b) = (b,c) olur.

Teorem isbat olunur.

## Evklid alqoritmi
Müasir riyaziyyatda ən böyük ortaq bölənin bir çox cəhətdən daha əhəmiyyətli olan aşağıdakı tərifi də var.

**TƏRİF 2.**(a_{1}, a_{2},...,a_{n}) ədədlərinin ortaq bölənləri içərisində eləsinə ƏBOB deyirlər ki, o, digər ortaq bölənlərin hamisina bölünsün.
Başqa sözlə, D ədədinin verilən ədədlərin ƏBOB-u olması üçün iki şərt ödənməlidir:

D ədədi a_{1}, a_{2},...,a_{n} ədədlərinin ortaq bölənidir;
D ədədi a_{1}, a_{2},...,a_{n} ədədlərinin ixtiyari bir d ortaq böləninə bölünür: D:\forall{d}

Məsələn a = 30 və c = 105 ədədlərinin ortaq bölənləri 1, 3, 5, 15 ədədləridir. Burada ƏBOB D = 15; göründüyü kimi, 15:1, 15:3, 15:5.
Sonuncu 2-ci tərifin üstünlüyü ondadır ki, ƏBOB anlayışını asanlıqla geniş riyazi obyektler çoxlugu üçün ümumiləşdirməyə imkan verir.
Tərif 2-dən belə bir aşkar nəticə çıxır ki, a və b ədədlərinin bütün ortaq bölənlər çoxluğu, bunların ƏBOB-nun (yəni (a,b) = D ədədinin) bölənlər çoxlugu ilə üst-üstə düşür.
İki a və b ədədlərinin ƏBOB-nu tapmaq üçün istifadə edilən səmərəli üsullardan biri antik dövrün böyük riyaziyyatçısı Evklidin adı ilə bağlı olan "Evklid" alqorifmidir. Evklid alqorifmi verilən a və b ədədlərinə qalıqlı bölmə alqorifmini və buradan qismət və qalıqlara ardıcıl tətbiq etməkdir. Belə ki, verilən a və b ədədləri üçün a>b şərtilə a = bq_{1} + r_{1}, 0\leq r_{1}; sonra b>r_{1} üçün b = r_{1}q_{2} + r_{2}, 0\leq r_{2}, 0\leq r_{1}; sonra r_{1}>r üçün r_{1} = r_{2}q_{3} + r_{3}, 0\leq r_{3}; sonra r_{2}>r_{3} üçün və s.
Bu proses qalıq sıfra bərabər olanda qurtarır və aşağıdakı bərabərliklər sistemi alınır:

(E)_{1}: a = bq_{1} + r_{1}, 0\leq r_{1},

(E)_{2}: b = r_{1}q_{2} + r_{2}, 0\leq r_{2},

(E)_{3}: r, 0\leq r_{3},

(E)_{4}: r_{2} = r_{3}q_{4} = r_{4}, 0\leq r_{4},

…………………………………………………

(E)_{k-2}: r_{k-4} = r_{k-2}q_{k-2} + r_{k-2}, 0\leq r_{k-2},

(E)_{k-1}: r_{k-3} = r_{k-2}q_{k-1} + r_{k-1}, 0\leq r_{k-1},

(E)_{k}: r_{k-2} = r_{k-1}q_{k} + r_{k}, 0\leq r_{k},

(E)_{k+1}: r_{k-1} = r_{k}.

(E) bərabərliklərini Evklid bərabərliklər sistemi adlandırırlar.

Əgər b>a olardısa onda b-ni a-ya bölməklə başlayıb (E) bərabərliklərində b ilə a-nın yerini dəyişərdik.

İndi aşağıdakı teoremi isbat edək.

**TEOREM.** a və b ədələrinin ƏBOB-u (E) bərabərliklər sistemindəki sonuncu 0-dan fərqli qalıqdır, yəni D = r_{k}.

**İSBATI.**Əvvəlcə göstərək ki, r_{k} ədədi a və b-nin ortaq bölənidir.

Sonuncu (E)_{k+1} bərabərliyindən görünür ki: r_{k-1}:r_{k}.Bunu nəzərə alıb (E)_{k} bərabərliyinə diqqət yetirsək, aydın olur ki, r_{k-2}:r_{k} (çünki r_{k}:r_{k} və r_{k-1}:r_{k}).Bunu nəzərə alıb (E)_{k-1} — tapırıq ki, r_{k-3}:r_{k} və s. Bu mühakiməni yuxarıya doğru davam etdirməklə (E)_{2}-dən b:r_{k}, (E)_{1}-dən isə a:r_{k} tapırıq. Deməli r_{k} ədədi a və b-nin ortaq bölənidir.

İndi r_{k}-nın ƏBOB olması üçün 2-ci tərifə görə göstərməliyik ki, r_{k} ədədi a və b-nin ixtiyari bir d ortaq böləninə bölünür.

(E) bərabərliklərini

(E)^{\prime}_{1}: a - bq_{1} = r_{1},

(E)^{\prime}_{2}: b - r_{1}q_{2} = r_{2},
  
(E)^{\prime}_{3}: r_{1} - r_{2}q_{3} = r_{3},
 
…………………………………….

(E)^{\prime}_{k-1}: r_{k-3} - r_{k-2}q_{k-1} = r_{k-1},

(E)^{\prime}_{k}: r_{k-2} - r_{k-1}q

(E)^{\prime}_{k+1}: r_{k-1} - r_{k}q_{k+1} = 0.

şəklində yazaq. d ixtiyari ortaq bölən olduğundan a:d və b:d, onda (E)^{\prime}_{1}-dən aydın olur ki: r_{1}:d. (E)^{\prime}_{2}-dən: r_{2}:d, (E)^{\prime}_{3}-dən: r_{3}:d və s.; nəhayət, (E)^{\prime}_{k}-dən: r_{k}:d olduğunu tapırıq.Ona görə də (a,b) = r_{k} = D.

Teorem isbat olundu.

**QEYD.**İki a və b ədədləri (b\ne0) üçün həmişə qalıqlı bölmə alqorifmi olduğundan ən böyük ortaq bölənin varlığı da aşkar olur.

## Ədəbiyyat
# Вандер Варден Б.Л. Алгебра "Наука" 1976.
# Куликов Л.Я. Алгебра и теория чисел. М.. Высшая школа, 1979.
# Курош А.Г. Курс высшей алгебры. М., Наука. 1977
# Бухштаб А.А. Теория чисел. М., Просвещение, 1966.
# Столл Р.С. Множества.Логинка.Аксиоматические теории. Просвещение. 1968.
# Qasımov V.Ə. Cəbr və ədədlər nəzəriyyəsi. I və II his. 1998, 1999. BDU nəşriyyatı.
# M.H.Cavadov, R.Ə.Eyyubov, F.H.Əfəndiyev: Cəbr və ədədlər nəzəriyyəsi I hissə, 1988.
# M.H.Cavadov, R.Ə.Eyyubov, F.H.Əfəndiyev: Cəbr və ədədlər nəzəriyyəsi II hissə, 1989.
# M.H.Cavadov, R.Ə.Eyyubov, F.H.Əfəndiyev: Cəbr və ədədlər nəzəriyyəsi III hissə, 1992.
# Abdulkərimov L.Ş., Baxşəliyev Y.R. və b. Cəbr və ədədlər nəzəriyyəsi IV hissə, 1995.

## Xarici keçidlər
* http://eqworld.ipmnet.ru/ru/library/mathematics/numtheory.htm
* http://adpu.edu.az/gen/html/azl/fakulte/Riyaziyyat_fakultesi/kafedra/Cebr_ve_hendese/ftp-7.htm