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}<b_{1}$; sonra $b>r_{1}$ üçün $b=r_{1}q_{2}+r_{2}$, $0\leq r_{2}<r_{1}$, $0\leq r_{1}<b_{1}$; sonra $r_{1}>r<_{2}$ üçün $r_{1}=r_{2}q_{3}+r_{3}$, $0\leq r_{3}<r_{2}$; 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}<b$,

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

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

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

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

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

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

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

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

$(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)_{1}^{\prime }$: $a-bq_{1}=r_{1}$,

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

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

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

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

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

$(E)_{k+1}^{\prime }$: $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)_{1}^{\prime }$-dən aydın olur ki: $r_{1}:d$. $(E)_{2}^{\prime }$-dən: $r_{2}:d$, $(E)_{3}^{\prime }$-dən: $r_{3}:d$ və s.; nəhayət, $(E)_{k}^{\prime }$-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\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.

Ədəbiyyat

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.

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