ƏBOB, ƏKOB və Evklid Alqoritmi

İsbat. Əgər $d$ ədədi $a$ və $b$-nin ortaq bölənidirsə, Dərs 3-dəki bölənlərin quruluşu xassəsinə əsasən, $d$-nin ayrılışında $p_i$-nin qüvvəti nə $\alpha_i$-ni, nə də $\beta_i$-ni aşa bilməz; yəni maksimum $\min(\alpha_i,\beta_i)$ ola bilər. Bütün qüvvətləri mümkün olan ən böyük qiymətə bərabər götürsək, ən böyük ortaq böləni alarıq — bu isə məhz $\prod p_i^{\min(\alpha_i,\beta_i)}$ ədədidir. ƏKOB üçün mühakimə analojidir (simmetrikdir): ortaq bölünəndə hər bir $p_i$-nin qüvvəti ən azı $\max(\alpha_i,\beta_i)$ olmalıdır və bütün qüvvətləri mümkün minimum qiymətə bərabər götürdükdə ən kiçik ortaq bölünən alınır. ■

İsbat. Əgər $d$ ortaq böləndirsə, hər bir $p_i$ üçün $d$-nin ayrılışındakı qüvvət $\alpha_i$ və $\beta_i$-dən böyük deyil. Deməli, o, $\min(\alpha_i,\beta_i)$-dən də böyük deyildir, yəni $d\mid(a,b)$. Əksinə, $d\mid(a,b)$ olarsa, bölünmənin tranzitivlik (keçiricilik) xassəsinə görə (Dərs 2) $d$ həm $a$-nı, həm də $b$-ni bölür. Bölünənlər üçün mühakimə eynidir: əgər $m$ ortaq bölünəndirsə, $m$-in ayrılışındakı hər bir qüvvət $\alpha_i$ və $\beta_i$-dən kiçik ola bilməz. Deməli, o, $\max(\alpha_i,\beta_i)$-dən də kiçik deyildir, yəni $[a,b]\mid m$; əksi yenə də tranzitivlik xassəsindən alınır. ■

İsbat. İxtiyari $x,y$ ədədləri üçün $\min(x,y)+\max(x,y)=x+y$ bərabərliyi həmişə doğrudur, çünki $\min$ və $\max$ funksiyalarının nəticələri elə $x$ və $y$-in özləridir, sadəcə yerləri dəyişik düşə bilər. Onda hər bir $p_i$ sadə vuruğu üçün $(a,b)\cdot[a,b]$ hasilində $p_i$-nin qüvvəti

$$\min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i) = \alpha_i+\beta_i$$

olacaqdır — bu isə $a\cdot b$ hasilindəki uyğun qüvvətlə eynidir. Bütün sadə vuruqlarda qüvvətlər üst-üstə düşdüyü üçün bu ədədlər bir-birinə bərabərdir. ■

İsbat. Göstərək ki, $\{a,b\}$ cütünün ortaq bölənləri çoxluğu ilə $\{b,r\}$ cütünün ortaq bölənləri çoxluğu tamamilə üst-üstə düşür — bu halda, həmin çoxluqların ən böyük elementləri də eyni olacaqdır. Tutaq ki, $d\mid a$ və $d\mid b$. $r = a - bq$ ədədi $a$ və $b$-nin xətti kombinasiyasıdır, deməli, Dərs 2-dəki xətti kombinasiya xassəsinə əsasən $d\mid r$ alınır. Beləliklə, $d$ həm $b$-ni, həm də $r$-i bölür. Əksinə, tutaq ki, $d\mid b$ və $d\mid r$. $a = bq + r$ ifadəsi yenə $b$ və $r$-in xətti kombinasiyası olduğundan, $d\mid a$ alarıq. Beləliklə, $d$ həm $a$-nı, həm də $b$-ni bölür. Hər iki istiqamət tam isbat olundu. ■

İsbat. $a$ və $b$-nin tam əmsallı və müsbət qiymətli bütün xətti kombinasiyalarının çoxluğuna baxaq:

$$S = \{\, ax + by \;:\; x, y \in \mathbb{Z},\; ax+by > 0 \,\}.$$

$a = a\cdot 1 + b\cdot 0 \in S$ olduğundan $S$ çoxluğu boş deyil. Natural ədədlərin hər bir boş olmayan altçoxluğunun ən kiçik elementi var; gəlin $S$-in ən kiçik elementini $d_0$ ilə işarə edək: $d_0 = ax_0 + by_0$. Addım 1: $d_0 \mid a$. $a$-nı $d_0$-a qalıqlı bölək: $a = qd_0 + r$, burada $0 \le r < d_0$. Onda,

$$r = a - qd_0 = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0),$$

yəni $r$ özü də $a$ və $b$-nin tam əmsallı xətti kombinasiyasıdır. Əgər $r > 0$ olsaydı, $r \in S$ olardı; lakin $r < d_0$ alırıq ki, bu da $d_0$-ın $S$-də ən kiçik element olması faktı ilə ziddiyyət təşkil edir. Deməli, $r = 0$, yəni $d_0 \mid a$. Analoji mühakimə ilə $d_0 \mid b$ olduğunu da göstərmək olar. Addım 2: $d_0 = (a,b)$. Addım 1-ə görə $d_0$ ortaq böləndir, ona görə də $d_0 \le (a,b)$. Digər tərəfdən, $(a,b)$ həm $a$-nı, həm də $b$-ni böldüyündən xətti kombinasiya xassəsinə görə $(a,b) \mid ax_0 + by_0 = d_0$, buradan da $(a,b) \le d_0$ alınır. Deməli, $d_0 = (a,b)$ və uyğun olaraq $ax_0 + by_0 = (a,b)$ bərabərliyi ödənilir. ■

İsbat. Əgər $(a,b)=1$ olarsa, Bezu teoreminə görə $ax+by=1$ həlli mütləq var. Tərsinə, əgər $ax+by=1$ ödənilirsə, $(a,b)$ həm $a$-nı, həm də $b$-ni böldüyü üçün $ax+by=1$ cəmini də bölməlidir; $1$-i bölən yeganə natural ədəd isə elə $1$-dir, deməli $(a,b)=1$. ■

İsbat. Əgər həll mövcuddursa, $(a,b)$ bərabərliyin sol tərəfini (xətti kombinasiya kimi) böldüyündən $n$-i də bölür. Əksinə, əgər $n = (a,b)\cdot m$ olarsa, Bezu bərabərliyinin hər iki tərəfini $m$-ə vuraq: $a(x_0 m) + b(y_0 m) = (a,b)\cdot m = n$ — beləliklə, axtarılan həll tapılmış olur. ■

İsbat. Tutaq ki, $p \nmid a$; göstərək ki, bu halda $p \mid b$ olmalıdır. $p$-nin bölənləri yalnız $1$ və $p$-dir; $p \nmid a$ olduğundan $p$ ilə $a$-nın ortaq böləni yalnız $1$ ola bilər, yəni $(p,a) = 1$. Bezu eyniliyinə əsasən, elə $x, y$ tam ədədləri var ki, $px + ay = 1$. Hər iki tərəfi $b$-yə vuraq:

$$b = pbx + aby.$$

Bərabərliyin sağ tərəfindəki birinci toplanan aşkar şəkildə $p$-yə bölünür; ikinci toplanan da $p$-yə bölünür, çünki $p \mid ab$. Deməli, cəm də $p$-yə bölünür və buradan $p \mid b$ alınır. ■

İsbat. Analoji üsulla: $(d,a)=1$ olduğundan elə $x,y$ var ki, $dx + ay = 1$ ödənilir. Hər iki tərəfi $b$-yə vurduqda, $b = dbx + aby$ alınır; sağdakı toplananların hər ikisi $d$-yə bölünür (şərtə görə $d\mid ab$), deməli nəticədə $d \mid b$ alarıq. ■

İsbat. Əksini fərz edək: tutaq ki, iki fərqli ayrılışı olan natural ədədlər mövcuddur. Onların ən kiçiyini $n$ ilə işarə edək və fərz edək ki,

$$n = p_1 p_2 \cdots p_s = q_1 q_2 \cdots q_t$$

bərabərliyi ödənilir (sadə vuruqlar təkrarlana bilər). $p_1$ sadə ədədi $q_1 q_2 \cdots q_t$ hasilini qalıqsız bölür. Evklid lemmasını ardıcıl tətbiq etdikdə ($p_1$ ya birinci vuruğu bölür, ya da qalan hasili; qalan hasilə də yenidən lemmanı tətbiq edirik və s.), tapırıq ki, $p_1$ mütləq vuruqlardan hansınısa, deyək ki, $q_j$-ni bölür. Lakin $q_j$ özü də sadədir, onun $1$-dən başqa yeganə böləni özüdür; deməli, $p_1 = q_j$. İndi bərabərliyin hər iki tərəfini $p_1$-ə ixtisar edək:

$$\frac{n}{p_1} = p_2 \cdots p_s = q_1 \cdots q_{j-1}\, q_{j+1} \cdots q_t.$$

$n/p_1 < n$ olduğundan və $n$ ədədi iki fərqli ayrılışı olan ən kiçik ədəd kimi seçildiyindən, $n/p_1$-in ayrılışı yeganə olmalıdır; deməli yuxarıdakı iki ayrılış vuruqların sırasına qədər eynidir. Bu halda hər iki tərəfə $p_1 = q_j$ vuruğunu geri qaytarsaq, $n$-in özünün də hər iki ayrılışının eyni olduğu aşkar olar — fərziyyəmizlə ziddiyyət alındı. Deməli, iki fərqli ayrılışı olan ədəd yoxdur. ■

İsbat. (1) Bezu teoreminə görə elə tam ədədlər mövcuddur ki, $ax_1+by_1=1$ və $ax_2+cy_2=1$. Bu iki bərabərliyi tərəf-tərəfə vuraq:

$$1 = (ax_1+by_1)(ax_2+cy_2) = a\underbrace{(ax_1x_2+cx_1y_2+bx_2y_1)}_{X} + bc\,\underbrace{(y_1y_2)}_{Y},$$

yəni $aX + bcY = 1$ alınır. Qarşılıqlı sadəlik meyarına əsasən $(a,bc)=1$. (2) Bu faktı Dərs 2-də isbatsız istifadə etmişdik — indi isə isbatını təqdim edirik. $(a,b)=1$ olduğundan elə $x,y$ var ki, $ax+by=1$. Hər iki tərəfi $n$-ə vuraq:

$$n = n(ax+by) = nax + nby.$$

Birinci toplananda $b\mid n$ olduğundan $na = a\cdot n$ hasili $ab$-yə qalıqsız bölünür; ikinci toplananda isə $a\mid n$ olduğundan $nb$ hasili $ab$-yə bölünür. Deməli, bu toplananların cəmi də bölünür, yəni $ab \mid n$. (3) Əgər $d\mid n$ və $d\mid n+1$ olarsa, xətti kombinasiya xassəsinə görə $d \mid (n+1)-n = 1$, yəni $d=1$. ■

İsbat. Əsas riyazi müşahidə: $n > m$ olduqda

$$(2^n - 1) - 2^{\,n-m}(2^m - 1) = 2^n - 1 - 2^n + 2^{\,n-m} = 2^{\,n-m} - 1.$$

$2^{\,n-m}-1$ ədədi $2^n-1$ və $2^m-1$-in xətti kombinasiyasıdır. Bu səbəbdən cütlərin ortaq bölənləri çoxluqları haqqında Evklid addımında apardığımız mühakimənin tamamilə eynisi burada da keçərlidir:

$$\left(2^n-1,\; 2^m-1\right) = \left(2^m-1,\; 2^{\,n-m}-1\right).$$

Yəni üstlər cütü $(n,m)$-dən $(m,\,n-m)$-ə keçdi — bu isə Evklid alqoritminin çıxma əməli vasitəsilə tətbiqinin məhz bir addımıdır! Alqoritmi üstlər üzərində sonadək aparsaq, üstlər cütü nəhayət $((m,n),\,0)$-a gəlib çatır və

$$\left(2^m-1,\; 2^n-1\right) = \left(2^{(m,n)}-1,\; 2^0-1\right) = \left(2^{(m,n)}-1,\; 0\right) = 2^{(m,n)}-1.$$

Nümunə vasitəsilə yoxlayaq: $\left(2^{12}-1,\,2^{18}-1\right) = (4095,\,262143) = 63 = 2^6-1$ və doğrudan da $(12,18)=6$. ■

Həll. Kanonik ayrılışlar: $48 = 2^4\cdot 3$, $180 = 2^2\cdot 3^2\cdot 5$. ƏBOB-da ortaq sadə vuruqların kiçik, ƏKOB-da isə böyük qüvvətini götürürük:

$$(48,180) = 2^2\cdot 3 = 12, \qquad [48,180] = 2^4\cdot 3^2\cdot 5 = 720 .$$

Yoxlama: $12\cdot 720 = 8640 = 48\cdot 180$. Cavab: $12$ və $720$.□

Həll.

$$252 = 105\cdot 2 + 42, \qquad 105 = 42\cdot 2 + 21, \qquad 42 = 21\cdot 2 + 0 .$$

Sonuncu sıfırdan fərqli qalıq $21$-dir. Cavab: $21$.□

Həll. $(a,b)\cdot[a,b] = ab$ düsturuna əsasən: $[a,b] = \dfrac{720}{6} = 120$. Cavab: $120$.□

Həll. $ab = (a,b)\cdot[a,b] = 8\cdot 96 = 768$, deməli $b = 768/24 = 32$. Yoxlama: $(24,32) = 8$, $[24,32] = 96$. Cavab: $b = 32$.□

Həll. $d = (n, n+1)$ olsun. $d$ hər iki ədədi böldüyündən onların fərqini də bölməlidir: $d \mid (n+1) - n = 1$, yəni $d = 1$. Cavab: $(n, n+1) = 1$.□

Həll. Ortaq sadə vuruqlar $2$ və $3$-dür:

$$(a,b) = 2^3\cdot 3^2 = 72, \qquad [a,b] = 2^5\cdot 3^4\cdot 5\cdot 7 = 90720 .$$

Cavab: $72$ və $90720$.□

Həll. $a \mid b$ olduqda $a$ özü ən böyük ortaq bölən, $b$ isə ən kiçik ortaq bölünəndir: $(17,51) = 17$, $[17,51] = 51$. Cavab: $(a,b) = a$ və $[a,b] = b$.□

Həll. Bu, tərifə görə $[6,8]$-dir: $6 = 2\cdot 3$, $8 = 2^3$, deməli $[6,8] = 2^3\cdot 3 = 24$. Cavab: $24$.□

Həll. Axtarılan vaxt hər iki intervalın ortaq bölünəni, daha dəqiqi isə ən kiçik ortaq bölünənidir: $[12,18] = 2^2\cdot 3^2 = 36$. Cavab: $36$ dəqiqədən sonra.□

Həll. Parçanın uzunluğu hər iki ədədin ortaq böləni olmalıdır, ən böyük mümkün uzunluq isə $(60,84)$-dür: $60 = 2^2\cdot 3\cdot 5$, $84 = 2^2\cdot 3\cdot 7$ $\Rightarrow$ $(60,84) = 12$. Cavab: $12$ sm.□

Həll. $(8,15) = 1$ və $(10,21) = 1$ — ortaq sadə vuruqları yoxdur. $(9,12) = 3$, $(7,21) = 7$. Cavab: $(8,15)$ və $(10,21)$.□

Həll. Ortaq bölənlər məhz ƏBOB-un bölənləridir: $(30,45) = 15$ və $15 = 3\cdot 5$ ədədinin $\tau(15) = 4$ böləni var: $1, 3, 5, 15$. Cavab: $4$ ortaq bölən.□

Həll. Bezu meyarına görə $ax+by = c$ tənliyinin tam həlli var $\iff$ $(a,b) \mid c$. Birinci tənlikdə $(4,6) = 2 \nmid 5$ — yəni həll yoxdur. İkincidə isə $(6,9) = 3 \mid 15$ — həll var (məsələn, $x = 1$, $y = 1$). Cavab: Birinci tənliyin həlli yoxdur, ikincinin isə var.□

Həll. $(5,7) = 1$ olduğundan həll mövcuddur. Seçmə (və ya sınaq) üsulu ilə yoxlayaq: $5\cdot 3 + 7\cdot(-2) = 15 - 14 = 1$. Cavab: $x = 3$, $y = -2$ (ümumi həll: $x = 3+7t$, $y = -2-5t$).□

Həll. $n^2 \mid n^3$ olduğundan ƏBOB kiçik ədədə, ƏKOB isə böyük ədədə bərabərdir. Cavab: $(n^2,n^3) = n^2$, $[n^2,n^3] = n^3$.□

Həll. Ortaq vuruğu xaricə çıxaraq: $(3n, 3n+3) = 3\,(n, n+1) = 3\cdot 1 = 3$. Cavab: Həmişə $3$-ə bərabərdir.□

Həll. Hər bir addımda böyük ədədi kiçiyə qalıqlı böləcəyik və Evklid addımına əsasən cütü $(b, r)$ ilə əvəz edəcəyik:

$$22121 = 2 \cdot 10055 + 2011 \implies (22121, 10055) = (10055, 2011),$$

$$10055 = 5 \cdot 2011 + 0 \implies (10055, 2011) = 2011.$$

Qalıq sıfır olduğu andakı bölən axtarılan cavabdır: $(10055, 22121) = 2011$. Qeyd edək ki, $2011$ sadə ədəddir (bunu $\sqrt{2011} < 45$-ə qədər olan sadə ədədlərə bölməklə təsdiq etmək olar), lakin alqoritmin tətbiqi üçün bu faktın əvvəlcədən bilinməsinə ehtiyac yox idi. Cavab: $2011$□

Həll. Bezu meyarına görə $ax + by = n$ tənliyinin tam həlli yalnız və yalnız $(a,b) \mid n$ olduqda mövcuddur. Burada $(12, 15) = 3$-dür. Lakin $10$ ədədi $3$-ə bölünmür: $10 = 3 \cdot 3 + 1$. Deməli, tənliyin tam ədədlərdə həlli yoxdur. Bunu bilavasitə də görmək olar: ixtiyari $x, y$ tam ədədləri üçün $12x + 15y = 3(4x + 5y)$ ifadəsi mütləq $3$-ə bölünür, halbuki sağ tərəfdəki $10$ ədədi $3$-ə bölünmür. Cavab: Xeyr, həlli yoxdur.□

Həll. Bu dərsin əsas xassəsinə görə iki ədədin ortaq bölənləri məhz onların ƏBOB-unun bölənləridir. Əvvəlcə kanonik ayrılışları yazaq:

$$2520 = 2^3 \cdot 3^2 \cdot 5 \cdot 7, \qquad 3960 = 2^3 \cdot 3^2 \cdot 5 \cdot 11.$$

Hər sadə vuruqda qüvvətlərin minimumunu götürsək,

$$(2520, 3960) = 2^3 \cdot 3^2 \cdot 5 = 360.$$

Deməli, axtarılan ədədlər $360$-ın bölənləridir. Dərs 3-də öyrəndiyimiz $\tau$ düsturu ilə onların sayı belə tapılır:

$$\tau(360) = (3+1)(2+1)(1+1) = 24.$$

Cavab: $24$□

Həll. Axtarılan say

$$n = \tau\!\left(60^{50}\right) - \#\{d : d \mid 60^{50} \ \text{və} \ d \mid 50^{60}\}$$

şəklindədir. Hər iki ədədi bölən $d$ ədədləri isə məhz $\left(60^{50}, 50^{60}\right)$-ın bölənləridir. Kanonik ayrılışlar:

$$60^{50} = 2^{100} \cdot 3^{50} \cdot 5^{50}, \qquad 50^{60} = 2^{60} \cdot 5^{120}.$$

Minimum qüvvətləri götürsək, $\left(60^{50}, 50^{60}\right) = 2^{60} \cdot 5^{50}$ alarıq. Dərs 3-dəki $\tau$ düsturunu tətbiq edək:

$$\tau\!\left(60^{50}\right) = 101 \cdot 51 \cdot 51 = 262701, \qquad \tau\!\left(2^{60} \cdot 5^{50}\right) = 61 \cdot 51 = 3111.$$

Deməli, $n = 262701 - 3111 = 259590$. İndi qalıqlı bölməni aparaq: $259590 = 50 \cdot 5191 + 40$, yəni alınan qalıq $40$-dır. Cavab: $40$□

Həll. $(a,b) = 48$ olduğundan, bu dərsdə öyrəndiyimiz parametrləşdirmə vasitəsilə $a = 48x$, $b = 48y$ yaza bilərik, burada $(x,y) = 1$. Onda

$$48x + 48y = 576 \implies x + y = 12.$$

Cüt fərqli ədədlərdən ibarət olduğundan $x < y$ qəbul edək və $(x,y)=1$ şərtini yoxlayaq: $(1,11)$, $(2,10)$, $(3,9)$, $(4,8)$, $(5,7)$ variantlarından yalnız $(1,11)$ və $(5,7)$ qarşılıqlı sadədir. (Diqqət edin: $(6,6)$ həm fərqli deyil, həm də qarşılıqlı sadə şərtini ödəmir). Beləliklə, cütlər $(48, 528)$ və $(240, 336)$ olmaqla cəmi $2$ dənədir. Cavab: $2$□