Evklid alqoritmi

TƏRİF. ${\displaystyle a_{1},a_{2},...,a_{n}}$ tam ədədlərinin hər birinin eyni zamanda bölündüyü ${\displaystyle 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 ${\displaystyle 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 (${\displaystyle a_{1},a_{2},...,a_{n}}$) kimi işarə edirlər.

ƏBOB-u ${\displaystyle D}$ ilə ${\displaystyle (a_{1},a_{2},...,a_{n})=D}$ işarə edək. Xüsusi halda iki ${\displaystyle a}$ və ${\displaystyle b}$ ədədləri üçün: ƏBOB ${\displaystyle (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 ${\displaystyle a}$ və ${\displaystyle b}$ ədədlərindən ${\displaystyle a:b}$ isə, onda bunların bütün ortaq bölənləri ${\displaystyle b}$ ədədinin bölənlərindən ibarət olur və xüsusi halda ${\displaystyle (a,b)=b}$ olur.

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

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

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

Teorem isbat olunur.

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.${\displaystyle (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ə, ${\displaystyle D}$ ədədinin verilən ədədlərin ƏBOB-u olması üçün iki şərt ödənməlidir:

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

Məsələn ${\displaystyle a=30}$ və ${\displaystyle c=105}$ ədədlərinin ortaq bölənləri ${\displaystyle 1}$, ${\displaystyle 3}$, ${\displaystyle 5}$, ${\displaystyle 15}$ ədədləridir. Burada ƏBOB ${\displaystyle D=15}$; göründüyü kimi, ${\displaystyle 15:1}$, ${\displaystyle 15:3}$, ${\displaystyle 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, ${\displaystyle a}$ və ${\displaystyle b}$ ədədlərinin bütün ortaq bölənlər çoxluğu, bunların ƏBOB-nun (yəni ${\displaystyle (a,b)=D}$ ədədinin) bölənlər çoxlugu ilə üst-üstə düşür. İki ${\displaystyle a}$ və ${\displaystyle 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 ${\displaystyle a}$ və ${\displaystyle 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 ${\displaystyle a}$ və ${\displaystyle b}$ ədədləri üçün ${\displaystyle a>b}$ şərtilə ${\displaystyle a=bq_{1}+r_{1}}$, ${\displaystyle 0\leq r_{1}<b_{1}}$; sonra ${\displaystyle b>r_{1}}$ üçün ${\displaystyle b=r_{1}q_{2}+r_{2}}$, ${\displaystyle 0\leq r_{2}<r_{1}}$, ${\displaystyle 0\leq r_{1}<b_{1}}$; sonra ${\displaystyle r_{1}>r<_{2}}$ üçün ${\displaystyle r_{1}=r_{2}q_{3}+r_{3}}$, ${\displaystyle 0\leq r_{3}<r_{2}}$; sonra ${\displaystyle 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:

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

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

${\displaystyle (E)_{3}}$: ${\displaystyle r<_{1}=r_{2}q_{3}+r_{3}}$, ${\displaystyle 0\leq r_{3}<r_{2}}$,

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

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

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

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

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

${\displaystyle (E)_{k+1}}$: ${\displaystyle r_{k-1}=r_{k}<q_{k+1}+0}$.

${\displaystyle (E)}$ bərabərliklərini Evklid bərabərliklər sistemi adlandırırlar.

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

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

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

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

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

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

${\displaystyle (E)}$ bərabərliklərini

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

${\displaystyle (E)_{2}^{\prime }}$: ${\displaystyle b-r_{1}q_{2}=r_{2}}$,

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

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

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

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

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

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

Teorem isbat olundu.

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

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

• 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 Arxivləşdirilib 2016-10-12 at the Wayback Machine