Xətti Diofant tənlikləri və Çin qalıq teoremi

İsbat. ($\Rightarrow$) Zərurilik. Tutaq ki, $x_0,y_0$ tənliyin həllidir. $d\mid a$ və $d\mid b$ olduğuna görə Dərs 2-nin xətti kombinasiya xassəsinə əsasən $d\mid (ax_0+by_0)=c$ alınır. ($\Leftarrow$) Kifayətlik. Tutaq ki, $d\mid c$, yəni $c=dk$. Dərs 4-dəki Bezu bərabərliyinə əsasən, elə $u,v$ tam ədədləri mövcuddur ki,

$$au+bv=d.$$

Bu bərabərliyin hər iki tərəfini $k$-ya vuraq:

$$a(uk)+b(vk)=dk=c.$$

Deməli, $x_0=uk$, $y_0=vk$ cütü tənliyin həllidir. ■

İsbat. Addım 1 (Düsturun həll olduğunu yoxlayaq). İfadələri tənlikdə yerinə yazaq:

$$a\Big(x_0+\frac{b}{d}t\Big)+b\Big(y_0-\frac{a}{d}t\Big)=ax_0+by_0+\frac{ab}{d}t-\frac{ab}{d}t=c.$$

$t$-dən asılı toplananlar bir-birini yox etdi, deməli, ixtiyari $t$ üçün həqiqətən həll alınır. Diqqət edin: $d$ hər iki ədədin böləni olduğu üçün $\frac{b}{d}$ və $\frac{a}{d}$ tam ədədlərdir. Addım 2 (Başqa həllərin olmaması). Tutaq ki, $(x,y)$ ixtiyari həlldir. Verilmiş tənliklə xüsusi həllin tənliyini tərəf-tərəfə çıxaq:

$$ax+by=c,\qquad ax_0+by_0=c\ \ \Longrightarrow\ \ a(x-x_0)=-b(y-y_0).$$

Hər iki tərəfi $d$-yə bölək və $a'=\frac{a}{d}$, $b'=\frac{b}{d}$ işarə edək:

$$a'(x-x_0)=-b'(y-y_0).$$

Dərs 4-dən bilirik ki, $\mbox{ƏBOB}(a',b')=1$. Sol tərəf $b'$-ə bölünür (çünki sağ tərəf bölünür) və $\mbox{ƏBOB}(a',b')=1$ olduğundan Evklid lemmasına əsasən

$$b'\mid (x-x_0),\qquad\text{yəni}\qquad x-x_0=b't$$

alınır (hansısa tam $t$ üçün). Bunu yerinə yazsaq, $a'b't=-b'(y-y_0)$, buradan da $y-y_0=-a't$ alarıq. Beləliklə, ixtiyari həll göstərilən şəkildə ifadə olunur. Addım 3 (Təkrarlanmanın olmaması). $t_1\ne t_2$ olduqda $b'\ne 0$ olduğuna görə $x_0+b't_1\ne x_0+b't_2$. ■

İsbat. I Hissə: $N=ab-a-b$ ifadə oluna bilməz. Fərz edək ki, hansısa mənfi olmayan tam $x,y$ üçün $ab-a-b=ax+by$. Hər iki tərəfə $a+b$ əlavə edək:

$$ab=a(x+1)+b(y+1).$$

$u=x+1\ge 1$, $v=y+1\ge 1$ işarə edək: $ab=au+bv$. Sağ tərəfdə $b\mid ab$ və $b\mid bv$, deməli $b\mid au$; $\mbox{ƏBOB}(a,b)=1$ olduğuna görə Evklid lemmasına əsasən $b\mid u$, yəni $u\ge b$ alınır. Eyni ilə $a\mid v$, yəni $v\ge a$. Onda

$$ab=au+bv\ge ab+ab=2ab,$$

bu isə $ab>0$ şərtinə ziddir. II Hissə: $n>ab-a-b$ olan hər $n$ ifadə oluna bilər. $\mbox{ƏBOB}(a,b)=1$ olduğundan $ax\equiv n \pmod b$ konqruensiyasının həlli var (növbəti bölmədə bunu rəsmiləşdirəcəyik); bu həlli $0\le x\le b-1$ aralığından seçək. Onda $n-ax$ ədədi $b$-yə bölünür; $y=\frac{n-ax}{b}$ işarə edək. $y\ge 0$ olduğunu göstərmək kifayətdir:

$$n-ax\ge n-a(b-1)>(ab-a-b)-ab+a=-b,$$

yəni $n-ax>-b$. Digər tərəfdən $n-ax$ ədədi $b$-yə bölünür və $-b$-dən böyükdür, deməli $n-ax\ge 0$ və uyğun olaraq $y\ge 0$ alınır. ■

İsbat. Mövcudluq. Yuxarıdakı əlaqəyə əsasən, konqruensiya $ax-my=b$ tənliyinə ekvivalentdir; Teorem 1.1-ə əsasən bunun həlli var $\iff$ $\mbox{ƏBOB}(a,m)\mid b$ (nəzərə alaq ki, $\mbox{ƏBOB}(a,-m)=\mbox{ƏBOB}(a,m)=d$). Sayı. Tutaq ki, $d\mid b$ ödənilir və $x_0$ tənliyin xüsusi həllidir. Teorem 1.2-yə görə bütün tam həllər

$$x=x_0+\frac{m}{d}\,t,\qquad t\in\mathbb{Z}$$

şəklindədir. İndi isə bu həllərdən neçəsinin $m$ moduluna görə fərqli olduğunu müəyyən edək. $t$ və $t'$ eyni qalığı verir $\iff$

$$\frac{m}{d}t\equiv \frac{m}{d}t' \pmod m \iff m\ \Big|\ \frac{m}{d}(t-t')\iff d\mid (t-t').$$

Deməli, $t=0,1,\dots,d-1$ qiymətləri fərqli həllər verir, $t=d$ isə $t=0$-ı təkrarlayır. Beləliklə, fərqli həllərin sayı dəqiq $d$-dir və onlar aşağıdakılardır:

$$x_0,\quad x_0+\frac{m}{d},\quad x_0+2\cdot\frac{m}{d},\quad \dots,\quad x_0+(d-1)\frac{m}{d}.$$

■

İsbat. Hər iki tərəfi $a^{-1}$-ə vuraq: $a^{-1}ax\equiv a^{-1}b$, yəni $x\equiv a^{-1}b$. Tərsinə, $x\equiv a^{-1}b$ olduqda, $ax\equiv aa^{-1}b\equiv b$ — yəni, doğrudan da, həlldir. ■

İsbat. Həllər $x_0,\ x_0+\frac{m}{d},\ \dots,\ x_0+(d-1)\frac{m}{d}$ ədədi silsiləsini təşkil edir. Cəm:

$$S=d\,x_0+\frac{m}{d}\big(0+1+\dots+(d-1)\big)=d\,x_0+\frac{m}{d}\cdot\frac{d(d-1)}{2}.$$

■

İsbat. Mövcudluq (Konstruktiv üsul). Birinci şərt, ixtiyari $k\in\mathbb{Z}$ üçün $x=a+mk$ olması deməkdir. Bunu ikinci şərtdə yerinə yazaq:

$$a+mk\equiv b \pmod n\quad\Longleftrightarrow\quad mk\equiv b-a \pmod n.$$

Bu, $k$-ya nəzərən xətti konqruensiyadır və $\mbox{ƏBOB}(m,n)=1$ olduğuna görə Nəticə 2.2-yə əsasən onun yeganə həlli var:

$$k\equiv m^{-1}(b-a) \pmod n.$$

Belə $k$-nı götürüb $x=a+mk$ bərabərliyinə qoysaq, hər iki şərt ödəniləcək. Yeganəlik. Tutaq ki, $x_1$ və $x_2$ hər ikisi həlldir. Onda

$$x_1\equiv x_2 \pmod m\quad\text{və}\quad x_1\equiv x_2 \pmod n,$$

yəni $m\mid (x_1-x_2)$ və $n\mid (x_1-x_2)$. $\mbox{ƏBOB}(m,n)=1$ olduğundan Dərs 4-ün xassəsinə görə $mn\mid (x_1-x_2)$, yəni $x_1\equiv x_2 \pmod{mn}$ alarıq. Deməli, həll $mn$ moduluna görə yeganədir. ■

İsbat. Riyazi induksiya ilə. $r=2$ halı Teorem 3.1-dir. Tutaq ki, iddia $r-1$ sayda konqruensiya üçün doğrudur. İlk $r-1$ şərti birləşdirək: onlar $M'=m_1\cdots m_{r-1}$ moduluna görə yeganə $x\equiv c \pmod{M'}$ şərtinə ekvivalentdir. Onda sistem

$$x\equiv c \pmod{M'},\qquad x\equiv a_r \pmod{m_r}$$

şəklinə düşür. Burada $\mbox{ƏBOB}(M',m_r)=1$-dir, çünki $m_r$ ədədi $m_1,\dots,m_{r-1}$-in hər biri ilə qarşılıqlı sadədir və deməli onların hasili ilə də qarşılıqlı sadə olacaq (Dərs 4). Teorem 3.1-ə əsasən, bu sistemin $M'm_r=M$ moduluna görə yeganə həlli var. ■

İsbat. $x=a+mk$ yazıb ikinci şərtdə yerinə yazsaq $mk\equiv b-a \pmod n$ alarıq. Teorem 2.1-ə görə, bunun həlli var $\iff$ $\mbox{ƏBOB}(m,n)\mid (b-a)$. Yeganəlik üçün: İki həllin fərqi həm $m$-ə, həm də $n$-ə bölünür, deməli onların Ən Kiçik Ortaq Bölünəninə (ƏKOB), yəni $\mbox{ƏKOB}(m,n)$-ə də bölünür. ■