Evklid alqoritmi

Ortaq bölən və ən böyük ortaq bölən 
TƏRİF.  tam ədədlərinin hər birinin eyni zamanda bölündüyü  ə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  ə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 () kimi işarə edirlər.

ƏBOB-u  ilə  işarə edək. Xüsusi halda iki  və  ədədləri üçün: ƏBOB 

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

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

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

TEOREM 2.  münasibətində olan  və  ədədlərinin ortaq böləni  və -nin ortaq bölənləri ilə eynidir və xüsusi halda .

İSBATI. və yaxud buradan alınan ,  bərabərlikləri göstərir ki,  və -nin hər bir ortaq böləni eyni zamanda -nin ortaq bölənləri olur; tərsinə,  ilə -nin istənilən ortaq bölənləri  — nın da bölənləridir və deməli,  və -nin ortaq bölənləri olurlar.Beləliklə alırıq ki,  və -nin ortaq bölənləri eyni zamanda  ilə -nin ortaq bölənləridir.ƏBOB da bu ortaq bölənlər içərisində olduğu üçün  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. ə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ədinin verilən ədədlərin ƏBOB-u olması üçün iki şərt ödənməlidir:

 ədədi  ədədlərinin ortaq bölənidir;
 ədədi  ədədlərinin ixtiyari bir  ortaq böləninə bölünür: 

Məsələn  və  ədədlərinin ortaq bölənləri , , ,  ədədləridir. Burada ƏBOB ; göründüyü kimi, , , .
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,  və  ədədlərinin bütün ortaq bölənlər çoxluğu, bunların ƏBOB-nun (yəni  ədədinin) bölənlər çoxlugu ilə üst-üstə düşür.
İki  və  ə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  və  ə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  və  ədədləri üçün  şərtilə , ; sonra  üçün , , ; sonra  üçün , ; sonra  üçü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:

: , ,

: , ,

: , ,

: , ,

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

: , ,

: , ,

: , ,

: .

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

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

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

TEOREM.  və  ədələrinin ƏBOB-u  bərabərliklər sistemindəki sonuncu -dan fərqli qalıqdır, yəni .

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

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

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

 bərabərliklərini

: ,

: ,

: ,

…………………………………….

: ,

: 

: 

şəklində yazaq.  ixtiyari ortaq bölən olduğundan  və , onda -dən aydın olur ki: . -dən: , -dən:  və s.; nəhayət, -dən:  olduğunu tapırıq.Ona görə də .

Teorem isbat olundu.

QEYD.İki  və  ədədləri  üçü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 

Kateqoriya:Ən böyük ortaq bölən
Kateqoriya:Ədədlər nəzəriyyəsi
Kateqoriya:Evklid alqorifmi