Modul arifmetikası I

İsbat. Dərs 2-nin qalıqlı bölmə teoreminə görə $a$ və $b$ ədədlərini yeganə şəkildə

$$a = mq_1 + r_1, \qquad b = mq_2 + r_2,$$

$0 \le r_1 < m$, $0 \le r_2 < m$ şəklində yazaq. Bu iki bərabərliyi tərəf-tərəfə çıxaq:

$$a - b = m(q_1 - q_2) + (r_1 - r_2).$$

Kafilik. Tutaq ki, $r_1 = r_2$. Onda $a-b = m(q_1-q_2)$, yəni $m \mid a-b$, deməli $a \equiv b \pmod m$. Zərurilik. İndi tutaq ki, $a \equiv b \pmod m$, yəni $m \mid a-b$. Yuxarıdakı bərabərlikdən

$$r_1 - r_2 = (a-b) - m(q_1-q_2).$$

Sağ tərəfdəki hər iki toplanan $m$-ə bölünür (birincisi şərtə görə, ikincisi aşkar şəkildə), ona görə də Dərs 2-nin xətti kombinasiya xassəsinə əsasən $m \mid r_1 - r_2$. Digər tərəfdən $0 \le r_1 < m$ və $0 \le r_2 < m$ olduğundan

$$-m < r_1 - r_2 < m, \qquad \text{yəni}\quad |r_1 - r_2| < m .$$

$m$-ə bölünən və mütləq qiyməti $m$-dən kiçik olan yeganə tam ədəd sıfırdır. Deməli $r_1 - r_2 = 0$, yəni $r_1 = r_2$. ■

İsbat. (1) $a - a = 0$ və $m \mid 0$. (2) $m \mid a-b$ olarsa, $b-a = -(a-b)$ olduğundan $m \mid b-a$. (3) $m \mid a-b$ və $m \mid b-c$ olsun. Onda Dərs 2-nin xətti kombinasiya xassəsinə görə $m \mid (a-b) + (b-c) = a-c$. ■

İsbat. Şərtə görə $m \mid a-b$ və $m \mid c-d$. (1) $(a+c) - (b+d) = (a-b) + (c-d)$. Sağ tərəf $m$-ə bölünən iki ədədin cəmidir, deməli Dərs 2-nin xətti kombinasiya xassəsinə görə $m$-ə bölünür. Bu isə tərifə görə məhz $a+c \equiv b+d \pmod m$ deməkdir. (2) Eynilə: $(a-c) - (b-d) = (a-b) - (c-d)$, yenə $m$-ə bölünən iki ədədin fərqi. (3) Burada birbaşa çıxarma işə yaramır, çünki $ac - bd$ ifadəsində nə $(a-b)$, nə də $(c-d)$ aşkar görünmür. Klassik üsul eyni ifadəni bir dəfə çıxıb, bir dəfə əlavə etməkdir:

$$ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d).$$

Bu addımı yaxşı başa düşmək lazımdır, çünki şagirdlər məhz burada çaşırlar. Ortadakı $bc$ ədədi süni şəkildə əlavə olunub: onu çıxıb yenidən topladıq, ona görə bərabərlik pozulmadı, amma indi ifadə iki hissəyə ayrıldı — birincisində $a-b$, ikincisində $c-d$ vuruq kimi durur. Hər ikisi $m$-ə bölünür, $c$ və $b$ isə sadəcə tam əmsallardır; deməli yenə xətti kombinasiya xassəsinə görə $m \mid ac-bd$. (4) $n$-ə nəzərən riyazi induksiya üsulu ilə. $n=1$ üçün iddia şərtin özüdür. Tutaq ki, $a^n \equiv b^n \pmod m$ doğrudur. (3) xassəsinə əsasən, bu konqruensiyanı $a \equiv b \pmod m$ konqruensiyası ilə tərəf-tərəfə vursaq, $a^n \cdot a \equiv b^n \cdot b$, yəni $a^{n+1} \equiv b^{n+1} \pmod m$ alınır. İnduksiya tamamlandı. (5) $ka - kb = k(a-b)$; $m \mid a-b$ olduğundan $m \mid k(a-b)$. (Bunu (3)-dən də almaq olardı: $k \equiv k \pmod m$ konqruensiyasını verilənlə vurmaq kifayətdir.) ■

İsbat. $P(x) = c_n x^n + \dots + c_1 x + c_0$ olsun. Teoremin (4) bəndinə görə hər $i$ üçün $a^i \equiv b^i$, sonra (5) bəndinə görə $c_i a^i \equiv c_i b^i$, nəhayət bu $n+1$ konqruensiyanı (1) bəndinə görə tərəf-tərəfə toplasaq, $P(a) \equiv P(b) \pmod m$ alınır. ■

İsbat. Şərtə görə $m \mid ka - kb$, yəni

$$m \mid k(a-b).$$

$d = (k,m)$ işarə edək və Dərs 4-dəki kimi $k = dk'$, $m = dm'$ yazaq; həmin dərsdə isbat etmişdik ki, belə seçimdə $(k', m') = 1$ olur. Bölünməni bu şəkildə yazaq: $dm' \mid dk'(a-b)$, buradan $d$-yə ixtisar etməklə (bu, adi tam ədədlər üçün bölünmə olduğundan tamamilə qanunidir)

$$m' \mid k'(a-b).$$

İndi Dərs 4-dəki Evklid lemmasının ümumiləşməsi işə düşür: $m' \mid k'(a-b)$ və $(m', k') = 1$ olduğundan

$$m' \mid a-b, \qquad \text{yəni}\quad a \equiv b \pmod{m'} .$$

$m' = m/d = m/(k,m)$ olduğundan iddia isbat olundu. Əgər $(k,m)=1$ isə $d=1$, $m'=m$ və modul dəyişmir. ■

Həll. Ədədi tam hesablamağa ehtiyac yoxdur: konqruensiyanın toplama və vurma qaydaları bizə hər bir toplananı ayrılıqda kiçiltməyə imkan verir, çünki $a \equiv a'$ və $b \equiv b'$ olduqda $a + b \equiv a' + b'$ olur. Odur ki, əvvəlcə $2^{10}$ və $3^{10}$ ədədlərini $5$ moduluna görə ayrıca sadələşdirək. Qüvvət qaydasına görə $2^{10} = (2^{2})^{5} = 4^{5}$, burada isə « ən əlverişli nümayəndəni seç» prinsipi işə düşür: $4 \equiv -1 \pmod 5$, çünki $5 \mid 4 - (-1) = 5$. Deməli

$$2^{10} = 4^{5} \equiv (-1)^{5} = -1 \equiv 4 \pmod 5 .$$

İkinci toplanan üçün $3^{10} = (3^{2})^{5} = 9^{5}$ və $9 \equiv -1 \pmod 5$ olduğundan eyni hesablama $3^{10} \equiv (-1)^{5} \equiv 4 \pmod 5$ verir. İndi toplama qaydasını tətbiq edirik:

$$2^{10} + 3^{10} \equiv 4 + 4 = 8 \equiv 3 \pmod 5 .$$

Yoxlama üçün: $2^{10} = 1024 = 5\cdot 204 + 4$ və $3^{10} = 59049 = 5\cdot 11809 + 4$, cəmi $60073 = 5\cdot 12014 + 3$ — doğrudan da qalıq $3$-dür. Cavab: $3$□

Həll. Burada iki alət birləşir: $3$-ə bölünmə üçün rəqəmlərin cəmi əlaməti və konqruensiyaların vurma qaydası. $10 \equiv 1 \pmod 3$ olduğundan $10^{i} \equiv 1$ və beləliklə istənilən $n$ ədədi öz rəqəmlərinin cəmi $T(n)$ ilə $3$ moduluna görə eyni qalığı verir. Birinci vuruq üçün

$$T(13579) = 1+3+5+7+9 = 25 \equiv 1 \pmod 3,$$

çünki $25 = 3\cdot 8 + 1$. İkinci vuruq üçün

$$T(24680) = 2+4+6+8+0 = 20 \equiv 2 \pmod 3,$$

çünki $20 = 3\cdot 6 + 2$. Vurma qaydası deyir ki, $a \equiv a'$ və $b \equiv b'$ olduqda $ab \equiv a'b'$; deməli

$$13579 \cdot 24680 \equiv 1 \cdot 2 = 2 \pmod 3 .$$

Diqqət edin ki, nəhəng hasili heç vaxt hesablamadıq — konqruensiya dilinin bütün gücü elə budur: böyük ədədləri ən kiçik nümayəndələri ilə əvəz edib yalnız kiçik ədədlərlə işləyirik. Cavab: $2$□

Həll. $6 = 2 \cdot 3$ və $(2,3) = 1$ olduğundan, Dərs 4-dəki xassəyə görə bir ədədin $6$-ya bölünməsini isbat etmək üçün onun həm $2$-yə, həm də $3$-ə bölündüyünü göstərmək kifayətdir. Ona görə də məsələni iki müstəqil hissəyə ayırırıq və hər birində $n$-in mümkün qalıqlarına əsasən hallara ayırırıq — bu, konqruensiya dilində çox qısa alınır, çünki $n \equiv r \pmod m$ olduqda çoxhədli nəticəsinə görə $P(n) \equiv P(r) \pmod m$. Burada $P(x) = x(x+1)(x+2)$. $2$ moduluna görə: $n \equiv 0$ olarsa $P(n) \equiv 0\cdot 1\cdot 2 = 0$; $n \equiv 1$ olarsa $P(n) \equiv 1\cdot 2\cdot 3 = 6 \equiv 0 \pmod 2$. Hər iki halda $2 \mid P(n)$. $3$ moduluna görə: $n \equiv 0$ olarsa $P(n) \equiv 0$; $n \equiv 1$ olarsa $P(n) \equiv 1\cdot 2\cdot 3 = 6 \equiv 0$; $n \equiv 2$ olarsa $P(n) \equiv 2\cdot 3\cdot 4 = 24 \equiv 0 \pmod 3$. Hər üç halda $3 \mid P(n)$. Beləliklə $2 \mid P(n)$ və $3 \mid P(n)$; $(2,3)=1$ olduğundan $6 \mid P(n)$, yəni ardıcıl üç tam ədədin hasili həmişə $6$-ya bölünür. (Mahiyyət odur ki, ardıcıl üç ədəd arasında mütləq bir cüt ədəd və mütləq bir $3$-ə bölünən ədəd var.) Cavab: İsbat olundu□

Həll. Konqruensiyanın tərifi bizə dərhal struktur verir: $a \equiv b \pmod m$ deməkdir ki, $m \mid a - b$, yəni uyğun tam $k$ üçün

$$a = b + km .$$

İndi iddianı bilavasitə ƏBOB-un tərifi ilə deyil, daha güclü bir yolla — $a$ ilə $m$-in ortaq bölənləri çoxluğunun $b$ ilə $m$-in ortaq bölənləri çoxluğu ilə eyni olduğunu göstərməklə isbat edək; iki çoxluq eynidirsə, onların ən böyük elementi də eynidir. Tutaq ki, $d \mid b$ və $d \mid m$. Onda Dərs 2-dəki xətti kombinasiya xassəsinə görə $d \mid b\cdot 1 + m\cdot k$, yəni $d \mid a$. Deməli $b$ ilə $m$-in hər ortaq böləni həm də $a$ ilə $m$-in ortaq bölənidir. Tərsinə, $d \mid a$ və $d \mid m$ olsun. Eyni xassəni $b = a - km$ bərabərliyinə tətbiq edirik: $d \mid a\cdot 1 + m\cdot(-k)$, yəni $d \mid b$. Deməli $a$ ilə $m$-in hər ortaq böləni $b$ ilə $m$-in də ortaq bölənidir. Hər iki altçoxluq münasibəti çoxluqların bərabərliyini verir, buradan isə $(a,m) = (b,m)$. Bu nəticə çox faydalıdır: məsələn, $(a,m)$-i hesablamaq üçün $a$-nı öz ən kiçik qalığı ilə əvəz etmək olar — elə Evklid alqoritminin birinci addımı da məhz budur. Cavab: İsbat olundu□

Həll. Xeyr, olmaz. Konqruensiyalarda « hər iki tərəfi eyni ədədə bölmək» adi bərabərlikdəki kimi sərbəst əməliyyat deyil, çünki $m \mid k(x-y)$ olmasından $m \mid x-y$ alınmır — $k$ ilə $m$ ortaq bölənə malik olduqda $m$-in bir hissəsi $k$ tərəfindən « udulur». Konkret əks-nümunə quraq: $x = 1$, $y = 5$ götürək. Onda $3x = 3$ və $3y = 15$, fərq $15 - 3 = 12$ olduğundan $3x \equiv 3y \pmod{12}$ doğrudur. Amma $y - x = 4$ və $12 \nmid 4$, yəni $x \not\equiv y \pmod{12}$. Deməli sadəcə $3$-ə bölmək yanlış nəticəyə aparır. Düzgün alət ixtisar qaydasıdır: $ka \equiv kb \pmod m$ olduqda

$$a \equiv b \pmod{\tfrac{m}{(k,m)}} .$$

Burada $k = 3$, $m = 12$ və $(3,12) = 3$, deməli modul $12/3 = 4$-ə qədər kiçilir:

$$3x \equiv 3y \pmod{12} \iff x \equiv y \pmod 4 .$$

Əks-nümunəmiz bunu təsdiqləyir: $1 \equiv 5 \pmod 4$, çünki $4 \mid 4$. Yəni informasiya itmir, sadəcə modul $12$-dən $4$-ə düşür. Cavab: Olmaz; düzgün nəticə $x \equiv y \pmod 4$-dür (əks-nümunə: $x=1$, $y=5$)□

Həll. Cəmdə $100$ toplanan var, lakin onların böyük əksəriyyəti $15$ moduluna görə sıfıra çevrilir — bu, faktorial olan məsələlərdə əsas ideyadır. Doğrudan da $15 = 3\cdot 5$ və $5! = 120 = 15 \cdot 8$, deməli $15 \mid 5!$. Əgər $n \geq 5$ olarsa, $n! = 5!\cdot 6\cdot 7\cdots n$ yazılışı göstərir ki, $5! \mid n!$, buradan da tranzitivliklə $15 \mid n!$, yəni $n! \equiv 0 \pmod{15}$. Beləliklə cəmdəki $5!, 6!, \dots, 100!$ toplananlarının hamısı $15$ moduluna görə $0$-a konqruentdir və toplama qaydasına görə onları sadəcə ata bilərik:

$$\sum_{n=1}^{100} n! \equiv 1! + 2! + 3! + 4! \pmod{15}.$$

Qalan dörd toplananı hesablayaq:

$$1 + 2 + 6 + 24 = 33 .$$

Nəhayət $33 = 15\cdot 2 + 3$, yəni $33 \equiv 3 \pmod{15}$. Deməli axtarılan qalıq $3$-dür. (Diqqət: qalıq $0 \le r < 15$ aralığında olmalıdır, ona görə $33$-ü də sona qədər kiçiltdik.) Cavab: $3$□

Həll. Konqruensiyanın tərifinə qayıdaq: $11! \equiv 10! \pmod n$ o deməkdir ki, $n \mid 11! - 10!$. Deməli sual əslində belədir: $11! - 10!$ ədədinin neçə natural böləni var? Fərqi vuruqlara ayıraq — $10!$ ortaq vuruğunu çıxarmaq kifayətdir:

$$11! - 10! = 10!\,(11 - 1) = 10!\cdot 10 .$$

İndi $10!$-in kanonik ayrılışını quraq. $10!$-də $2$-nin qüvvəti $2,4,6,8,10$ vuruqlarından gəlir və $1+2+1+3+1 = 8$-ə bərabərdir; $3$-ün qüvvəti $3,6,9$-dan $1+1+2 = 4$; $5$-in qüvvəti $5,10$-dan $2$; $7$-nin qüvvəti $1$. Yəni

$$10! = 2^{8}\cdot 3^{4}\cdot 5^{2}\cdot 7 .$$

Buna $10 = 2\cdot 5$ vuruğunu əlavə edirik:

$$11! - 10! = 2^{9}\cdot 3^{4}\cdot 5^{3}\cdot 7 = 36\,288\,000 .$$

Dərs 3-dəki $\tau$ düsturuna görə bölənlərin sayı, sadə vuruqların qüvvət üstlərinin bir vahid artırılmış qiymətlərinin hasilidir:

$$\tau = (9+1)(4+1)(3+1)(1+1) = 10\cdot 5\cdot 4\cdot 2 = 400 .$$

Beləliklə şərti ödəyən $400$ ədəd $n$ var. (Qeyd edək ki, $n = 1$ də sayılır: $1$ moduluna görə bütün ədədlər konqruentdir.) Cavab: $400$□

Həll. Birinci hissə əslində qüvvət qaydasının özüdür, lakin onu induksiya ilə səliqəli isbat edək — belə ki, qüvvət qaydası vurma qaydasının təkrarından doğur. $k = 1$ üçün iddia şərtin özüdür: $m \mid a - b$. İndi tutaq ki, hansısa $k$ üçün $a^{k} \equiv b^{k} \pmod m$ doğrudur. Bu konqruensiyanı ilkin $a \equiv b \pmod m$ konqruensiyası ilə vurma qaydasına görə tərəf-tərəfə vururuq:

$$a^{k}\cdot a \equiv b^{k}\cdot b, \quad \text{yəni} \quad a^{k+1} \equiv b^{k+1} \pmod m .$$

Deməli iddia $k+1$ üçün də doğrudur və induksiya ilə bütün natural $k$-lar üçün $a^{k} \equiv b^{k} \pmod m$, yəni $m \mid a^{k} - b^{k}$. İndi bu aləti $2^{30} - 1$ üçün işlədək. $31$ moduluna görə $2$-nin qüvvətlərinə baxdıqda ən əlverişli nümayəndə $2^{5} = 32$-dir, çünki $32 = 31 + 1$, yəni

$$2^{5} \equiv 1 \pmod{31} .$$

Bu, düzgün modulun seçilməsinin bütün sirridir: $31$-i məhz $32$-yə yaxın olduğu üçün seçdik. İndi isbat etdiyimiz xassəni $a = 2^{5}$, $b = 1$, $k = 6$ ilə tətbiq edirik:

$$2^{30} = (2^{5})^{6} \equiv 1^{6} = 1 \pmod{31},$$

buradan $2^{30} - 1 \equiv 0 \pmod{31}$, yəni $31 \mid 2^{30} - 1$. (Həqiqətən $2^{30} - 1 = 1\,073\,741\,823 = 31\cdot 34\,636\,833$.) Cavab: İsbat olundu; $31 \mid 2^{30}-1$□

İsbat. $10 - 1 = 9$ olduğundan $10 \equiv 1 \pmod 9$. Birinci bölmənin əsas əməliyyatlar teoreminin (4) bəndinə görə hər $i \ge 0$ üçün

$$10^i \equiv 1^i = 1 \pmod 9 .$$

İndi (5) bəndinə görə hər $i$ üçün $a_i \cdot 10^i \equiv a_i \cdot 1 = a_i \pmod 9$, və nəhayət (1) bəndinə görə bu $k+1$ konqruensiyanı tərəf-tərəfə toplasaq:

$$n = \sum_{i=0}^{k} a_i 10^i \equiv \sum_{i=0}^{k} a_i = T(n) \pmod 9 .$$

$3 \mid 9$ olduğundan $10 - 1 = 9$ ədədi $3$-ə də bölünür, yəni $10 \equiv 1 \pmod 3$ də doğrudur və eyni hesablama hərfi-hərfinə təkrarlanır. Nəhayət, xüsusi hal: $n \equiv T(n)$ olduğundan tranzitivliklə $n \equiv 0 \iff T(n) \equiv 0$, yəni $9 \mid n \iff 9 \mid T(n)$. ■

İsbat. $n \equiv T(n) \pmod 9$ tərifə görə elə $9 \mid n - T(n)$ deməkdir. ■

İsbat. $10 - (-1) = 11$ olduğundan $10 \equiv -1 \pmod{11}$. Deməli hər $i$ üçün

$$10^i \equiv (-1)^i \pmod{11},$$

yəni cüt $i$-lər üçün $10^i \equiv 1$, tək $i$-lər üçün isə $10^i \equiv -1$. Hər həddi $a_i$-yə vurub toplasaq:

$$n = \sum_{i=0}^{k} a_i 10^i \equiv \sum_{i=0}^{k} (-1)^i a_i \pmod{11}.$$

■

İsbat. $10^k = 2^k \cdot 5^k$ olduğundan $2^k \mid 10^k$, yəni

$$10^k \equiv 0 \pmod{2^k}.$$

Onda hər $i \ge k$ üçün $10^i = 10^k \cdot 10^{i-k} \equiv 0 \cdot 10^{i-k} = 0 \pmod{2^k}$. İndi $n$-i iki hissəyə ayıraq: son $k$ rəqəmindən düzələn $s = a_{k-1} 10^{k-1} + \dots + a_1 \cdot 10 + a_0$ ədədi və qalan hissə:

$$n = \underbrace{\sum_{i \ge k} a_i 10^i}_{\text{hər həddi } \equiv\, 0} + \; s \; \equiv \; s \pmod{2^k}.$$

$5^k \mid 10^k$ olduğundan eyni mühakimə $5^k$ modulu üçün də söz-söz təkrarlanır. ■