Modul Arifmetikası II — Onlayn dərslik

1Qüvvətlərin qalıqlarının dövriliyiDərs 5-də

3^{100}

7^{2026}

və bu tipli ifadələrin qalığını taparkən hər dəfə eyni halla qarşılaşdıq: ədədin qüvvətlərini bir-bir hesabladıqca qalıqlar müəyyən addımdan sonra təkrarlanmağa başladı. O zaman biz bundan xoş bir təsadüf kimi istifadə etdik — «bax,

2^3 \equiv 1

alındı, deməli qüvvət üstünü üç-üç ayıra bilərik» dedik və irəlilədik. Amma orada bir sual cavabsız qalmışdı: bu təkrarlanma həmişəmi baş verir, yoxsa bəzi ədədlərə məxsus xüsusi haldır? Bəlkə, elə

a

və elə

m

var ki,

a

-nın qüvvətlərinin qalıqları sonsuza qədər heç təkrarlanmadan davam edir? Bu bölmədə bu məsələyə aydınlıq gətirəcəyik. Göstərəcəyik ki, təkrarlanma qaçılmazdır — o, heç bir təsadüfdən asılı deyil, sırf «qalıqların sayının sonlu olması» faktından irəli gəlir. Sonra, qarşılıqlı sadə ədədlər halında bu təkrarlanmanın xüsusilə səliqəli bir forma aldığını görəcəyik və nəhayət, bunu praktik hesablama alətinə çevirəcəyik: istənilən böyük qüvvət üstünü daha kiçik bir ədədə qədər azaltmağı öyrənəcəyik.

Teorem 1.1 (Dövriliyin zəruriliyi). Tutaq ki,

m \ge 2

tam ədədi və ixtiyari

a

tam ədədi verilmişdir. Onda

a^1,\quad a^2,\quad a^3,\quad a^4,\quad \dots

ardıcıllığının

m

moduluna görə qalıqları mütləq təkrarlanır: elə

1 \le i < j

natural ədədləri var ki,

a^i \equiv a^j \pmod m .

İsbat. İsbatın əsasında çox sadə bir müşahidə dayanır: hər hansı tam ədədin

m

moduluna görə qalığı yalnız

0,\; 1,\; 2,\; \dots,\; m-1

qiymətlərindən birini ala bilər. Bu, Dərs 2-dəki qalıqlı bölmə haqqında teoremdən birbaşa irəli gəlir:

a^n

ədədini

m

-ə böldükdə

a^n = mq + r

0 \le r < m

alırıq və

r

üçün cəmi

m

fərqli imkan var. Deməli, əlimizdə sonsuz sayda həddi olan bir ardıcıllıq var —

a^1, a^2, a^3, \dots

— lakin bu ardıcıllığın hədlərinin qalıqları cəmi

m

fərqli «yuva»dan (qalıq sinfindən) birinə düşür. Konkret olaraq ilk

m+1

ədədi götürək:

a^1,\ a^2,\ \dots,\ a^{m+1}.

Bunlar

m+1

sayda ədəddir, mümkün qalıq isə cəmi

m

növdür.

m+1 > m

olduğuna görə bu ədədlərdən ən azı ikisi eyni qalığı verməlidir — əks halda

m+1

ədədin hamısı fərqli qalıqlara sahib olardı, yəni

m

növ qalıq

m+1

müxtəlif qiymət verə bilərdi ki, bu da mümkün deyil. Məhz bu mühakimə Dirixle prinsipi (və ya göyərçin yuvası prinsipi) adlanır: əgər

m

sayda yuvaya

m+1

sayda göyərçin yerləşdirilsə, hansısa yuvada ən azı iki göyərçin olacaq. Bizim halda «yuvalar»

0,1,\dots,m-1

qalıqları, «göyərçinlər» isə

a^1, \dots, a^{m+1}

qüvvətləridir. Beləliklə, elə

1 \le i < j \le m+1

tapılır ki,

a^i

və

a^j

eyni qalığı verir, yəni Dərs 5-in tərifinə görə

a^i \equiv a^j \pmod m

Qeyd. Bu teoremin gücü onun çox az şərt tələb etməsindədir:

a

haqqında heç bir əlavə şərt yoxdur.

a

mənfi ola bilər,

m

-ə bölünə bilər,

m

ilə ortaq bölənləri ola bilər — fərqi yoxdur. Sonlu sayda qalıq və sonsuz sayda qüvvət — təkrarlanma üçün bu qədəri bəs edir. Diqqət yetirin ki, teorem təkrarlanmanın harada baş verdiyini demir, yalnız baş verdiyini deyir; üstəlik, isbatdan əlavə bir nəticə də alırıq: təkrar ən geci

(m+1)

-ci addıma qədər baş verməlidir.

Bu teorem bizə təkrarlanmanın varlığını sübut etdi. Amma hesablamalar aparmaq üçün bu, hələ yetərli deyil. Bizə daha konkret bir fakt lazımdır: ardıcıllığın elə əvvəldən dövri olması və dövrün

1

qalığından başlaması — çünki

a^k \equiv 1

münasibəti hesablamalarda ən əlverişli istinad nöqtəsidir. Aşağıdakı teorem məhz bunu verir, amma bir şərtlə.

Teorem 1.2 (Qarşılıqlı sadə ədədlər halında tam dövrilik). Tutaq ki,

m \ge 2

və

(a,m) = 1

. Onda elə ən kiçik

k \ge 1

natural ədədi var ki,

a^k \equiv 1 \pmod m .

İsbat. Əvvəlki teoremə görə elə

1 \le i < j

var ki,

a^i \equiv a^j \pmod m .

Bu münasibətin sağ tərəfini

a^j = a^i \cdot a^{\,j-i}

şəklində yazaq:

a^i \cdot 1 \equiv a^i \cdot a^{\,j-i} \pmod m .

İndi hər iki tərəfi

a^i

-yə «ixtisar etmək» istəyirik. Dərs 5-in ixtisar qaydası deyir ki,

ka \equiv kb \pmod m

olduqda

a \equiv b \pmod{m/(k,m)}

; yəni modul yalnız o halda dəyişmir ki,

(k,m) = 1

olsun. Bizim halda

k

rolunu

a^i

oynayır, deməli,

(a^i, m) = 1

olduğunu yoxlamalıyıq. Bu, Dərs 4-dəki qarşılıqlı sadəlik qaydalarından irəli gəlir:

(a,m) = 1

olduqda

a

və

m

-in ortaq sadə vuruğu yoxdur;

a^i

ədədinin sadə vuruqları isə məhz

a

-nın sadə vuruqlarıdır (kanonik ayrılışda yalnız qüvvət üstləri

i

dəfə artır, yeni sadə ədəd əlavə olunmur). Deməli,

a^i

ilə

m

-in də ortaq sadə vuruğu yoxdur, yəni

(a^i, m) = 1

. İndi ixtisar qaydasını tətbiq edirik: modul dəyişmir və

1 \equiv a^{\,j-i} \pmod m

alınır. Burada

j - i \ge 1

olduğuna görə

a^{\,j-i}

həqiqətən natural üstlü qüvvətdir. Beləliklə,

a^t \equiv 1 \pmod m

şərtini ödəyən ən azı bir

t \ge 1

natural ədədi mövcuddur. Deməli, belə natural ədədlərin çoxluğu boş deyil; boş olmayan hər natural ədədlər çoxluğunun isə ən kiçik elementi var. Həmin ən kiçiyi

k

ilə işarə edirik.

Qeyd. Bu teoremdə

(a,m) = 1

şərti sadəcə formal deyil, həqiqətən də vacibdir. Əgər

(a,m) > 1

olsa,

a^k \equiv 1

münasibəti heç vaxt ödənə bilməz. Doğrudan da,

d = (a,m) > 1

olsun.

a^k \equiv 1 \pmod m

olsaydı,

m \mid a^k - 1

olardı;

d \mid m

olduğuna görə

d \mid a^k - 1

alınardı. Digər tərəfdən

d \mid a

, deməli

d \mid a^k

. Onda

d

həm

a^k

-nı, həm də

a^k - 1

-i böldüyünə görə (Dərs 2-nin xətti kombinasiyanın xassəsi) onların fərqini, yəni

1

-i də bölərdi — bu isə

d > 1

şərti ilə ziddiyyət təşkil edir. Belə halda ardıcıllıq yenə də təkrarlanır (birinci teorem heç bir əlavə şərt tələb etmirdi), amma dövr başlamazdan əvvəl bir dövrəqədərki hissə (və ya «quyruq») olur; bunu bölmənin sonunda ayrıca müzakirə edəcəyik.

Tərif 1.3 (Dövrün uzunluğu).

(a,m) = 1

olsun.

a^k \equiv 1 \pmod m

şərtini ödəyən ən kiçik

k \ge 1

natural ədədinə

a

-nın

m

moduluna görə dövrünün uzunluğu deyilir.

Qeyd. Bu anlayışın rəsmi adı və dərin xassələri — xüsusən onun

m

-dən necə asılı olması, hansı ədədləri bölməsi və s. — Dərs 7-nin mövzusudur. Orada bu suallara ümumi teoremlərlə cavab verəcəyik. İndilik biz

k

-nı sadəcə birbaşa hesablanan praktik alət kimi işlədirik: verilmiş konkret

a

və

m

üçün

a^1, a^2, a^3, \dots

qalıqlarını ardıcıl yazır və ilk dəfə

1

göründüyü yeri qeyd edirik. Kiçik modullarda bu, bir neçə saniyəlik işdir.

İndi bu anlayışın bütün faydası aşağıdakı teoremdə üzə çıxır.

Teorem 1.4 (Qüvvət üstünün kiçildilməsi).

(a,m) = 1

və

k

—

a

-nın

m

moduluna görə dövrünün uzunluğu olsun. Onda istənilən

n \ge 1

natural ədədi üçün

a^n \equiv a^r \pmod m,

burada

r

—

n

-in

k

-ya bölünməsindən alınan qalıqdır, yəni

n = qk + r

0 \le r < k

İsbat. Addım-addım gedək. İlk növbədə

n

ədədini

k

-ya qalıqlı bölürük (Dərs 2): elə yeganə

q \ge 0

və

0 \le r < k

var ki,

n = qk + r .

İndi qüvvətin xassələrindən istifadə edirik:

a^n = a^{qk + r} = a^{qk} \cdot a^{r} = \left(a^{k}\right)^{q} \cdot a^{r}.

Bu, sırf cəbri çevirmədir, hələ heç bir modul mühakiməsi aparılmayıb. İndi modul daxil olur. Tərifə görə

a^k \equiv 1 \pmod m

. Dərs 5-in qüvvət qaydasına görə konqruensiyanın hər iki tərəfini eyni

q

dərəcəsinə yüksəltmək olar:

\left(a^{k}\right)^{q} \equiv 1^{q} = 1 \pmod m .

Nəhayət, Dərs 5-in vurma qaydasına görə bu konqruensiyanın hər iki tərəfini eyni

a^r

ədədinə vururuq:

\left(a^{k}\right)^{q} \cdot a^{r} \equiv 1 \cdot a^{r} = a^{r} \pmod m .

Sol tərəf isə elə

a^n

-dir. Deməli,

a^n \equiv a^r \pmod m

Bu teorem çox böyük qüvvət üstləri ilə işləməyi asanlaşdırır:

a^{2026}

və ya

a^{10^{100}}

kimi ifadələr

a^0, a^1, \dots, a^{k-1}

siyahısındakı kiçik bir üzvə çevrilir. Bütün iş

k

-nı düzgün tapmaq və qüvvət üstünü məhz $k$ -ya görə kiçiltməkdir. Növbəti qeyd tam da bu son cümlə haqqındadır.

Qeyd. Şagirdlərin bu mövzuda buraxdığı ən yayğın səhv budur: qüvvət üstünü modula görə kiçiltmək. Yəni

2^{100} \pmod 7

hesablayarkən

100

-ü

7

-yə bölmək. Bu, kobud səhvdir. Qüvvət üstü dövrün uzunluğuna görə kiçildilir, modula görə yox — teoremdə

n = qk + r

yazılıb,

n = qm + r

yox. Fərqi konkret görək.

2

-nin

7

moduluna görə qüvvətləri:

2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 = 8 \equiv 1 \pmod 7 .

Deməli, dövrün uzunluğu

k = 3

-dür (modul isə

7

-dir!). YANLIŞ yanaşma:

100 = 7 \cdot 14 + 2

, deməli, guya

2^{100} \equiv 2^2 = 4 \pmod 7

. DOĞRU yanaşma:

100 = 3 \cdot 33 + 1

, deməli

2^{100} = \left(2^{3}\right)^{33} \cdot 2^{1} \equiv 1^{33} \cdot 2 = 2 \pmod 7 .

Hesablama ilə yoxlanır ki, doğru cavab

2

-dir. Yanlış yanaşma

4

verirdi — yəni tamamilə yanlış nəticə. Yadda saxlayın: modul

m

ilə dövrün uzunluğu

k

iki ayrı ədəddir və onları qarışdırmaq hesablamanı tamamilə pozur.

Nümunə 1.1 (Son rəqəmin dövriliyi cədvəli). Ədədin son rəqəmi onun

10

moduluna görə qalığıdır. Deməli, qüvvətlərin son rəqəmini öyrənmək üçün

0,1,\dots,9

rəqəmlərinin

10

moduluna görə dövrlərini bilmək kifayətdir. Onları ardıcıl hesablayaq (hər sətirdə

a^1, a^2, a^3, a^4

qalıqları):

\begin{array}{c|cccc|c} a & a^1 & a^2 & a^3 & a^4 & \text{dövr} \\ \hline 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 4 & 8 & 6 & 4 \\ 3 & 3 & 9 & 7 & 1 & 4 \\ 4 & 4 & 6 & 4 & 6 & 2 \\ 5 & 5 & 5 & 5 & 5 & 1 \\ 6 & 6 & 6 & 6 & 6 & 1 \\ 7 & 7 & 9 & 3 & 1 & 4 \\ 8 & 8 & 4 & 2 & 6 & 4 \\ 9 & 9 & 1 & 9 & 1 & 2 \end{array}

Cədvəldən istifadə qaydası: hər sətirdə qiymətlər göstərilən uzunluqda təkrarlanır. Məsələn,

2

üçün

2,4,8,6,\ 2,4,8,6,\ \dots

;

4

üçün

4,6,4,6,\dots

;

5

və

6

üçün isə qiymət heç dəyişmir. Ən vacib müşahidə: bütün dövr uzunluqları

1

2

və ya

4

-dür, yəni hamısı

4

-ün bölənidir. Deməli, son rəqəmi tapmaq üçün qüvvət üstünü $4$ -ə görə azaltmaq həmişə kifayətdir —

a

nə olursa-olsun. Yalnız bir texniki incəliyə diqqət yetirin: üstü azaldarkən qalıq

0

alınarsa,

a^4

(yəni cədvəlin dördüncü sütunu) götürülür,

a^0 = 1

yox; çünki

2

5

6

kimi rəqəmlər üçün ardıcıllıq

1

-dən başlamır.

Nümunə 1.2.

2^{2026}

ədədinin son rəqəmini tapaq. Yuxarıdakı cədvələ görə

2

-nin son rəqəmlərinin dövrü

2,4,8,6

-dır və uzunluğu

4

-dür. Qüvvət üstünü

4

-ə qalıqlı bölürük:

2026 = 4 \cdot 506 + 2 .

Qalıq

2

-dir, deməli

2^{2026}

-nın son rəqəmi dövrün ikinci üzvüdür, yəni

\mathbf{4}

. Eyni şeyi açıq şəkildə də göstərmək olar:

2^4 = 16 \equiv 6 \pmod{10}

olduğuna görə

1

alınmır, ona görə də dövrü birbaşa istifadə edirik:

2^{2026} = \left(2^{4}\right)^{506} \cdot 2^{2},

və cədvəldən bilirik ki,

2

-nin qüvvətlərinin son rəqəmləri dördlük qruplarla təkrarlanır; qalıq

2

olduğuna görə cavab

2^2 = 4

-ün son rəqəmi, yəni

4

-dür. Hesablama bunu təsdiqləyir.

Nümunə 1.3.

3

-ün

7

moduluna görə dövrünü tapaq və

3^{1000} \pmod 7

hesablayaq. Əvvəlcə qüvvətləri ardıcıl yazırıq (hər addımda əvvəlkini

3

-ə vurub

7

-yə görə kiçildirik — Dərs 5-dəki addım-addım kiçiltmə üsulu):

\begin{array}{c|cccccc} n & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 3^n \bmod 7 & 3 & 2 & 6 & 4 & 5 & 1 \end{array}

Yoxlama:

3^1 = 3

;

3 \cdot 3 = 9 \equiv 2

;

2 \cdot 3 = 6

;

6 \cdot 3 = 18 \equiv 4

;

4 \cdot 3 = 12 \equiv 5

;

5 \cdot 3 = 15 \equiv 1

. İlk dəfə

1

məhz

n = 6

-da göründü, deməli dövrün uzunluğu

k = 6

-dır. (Diqqət: burada dövr bütün sıfırdan fərqli qalıqları —

3,2,6,4,5,1

— əhatə etdi. Bunun təsadüf olub-olmadığına Dərs 7-də aydınlıq gətiriləcək.) İndi üstü

6

-ya görə azaldırıq:

1000 = 6 \cdot 166 + 4 .

Deməli

3^{1000} = \left(3^{6}\right)^{166} \cdot 3^{4} \equiv 1^{166} \cdot 3^{4} \equiv 4 \pmod 7 .

Cavab:

3^{1000} \equiv 4 \pmod 7

. Hesablama ilə təsdiqlənir.

Qüvvət qülləsi: qüvvətin qüvvəti. Olimpiadalarda

a^{b^c}

şəklində «qüvvət qülləsi» ifadələrinə tez-tez rast gəlinir. Burada qüvvət üstü özü də çox böyük bir ədəddir və onu hesablamaq mümkün deyil. Amma bizə onun dəqiq qiyməti lazım deyil — yalnız dövrün uzunluğuna görə qalığı lazımdır. Bu, məsələni ikimərhələli işə çevirir:

1. $a$ -nın $m$ moduluna görə dövrünün uzunluğu olan $k$ -nı tap (bu, birinci, «xarici» məsələdir);
2. $b^{c}$ ədədinin $k$ moduluna görə qalığı olan $r$ -i hesabla (bu, ikinci, «daxili» məsələdir — və o, adətən daha kiçik və daha asandır, çünki $k$ ədədi kiçikdir);
3. cavab $a^{r} \pmod m$ olur.

Diqqət yetirin ki, ikinci addımda modul

m

deyil,

k

-dır. Qüllənin hər mərtəbəsində modul dəyişir — bu, üsulun mahiyyətidir. Konkret nümunə:

2^{3^{100}} \pmod 5

hesablayaq. Addım 1.

2

-nin

5

moduluna görə dövrünü tapırıq:

2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 = 8 \equiv 3,\quad 2^4 = 16 \equiv 1 \pmod 5 .

Deməli

k = 4

. (Həmçinin

(2,5) = 1

, yəni teoremin şərti ödənir.) Addım 2. İndi qüvvət üstünü, yəni

3^{100}

ədədini

4

moduluna görə hesablamalıyıq. Burada Dərs 5-dəki mənfi qalıqdan (nümayəndədən) istifadə etmək çox əlverişlidir:

3 \equiv -1 \pmod 4 \quad \Longrightarrow \quad 3^{100} \equiv (-1)^{100} = 1 \pmod 4 .

Deməli

3^{100} = 4q + 1

şəklindədir, yəni

r = 1

. Addım 3. Qüvvət üstünün kiçildilməsi teoreminə görə

2^{3^{100}} \equiv 2^{1} = 2 \pmod 5 .

Cavab:

\mathbf{2}

. Hesablama bunu təsdiqləyir (kompüter

3^{100}

-ü tam şəkildə hesablayıb yoxlaya bilir və nəticə eynidir). Xəbərdarlıq. Bu üsul məhz bu sadəlikdə yalnız

(a,m) = 1

olduqda işləyir. Əks halda

a^k \equiv 1

münasibəti yoxdur (yuxarıdakı qeydə baxın) və üstü sərbəst şəkildə dövrə görə azaltmaq olmaz — ilk bir neçə həddə xüsusi diqqət tələb olunur.

Qeyd. Şərtin nə qədər zəruri olduğunu bir misalda görək.

a = 2

m = 12

götürək; burada

(2,12) = 2 \ne 1

. Qüvvətlərin qalıqlarını yazaq:

\begin{array}{c|cccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 2^n \bmod 12 & 2 & 4 & 8 & 4 & 8 & 4 & 8 & 4 \end{array}

Göründüyü kimi, ardıcıllıq

n \ge 2

-dən başlayaraq

4, 8, 4, 8, \dots

şəklində dövri olur, lakin əvvəldə dövrə daxil olmayan bir hədd var: birinci hədd olan

2

bir daha heç vaxt təkrarlanmır. Belə başlanğıc hissəyə « dövrəqədərki hissə » (və ya « quyruq») demək olar. Diqqət edin: birinci teoremimiz burada da doğrudur — təkrarlanma var (

2^2 \equiv 2^4 \equiv 4

). Pozulan şey ikinci teoremdir:

1

qalığı bu ardıcıllıqda heç vaxt görünmür, yəni

2^k \equiv 1 \pmod{12}

şərtini ödəyən

k

mövcud deyil. Bunu artıq nəzəri olaraq da isbat etmişdik:

d = (a,m) > 1

olduqda

a^k \equiv 1

mümkün deyil. Praktik nəticə:

(a,m) > 1

halında üstü azaltmaq üçün ardıcıllığın harada dövrə girdiyini əl ilə müəyyənləşdirmək və üstün kiçik qiymətlərini ayrıca yoxlamaq lazımdır. Bu tip məsələlərdə çox vaxt daha rahat yol

m

-i qarşılıqlı sadə vuruqlara ayırıb hər birinə ayrıca baxmaqdır — bu texnikanı Dərs 7–8-də sistemləşdirəcəyik.

Məsələ 1.

3^{2027}

ədədinin son rəqəmini tapın.

Həll. Son rəqəm dedikdə ədədin

10

modulunda qalığı nəzərdə tutulur, ona görə bütün hesablamanı

\bmod\ 10

aparmaq kifayətdir. Əvvəlcə

3

-ün qüvvətlərinin son rəqəmlərinə baxaq:

3^1\equiv 3

3^2\equiv 9

3^3\equiv 27\equiv 7

3^4\equiv 21\equiv 1\ (\mathrm{mod}\ 10)

3^4\equiv 1

alındığı üçün buradan sonra hər şey təkrarlanır:

3^5\equiv 3^4\cdot 3\equiv 3

və s., yəni son rəqəmlər

3,9,7,1

dövrü ilə gedir, dövrün uzunluğu

k=4

-dür. Deməli,

3^n

-in son rəqəmi yalnız

n

-in

4

-ə bölünməsindən alınan qalıqdan asılıdır:

3^n\equiv 3^{\,n\bmod 4}\ (\mathrm{mod}\ 10)

. İndi üstü dövrə görə azaldırıq:

2027=4\cdot 506+3

, yəni

2027\equiv 3\ (\mathrm{mod}\ 4)

. Onda

3^{2027}\equiv 3^{3}\equiv 7\ (\mathrm{mod}\ 10)

. Cavab:

7

Məsələ 2.

2^{2026}

ədədinin

13

-ə bölünməsindən alınan qalığı tapın.

Həll. Qüvvət üstü çox böyükdür, ona görə

2^{2026}

-nı birbaşa hesablamaq mümkün deyil; əvəzinə

2

-nin qüvvətlərinin

13

modulunda dövrünü tapmalıyıq, yəni

2^k\equiv 1\ (\mathrm{mod}\ 13)

olan ən kiçik

k

-nı axtarırıq. Kiçik qüvvətləri ardıcıl yazaq:

2^1\equiv 2

2^2\equiv 4

2^3\equiv 8

2^4\equiv 16\equiv 3

2^5\equiv 6

2^6\equiv 12\ (\mathrm{mod}\ 13)

. Burada dayanıb

12

-ni mənfi qalıq (nümayəndə) ilə yazmaq işi bir addımda bitirir:

2^6\equiv -1\ (\mathrm{mod}\ 13)

, çünki

12=13-1

. Hər iki tərəfi kvadrata yüksəltsək,

2^{12}\equiv (-1)^2=1\ (\mathrm{mod}\ 13)

alınır; deməli, qüvvətlər

12

addımdan bir təkrarlanır və

2^n\equiv 2^{\,n\bmod 12}\ (\mathrm{mod}\ 13)

. (Ara qiymətlərdən heç biri

1

olmadığı üçün

12

həqiqətən ən kiçik dövrdür.) İndi üstü dövrə görə qalıqlı bölürük:

2026=12\cdot 168+10

, yəni

2026\equiv 10\ (\mathrm{mod}\ 12)

. Onda

2^{2026}\equiv 2^{10}=2^6\cdot 2^4\equiv (-1)\cdot 3=-3 \equiv 13-3=10\ (\mathrm{mod}\ 13)

. Cavab:

10

Məsələ 3.

n

qeyri-mənfi tam ədəd olduqda

5^{6n+10}+3^{6n+8}

ədədinin

7

-yə bölünməsindən neçə fərqli qalıq alına bilər?

Həll. Sual «qalıq neçədir» deyil, «neçə fərqli qalıq alına bilər» şəklindədir, ona görə qalığın

n

-dən asılı olub-olmadığını yoxlamalıyıq. Üstlərdəki

6n

payı göstərir ki,

7

modulunda

6

uzunluqlu dövr axtarmaq təbiidir.

5

-in qüvvətləri:

5^1\equiv 5

5^2\equiv 25\equiv 4

5^3\equiv 20\equiv 6

5^4\equiv 30\equiv 2

5^5\equiv 10\equiv 3

5^6\equiv 15\equiv 1\ (\mathrm{mod}\ 7)

; deməli, dövr

6

-dır.

3

-ün qüvvətləri:

3^1\equiv 3

3^2\equiv 2

3^3\equiv 6

3^4\equiv 4

3^5\equiv 5

3^6\equiv 1\ (\mathrm{mod}\ 7)

; burada da dövr

6

-dır. Hər iki əsas üçün

6

-cı qüvvət

1

olduğundan

5^{6n+10}=(5^6)^n\cdot 5^{10}\equiv 1^n\cdot 5^{10}

və

5^{10}\equiv 5^{10\bmod 6}=5^4\equiv 2

, eyni ilə

3^{6n+8}\equiv 3^{8\bmod 6}=3^2\equiv 2\ (\mathrm{mod}\ 7)

. Beləliklə, ifadə

n

-dən tamamilə asılı olmayaraq

2+2=4\ (\mathrm{mod}\ 7)

olur, yəni cəmi bir qalıq alınır. Cavab:

1

(yeganə qalıq

4

-dür)

Məsələ 4.

n

natural ədəd olduqda

101^{\,n!}

ədədinin

7

-yə bölünməsindən neçə fərqli qalıq alına bilər?

Həll. Əvvəlcə əsası kiçildək:

101=14\cdot 7+3

, yəni

101\equiv 3\ (\mathrm{mod}\ 7)

, deməli

101^{n!}\equiv 3^{n!}\ (\mathrm{mod}\ 7)

3

-ün

7

modulunda qüvvətləri

3,2,6,4,5,1

olub

3^6\equiv 1

verir, yəni dövrün uzunluğu

6

-dır və

3^{m}\equiv 3^{\,m\bmod 6}\ (\mathrm{mod}\ 7)

. Onda hər şey

n!

-in

6

-ya bölünməsindən alınan qalığa gəlib çıxır. Burada həlledici müşahidə budur:

n\ge 3

olduqda

n!

hasilində həm

2

, həm də

3

vuruğu iştirak edir, yəni

6\mid n!

və

n!\equiv 0\ (\mathrm{mod}\ 6)

. Deməli,

n\ge 3

üçün

3^{n!}\equiv 3^{0}=1\ (\mathrm{mod}\ 7)

— sonsuz sayda

n

eyni qalığı verir. Yerdə yalnız kiçik hallar qalır:

n=1

üçün

3^{1!}=3^1\equiv 3

n=2

üçün

3^{2!}=3^2\equiv 2\ (\mathrm{mod}\ 7)

. Beləliklə, mümkün qalıqlar dəsti

\{1,2,3\}

-dür. Cavab:

3

Məsələ 5.

7^{\,7^{77}}

ədədinin son rəqəmini tapın.

Həll. Bu, «qüvvət qülləsi»dir: üst özü də qüvvətdir, ona görə iki mərhələdə işləyirik — əvvəlcə xarici əsasın dövrünü tapırıq, sonra üstü həmin dövrə görə azaldırıq. Birinci mərhələ:

7

-nin son rəqəmləri

7^1\equiv 7

7^2\equiv 49\equiv 9

7^3\equiv 63\equiv 3

7^4\equiv 21\equiv 1\ (\mathrm{mod}\ 10)

, yəni dövr

k=4

-dür və

7^{m}\equiv 7^{\,m\bmod 4}\ (\mathrm{mod}\ 10)

. İkinci mərhələ: deməli, bizə

m=7^{77}

ədədinin

4

-ə bölünməsindən alınan qalıq lazımdır — diqqət edin, indi modul

10

deyil,

4

-dür, çünki üst məhz dövrün uzunluğuna görə azaldılır. Burada mənfi qalıq işi bir sətrə salır:

7\equiv -1\ (\mathrm{mod}\ 4)

, ona görə

7^{77}\equiv (-1)^{77}=-1\equiv 3\ (\mathrm{mod}\ 4)

(

77

tək ədəd olduğu üçün). Deməli,

m\equiv 3\ (\mathrm{mod}\ 4)

və

7^{\,7^{77}}\equiv 7^{3}\equiv 3\ (\mathrm{mod}\ 10)

. Cavab:

3

Məsələ 6.

S=1+(1+2)+(1+2+2^2)+\dots+(1+2+2^2+\dots+2^{100})

cəminin son rəqəmini tapın.

Həll. Əvvəlcə cəmi daha yığcam şəkildə yazaq, çünki

101

mötərizəni ayrı-ayrılıqda

\bmod\ 10

hesablamaq uzun olardı. Həndəsi silsilənin cəmi düsturuna görə

1+2+\dots+2^{k}=2^{k+1}-1

, ona görə

S=\sum_{k=0}^{100}\bigl(2^{k+1}-1\bigr) =\bigl(2^1+2^2+\dots+2^{101}\bigr)-101 .

Mötərizədəki cəm yenə həndəsi silsilədir:

2^1+\dots+2^{101}=2^{102}-2

, deməli

S=2^{102}-103

. İndi yalnız

2^{102}

-nin son rəqəmi lazımdır:

2

-nin son rəqəmləri

2,4,8,6

dövrü ilə gedir (dövr

4

), yəni

n\ge 1

üçün

2^n

-in son rəqəmi

n

-in

4

-ə görə qalığı ilə təyin olunur.

102=4\cdot 25+2

olduğundan

2^{102}

-nin son rəqəmi

2^2

-ninki, yəni

4

-dür:

2^{102}\equiv 4\ (\mathrm{mod}\ 10)

. Onda

S\equiv 4-103\equiv 4-3=1\ (\mathrm{mod}\ 10)

(çünki

103\equiv 3\ (\mathrm{mod}\ 10)

). Cavab:

1

Məsələ 7. UİMO ·

1\le n\le 100

şərtini ödəyən neçə

n

tam ədədi üçün

5^n+3^n+1

ədədi

7

-yə bölünür?

Həll. Şərt

7\mid 5^n+3^n+1

, yəni

5^n+3^n+1\equiv 0\ (\mathrm{mod}\ 7)

deməkdir, ona görə hər iki qüvvəti

7

modulunda dövrə salırıq.

5

-in qüvvətləri

\bmod\ 7

5,4,6,2,3,1

və sonra təkrar (dövr

6

);

3

-ün qüvvətləri

\bmod\ 7

3,2,6,4,5,1

və sonra təkrar (yenə dövr

6

). Hər ikisinin dövrü

6

olduğundan bütün

5^n+3^n+1

ifadəsi də

n

-ə görə

6

addımdan bir təkrarlanır; deməli, yalnız

n=1,2,\dots,6

hallarını yoxlamaq kifayətdir. Hesablayaq:

n=1

5+3+1=9\equiv 2

;

n=2

4+2+1=7\equiv 0

;

n=3

6+6+1=13\equiv 6

;

n=4

2+4+1=7\equiv 0

;

n=5

3+5+1=9\equiv 2

;

n=6

1+1+1=3

(hamısı

\bmod\ 7

). Deməli, bölünmə yalnız

n\equiv 2

və

n\equiv 4\ (\mathrm{mod}\ 6)

olduqda baş verir. İndi sayaq:

1\le n\le 100

aralığında

n\equiv 2\ (\mathrm{mod}\ 6)

olanlar

2,8,\dots,98

— bu

\frac{98-2}{6}+1=17

ədəddir;

n\equiv 4\ (\mathrm{mod}\ 6)

olanlar

4,10,\dots,100

— bu da

\frac{100-4}{6}+1=17

ədəddir. İki sinif kəsişmədiyi üçün cəmi

17+17=34

ədəd alınır. Cavab:

34

Məsələ 8.

10^{200}

ədədi

19

əsaslı say sistemində yazılsa, son rəqəmi nə olar?

Həll.

19

əsaslı yazılışda son rəqəm sağdan birinci mərtəbədir və qalıqlı bölmə haqqında teoremə görə o, məhz ədədin

19

-a bölünməsindən alınan qalıqdır (bu qalıq

0

ilə

18

arasında olduğundan həqiqətən bir rəqəmdir). Deməli,

10^{200}\bmod 19

hesablamalıyıq. Üst böyük olduğu üçün

10

-un qüvvətlərində dövr axtarırıq, ancaq bütün siyahını yazmaq əvəzinə ardıcıl kvadrata yüksəltmə ilə irəliləyək:

10^2=100=5\cdot 19+5\equiv 5

, ona görə

10^3\equiv 10\cdot 5=50=2\cdot 19+12\equiv 12\ (\mathrm{mod}\ 19)

. Buradan

10^6\equiv 12^2=144=7\cdot 19+11\equiv 11

və

10^9\equiv 10^6\cdot 10^3\equiv 11\cdot 12=132=6\cdot 19+18 \equiv 18\equiv -1\ (\mathrm{mod}\ 19)

. Mənfi qalıq yenə həlledicidir:

10^9\equiv -1

olduğundan kvadrata yüksəldib

10^{18}\equiv 1\ (\mathrm{mod}\ 19)

alırıq, yəni qüvvətlər

18

addımdan bir təkrarlanır. Onda üstü

18

-ə görə azaldırıq:

200=18\cdot 11+2

, yəni

200\equiv 2\ (\mathrm{mod}\ 18)

, deməli

10^{200}\equiv 10^{2}\equiv 5\ (\mathrm{mod}\ 19)

. Beləliklə,

19

əsaslı yazılışda son rəqəm

5

-dir. Cavab:

5

2Tam kvadratların qalıqlarıBu bölmə olimpiada ədədlər nəzəriyyəsinin ən çox istifadə olunan mövzularından biridir — desək ki, olimpiada məsələlərinin böyük bir hissəsində bu bölmədəki hər hansı bir fakt mütləq tətbiq olunur, heç də mübaliğə etmiş olmarıq. İdeya təəccüblü dərəcədə sadədir. Kiçik bir modul götürək, məsələn

4

. Tam kvadratların bu modula görə qalıqlarına baxsaq, görərik ki, onlar yalnız

0

və

1

ola bilir —

2

və

3

qalıqları tam kvadratlar üçün mümkün deyil. Deməli, əlimizdə güclü bir alət var: əgər hansısa ifadənin

4

moduluna görə qalığı

3

-dürsə, o ifadə heç bir halda tam kvadrat ola bilməz — nə qədər böyük olursa-olsun, nə qədər axtarsaq da. Bir sətirlik hesablama sonsuz sayda imkanı birdəfəlik kəsir. Bu, Dərs 5-də tanış olduğumuz «mümkünsüzlük» (əksini fərz etmə) mühakiməsinin ən məhsuldar formasıdır. İndi onun üçün lazım olan bütün cədvəlləri sistemli şəkildə quracağıq.

Teorem 2.1 (Kvadratların mod 4 və mod 8 qalıqları). Tutaq ki,

n

tam ədəddir.

1. Əgər $n$ cütdürsə, $n^2 \equiv 0 \pmod 4$ .
2. Əgər $n$ təkdirsə, $n^2 \equiv 1 \pmod 8$ .

İsbat. Birinci hal.

n

cütdürsə,

n = 2k

şəklində yazılır. Onda

n^2 = (2k)^2 = 4k^2 ,

yəni

n^2

ədədi

4

-ə bölünür:

n^2 \equiv 0 \pmod 4

. İkinci hal.

n

təkdirsə,

n = 2k+1

şəklində yazılır. Onda

n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1 .

İndi diqqətlə baxaq:

k(k+1)

— iki ardıcıl tam ədədin hasilidir. Ardıcıl iki ədəddən biri mütləq cütdür (Dərs 2-də

2

-yə görə hallara ayırma), deməli onların hasili cütdür:

k(k+1) = 2t

şəklindədir. Onda

n^2 = 4 \cdot 2t + 1 = 8t + 1 ,

yəni

8 \mid n^2 - 1

, başqa sözlə

n^2 \equiv 1 \pmod 8

Nəticə 2.2. Tam kvadratın

8

moduluna görə qalığı yalnız

0

1

və ya

4

ola bilər;

2

3

5

6

7

qalıqları mümkün deyil.

İsbat.

n

-i

4

-ə görə hallara ayıraq (yəni

n

-in

4

moduluna görə qalığına baxaq).

• $n = 4t$ : onda $n^2 = 16t^2 \equiv 0 \pmod 8$ , çünki $8 \mid 16t^2$ .
• $n = 4t+2$ : onda $n^2 = 16t^2 + 16t + 4 \equiv 4 \pmod 8$ , çünki $8 \mid 16t^2 + 16t$ .
• $n$ tək (yəni $n = 4t+1$ və ya $n = 4t+3$ ): yuxarıdakı teoremə görə $n^2 \equiv 1 \pmod 8$ .

Deməli, mümkün qalıqlar yalnız

\{0, 1, 4\}

-dür. Buradan həmçinin

4

moduluna görə nəticə də çıxır:

0

və

4

qalıqları

4

-ə görə

0

1

qalığı isə

1

verir, yəni tam kvadratın

4

moduluna görə qalığı yalnız

0

və ya

1

-dir.

Teorem 2.3 (Kvadratların mod 3, 5, 9, 16 qalıqları). Tam kvadratın qalığı:

• $3$ moduluna görə yalnız $\{0, 1\}$ ;
• $5$ moduluna görə yalnız $\{0, 1, 4\}$ ;
• $9$ moduluna görə yalnız $\{0, 1, 4, 7\}$ ;
• $16$ moduluna görə yalnız $\{0, 1, 4, 9\}$

çoxluğundan ola bilər.

İsbat. İsbat üsulu bütün hallarda eynidir və Dərs 5-in çoxhədli nəticəsinə söykənir: əgər

n \equiv r \pmod m

olarsa, onda

n^2 \equiv r^2 \pmod m

. Deməli,

n

-in bütün mümkün qalıqlarını — yəni

r = 0, 1, \dots, m-1

— yoxlamaq kifayətdir; başqa heç bir

n

yeni qalıq verə bilməz. Bu, sonsuz sayda ədədi yoxlamaq məsələsini sonlu, hətta çox kiçik bir yoxlamaya çevirir. Üstəlik işi yarıya endirmək olar. Qeyd edək ki,

r

və

-r

eyni kvadratı verir:

(-r)^2 = r^2

m

moduluna görə

-r

ilə

m - r

eyni şeydir, deməli

r

və

m-r

qalıqları eyni kvadrat qalığını verir. Ona görə

r = 0, 1, \dots, \lfloor m/2 \rfloor

-yə qədər yoxlamaq bəs edir — qalanları onlara nəzərən simmetrikdir. Modul 3.

r \in \{0, 1, -1\}

(yəni

0,1,2

0^2 = 0,\qquad 1^2 = 1,\qquad (-1)^2 = 1 .

Mümkün qalıqlar:

\{0, 1\}

. Yəni

2

qalığı tam kvadratlar üçün mümkün deyil. Modul 5.

r \in \{0, 1, -1, 2, -2\}

(yəni

0,1,4,2,3

0^2 = 0,\quad (\pm 1)^2 = 1,\quad (\pm 2)^2 = 4 .

Mümkün qalıqlar:

\{0, 1, 4\}

2

və

3

mümkün deyil. Modul 9.

r \in \{0, \pm 1, \pm 2, \pm 3, \pm 4\}

0^2 = 0,\quad (\pm 1)^2 = 1,\quad (\pm 2)^2 = 4,

(\pm 3)^2 = 9 \equiv 0,\quad (\pm 4)^2 = 16 \equiv 7 \pmod 9 .

Mümkün qalıqlar:

\{0, 1, 4, 7\}

. Modul 16.

r \in \{0, \pm 1, \dots, \pm 7, 8\}

0^2 = 0,\ (\pm 1)^2 = 1,\ (\pm 2)^2 = 4,\ (\pm 3)^2 = 9,

(\pm 4)^2 = 16 \equiv 0,\quad (\pm 5)^2 = 25 \equiv 9,\quad (\pm 6)^2 = 36 \equiv 4,

(\pm 7)^2 = 49 \equiv 1,\quad 8^2 = 64 \equiv 0 \pmod{16}.

Mümkün qalıqlar:

\{0, 1, 4, 9\}

. Bütün cədvəllər hesablama ilə yoxlanmışdır.

Nümunə 2.1 (Ümumi cədvəl). Yuxarıdakı bütün nəticələri bir yerə toplayaq:

\begin{array}{c|l} \text{modul } m & \text{tam kvadratın mümkün qalıqları} \\ \hline 3 & 0,\ 1 \\ 4 & 0,\ 1 \\ 5 & 0,\ 1,\ 4 \\ 8 & 0,\ 1,\ 4 \\ 9 & 0,\ 1,\ 4,\ 7 \\ 16 & 0,\ 1,\ 4,\ 9 \end{array}

Şagirdlərə məsləhət: bu cədvəli əzbərləmək lazım deyil. Onu

30

saniyəyə yenidən qurmaq olar: sadəcə

0^2, 1^2, 2^2, \dots

qiymətlərini götürüb modula görə kiçildin və

r

ilə

m-r

-in eyni nəticə verdiyini xatırlayıb yarıda dayanın. Məsələn,

9

üçün:

0, 1, 4, 9 \to 0, 16 \to 7

— bitdi, cavab

\{0,1,4,7\}

Nəticə 2.4 (Son rəqəm). Tam kvadratın son rəqəmi yalnız

0,\ 1,\ 4,\ 5,\ 6,\ 9

ola bilər. Deməli, son rəqəmi

2

3

7

və ya

8

olan heç bir ədəd tam kvadrat deyil.

İsbat. Son rəqəm —

10

moduluna görə qalıqdır.

n \equiv r \pmod{10}

olduqda

n^2 \equiv r^2 \pmod{10}

, deməli

r = 0,1,\dots,9

üçün yoxlamaq kifayətdir:

\begin{array}{c|cccccccccc} r & 0&1&2&3&4&5&6&7&8&9 \\ \hline r^2 \bmod 10 & 0&1&4&9&6&5&6&9&4&1 \end{array}

Alınan qiymətlər çoxluğu:

\{0,1,4,5,6,9\}

. Burada

2, 3, 7, 8

yoxdur. Simmetriyaya diqqət edin — cədvəl mərkəzə nəzərən simmetrikdir, çünki

r

və

10-r

eyni son rəqəmi verir.

Nəticə 2.5 (İki ədədin kvadratları cəmi).

x^2 + y^2

ifadəsi

4

moduluna görə yalnız

0

1

və ya

2

qalığını verə bilər. Deməli,

4k+3

şəklində olan heç bir ədəd iki tam kvadratın cəmi kimi yazıla bilməz.

İsbat. Cədvəldən bilirik ki,

x^2 \equiv 0

və ya

1 \pmod 4

; eyni şey

y^2

üçün də doğrudur. Bütün mümkün birləşmələri yazaq:

\begin{array}{c|cc} x^2 + y^2 & y^2 \equiv 0 & y^2 \equiv 1 \\ \hline x^2 \equiv 0 & 0 & 1 \\ x^2 \equiv 1 & 1 & 2 \end{array}

Deməli,

x^2 + y^2 \pmod 4

yalnız

0

1

2

qiymətlərini alır.

3

qalığı heç bir halda alınmır.

Nümunə 2.2.

2027

ədədi iki tam kvadratın cəmi kimi yazıla bilərmi?

2027 = 4 \cdot 506 + 3

, yəni

2027 \equiv 3 \pmod 4

. Yuxarıdakı nəticəyə görə

x^2 + y^2

heç vaxt

4

moduluna görə

3

qalığını vermir. Deməli, cavab: xeyr,

2027

iki tam kvadratın cəmi deyil. Diqqət yetirin ki, biz heç bir axtarış aparmadıq —

x

və

y

üçün variantları sınamadıq. Bir sətirlik modul hesabı bütün sonsuz imkanları birdəfəlik kəsdi. (Kompüterlə birbaşa axtarış da eyni nəticəni verir: uyğun

x, y

cütü yoxdur.)

Nəticə 2.6 (3 və 7 modulları).

1. Əgər $3 \mid x^2 + y^2$ olarsa, onda həm $3 \mid x$ , həm də $3 \mid y$ .
2. Əgər $7 \mid x^2 + y^2$ olarsa, onda həm $7 \mid x$ , həm də $7 \mid y$ .

İsbat. Birinci hissə. Kvadratlar

3

moduluna görə yalnız

0

və ya

1

qalığını verir.

x^2 + y^2 \equiv 0 \pmod 3

olması üçün mümkün birləşmələrə baxaq:

0 + 0 = 0,\qquad 0 + 1 = 1,\qquad 1 + 1 = 2 .

Yalnız

0 + 0

birləşməsi

0

verir. Deməli

x^2 \equiv 0

və

y^2 \equiv 0 \pmod 3

olmalıdır.

3

sadə ədəd olduğuna görə (Dərs 4-dəki Evklid lemması)

3 \mid x \cdot x

münasibətindən

3 \mid x

çıxır; eyni ilə

3 \mid y

. İkinci hissə. Əvvəlcə

7

moduluna görə kvadratların qalıqlarını tapaq:

0^2 = 0,\ (\pm 1)^2 = 1,\ (\pm 2)^2 = 4,\ (\pm 3)^2 = 9 \equiv 2 \pmod 7 .

Yəni mümkün qalıqlar

\{0, 1, 2, 4\}

-dür. İndi bu çoxluqdan iki elementin cəmi

7

-yə bölünə bilərmi? Mümkün cəmlər:

0,\ 1,\ 2,\ 4,\ 1{+}1{=}2,\ 1{+}2{=}3,\ 1{+}4{=}5,

2{+}2{=}4,\ 2{+}4{=}6,\ 4{+}4{=}8 \equiv 1 .

Yeganə sıfır verən birləşmə

0 + 0

-dır. Deməli

x^2 \equiv y^2 \equiv 0 \pmod 7

, buradan da

7

sadə ədəd olduğu üçün

7 \mid x

və

7 \mid y

. Hər iki iddia hesablama ilə tam yoxlanmışdır.

Qeyd. Bu xassənin üç kvadrata köçürülməsi doğru deyil! Yəni «

7 \mid x^2 + y^2 + z^2

olarsa, hər üçü

7

-yə bölünür» iddiası səhvdir. Əks misal:

1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14 = 7 \cdot 2 ,

burada

x = 1

y = 2

z = 3

və heç biri

7

-yə bölünmür. Səbəb aydındır:

7

moduluna görə kvadratların qalıqları

\{0,1,2,4\}

çoxluğudur və üç elementin cəmi asanlıqla

7

-yə bölünə bilər (

1 + 2 + 4 = 7

). Ümumiyyətlə, belə iddiaları həmişə kiçik nümunələrlə yoxlayın — «iki üçün doğrudursa, üç üçün də doğrudur» tipli ümumiləşdirmələr ədədlər nəzəriyyəsində çox vaxt yanlış çıxır.

Modul necə seçilməlidir?. Modul seçimi bu mövzuda əsas bacarıqdır. Praktik siyahı belədir:

1. Əvvəlcə $4$ . Ən sadə və ən tez-tez tətbiq olunan moduldur: kvadratlar üçün cəmi iki qalıq ( $0, 1$ ) buraxır, yəni imkanların yarısını dərhal kəsir. Kvadratlarla bağlı hər məsələdə birinci sınanacaq şeydir.
2. Sonra $8$ . $4$ nəticə vermədikdə $8$ -ə keçin: tək kvadratların hamısı $1$ qalığını verir, bu isə çox güclü məhdudiyyətdir. Xüsusən ifadədə $2$ -nin qüvvəti və ya tək ədədlərin kvadratı varsa, $8$ demək olar ki, həmişə işləyir.
3. Sonra $3$ . Kvadratlar üçün $\{0,1\}$ verir. İfadədə $3$ -ə bölünmə ilə bağlı sabitlər (məsələn, $3$ , $6$ , $9$ , $12$ ) varsa, ilk namizəddir.
4. Sonra $5$ , $9$ , $16$ . Bunlar daha həssas alətlərdir. $5$ — ifadədə $5$ və ya $10$ -un qüvvətləri varsa; $9$ — rəqəmlər cəmi ilə bağlı məsələlərdə (Dərs 5-dən $n \equiv T(n) \pmod 9$ nəticəsi); $16$ — $8$ kifayət etmədikdə növbəti addım kimi.
5. Rəqəmlərlə bağlı məsələlərdə $10$ və $100$ . Son rəqəm soruşulursa $10$ , son iki rəqəm soruşulursa $100$ modulu ilə işləyin.
6. Ardıcıl ədədlər varsa $4$ (bəzən $3$ ). $n(n+1)$ , $n(n+1)(n+2)$ tipli hasillərin cütlüyü və $3$ -ə bölünməsi bu modullarda dərhal görünür.

«Modul necə seçilir?» sualına ümumi cavab: ifadəyə baxıb iki şeyi soruşun. Birincisi — ifadədəki sabitlərin hansı bölənləri var? Məsələn,

x^2 + y^2 = 2027

tənliyində

2027

-nin

4

-ə görə qalığı (

3

) hər şeyi həll edir;

x^2 = 3y + 8

tipli ifadədə

3

modulu təbii seçimdir. İkincisi — ifadədə hansı qüvvətlər var və onların dövr uzunluqları nədir? Əgər

2^n

varsa,

2

-nin dövrü qısa olan modulu seçin (

7

üçün dövr

3

5

üçün

4

); belə modulda

2^n

cəmi bir neçə qiymət alır və hallara ayırmaq asanlaşır. Qısaca: modul elə seçilir ki, ifadənin tərəfləri mümkün qədər az qiymət alsın — onda ziddiyyət tapmaq şansı ən yüksək olur.

Qeyd. Bu bölmənin ən vacib məntiqi xəbərdarlığı budur — Dərs 5-də də oxşar xəbərdarlıq vermişdik, burada təkrarlayırıq, çünki səhv çox yayğındır. Qalıq cədvəli yalnız bir istiqamətdə işləyir:

• Əgər ədədin qalığı cədvəldə yoxdursa — o, mütləq tam kvadrat deyil. Bu, tam etibarlı nəticədir.
• Əgər ədədin qalığı cədvəldə varsa — bu, heç nə sübut etmir. Ədəd tam kvadrat ola da bilər, olmaya da.

Konkret misal:

21 = 4 \cdot 5 + 1

, yəni

21 \equiv 1 \pmod 4

— bu, tam kvadratlar üçün icazəli qalıqdır. Amma

21

tam kvadrat deyil (

4^2 = 16 < 21 < 25 = 5^2

). İndi eyni ədədə

8

moduluna görə baxaq:

21 = 8 \cdot 2 + 5

, yəni

8

modulunda

21

-in qalığı

5

-dir və bu, icazəli qalıqlar

\{0,1,4\}

siyahısında yoxdur — deməli

8

modulu bu halda işləyir və

21

-in tam kvadrat olmadığını sübut edir. Bu, eyni zamanda göstərir ki, bir modul nəticə vermədikdə başqasını sınamağa dəyər. Amma prinsip dəyişmir: heç bir modul cədvəli « tam kvadratdır » nəticəsini verə bilməz. Belə iddianı sübut etmək üçün ya konkret

n

tapıb onun nəyinsə kvadratı olduğunu (

n^2

) göstərmək, ya da Dərs 3-dəki kanonik ayrılış meyarından (bütün sadə vuruqların qüvvətlərinin cüt olmasından) istifadə etmək lazımdır.

Məsələ 9. Bütün rəqəmləri

1

olan

2026

rəqəmli

\underbrace{11\ldots 1}_{2026}

ədədi tam kvadratdırmı?

Həll. Belə nəhəng ədədin kökünü hesablamaq mümkün deyil, ona görə tam kvadratların kiçik modullardakı qalıqlarından istifadə edirik — əgər ədəd hansısa modulda kvadratın ala bilmədiyi qalığı verirsə, o, tam kvadrat ola bilməz. Ən sadə süzgəc

\bmod\ 4

-dür: hər

x

tam ədədi ya cütdür (

x=2t

x^2=4t^2\equiv 0

), ya da təkdir (

x=2t+1

x^2=4t(t+1)+1\equiv 1

), yəni

x^2\equiv 0

və ya

1\ (\mathrm{mod}\ 4)

. İndi verilmiş ədədin

4

-ə görə qalığını tapaq:

100

ədədi

4

-ə bölündüyü üçün istənilən ədəd

\bmod\ 4

-də öz son iki rəqəmi ilə eyni qalığı verir. Bizim ədədin son iki rəqəmi

11

-dir,

11=2\cdot 4+3

, deməli

\underbrace{11\ldots 1}_{2026}\equiv 3\ (\mathrm{mod}\ 4)

. Lakin

3

tam kvadratın

\bmod\ 4

ala biləcəyi qalıqlar

\{0,1\}

çoxluğuna daxil deyil. Deməli, bu ədəd tam kvadrat ola bilməz. (Qeyd edək ki, rəqəmlərin sayının

2026

olması heç bir rol oynamadı: ən azı iki vahiddən ibarət heç bir belə ədəd tam kvadrat deyil.) Cavab: Xeyr, tam kvadrat deyil

Məsələ 10. Kanada MO 1969 ·

x^2+y^2=8z+6

tənliyini ödəyən neçə

(x,y,z)

tam ədəd üçlüyü vardır?

Həll. Sağ tərəf

z

-dən asılı olsa da, onun

8

-ə görə qalığı sabitdir:

8z+6\equiv 6\ (\mathrm{mod}\ 8)

. Deməli, sual belə çevrilir: iki tam kvadratın cəmi

8

modulunda

6

qalığını verə bilərmi? Əvvəlcə daha zəif süzgəci —

\bmod\ 4

-ü — sınayaq: kvadratlar

\bmod\ 4

-də yalnız

0

və ya

1

olduğundan

x^2+y^2\in\{0,1,2\}\ (\mathrm{mod}\ 4)

, sağ tərəf isə

8z+6\equiv 2\ (\mathrm{mod}\ 4)

— bu, mümkün dəyərlərdəndir, yəni

\bmod\ 4

ziddiyyət vermir və daha güclü modula keçmək lazımdır. Məhz buna görə

\bmod\ 8

götürürük: cüt

x=2t

üçün

x^2=4t^2\equiv 0

və ya

4

(

t

-nin cütlüyündən asılı olaraq), tək

x

üçün isə

x^2\equiv 1\ (\mathrm{mod}\ 8)

; yəni

x^2\in\{0,1,4\}\ (\mathrm{mod}\ 8)

. Bu üç dəyərdən iki ədəd seçib cəmləsək, alına bilən qalıqlar

0+0=0

0+1=1

0+4=4

1+1=2

1+4=5

4+4=8\equiv 0

, yəni

\{0,1,2,4,5\}

çoxluğudur.

6

bu siyahıda yoxdur, deməli tənliyin heç bir tam ədəd həlli yoxdur. Cavab:

0

Məsələ 11.

m

və

n

tək ədədlər olduqda

m^2+n^2

ədədinin

8

-ə bölünməsindən neçə fərqli qalıq alına bilər?

Həll. Sual mümkün qalıqların sayını soruşduğu üçün tək ədədin kvadratının

\bmod\ 8

davranışını dəqiq təsvir etməliyik.

m

tək olsun, yəni

m=2t+1

(

t

tam ədəd). Onda

m^2=4t^2+4t+1=4t(t+1)+1

. Burada

t

və

t+1

ardıcıl tam ədədlərdir, deməli, onlardan biri mütləq cütdür və

t(t+1)

hasili

2

-yə bölünür. Onda

4t(t+1)

ifadəsi

8

-ə bölünür və nəticədə

m^2\equiv 1\ (\mathrm{mod}\ 8)

— bu, heç bir istisnası olmayan qaydadır: « hər tək ədədin kvadratı

8

moduluna görə

1

-ə konqruentdir». Eyni səbəbdən

n^2\equiv 1\ (\mathrm{mod}\ 8)

. Konqruensiyaları toplayaq:

m^2+n^2\equiv 1+1=2\ (\mathrm{mod}\ 8)

. Bu,

m

və

n

-in konkret qiymətlərindən heç asılı deyil, yəni qalıq həmişə

2

-dir və mümkün fərqli qalıqların sayı yalnız birdir (bu qalıq həqiqətən alınır:

m=n=1

üçün

1+1=2

). Cavab:

1

(yeganə qalıq

2

-dir)

Məsələ 12.

1!+2!+3!+\dots+n!

cəmi tam kvadrat olan bütün

n

natural ədədlərini tapın.

Həll. Kiçik hallardan başlayaq, çünki faktorialların cəmi çox sürətlə böyüyür:

n=1

1=1^2

— tam kvadratdır;

n=2

1+2=3

— deyil;

n=3

1+2+6=9=3^2

— tam kvadratdır;

n=4

1+2+6+24=33

— deyil. İndi əsas ideya:

n\ge 5

üçün cəmi bütünlüklə hesablamaq əvəzinə yalnız son rəqəminə baxaq, çünki tam kvadratın son rəqəmi mütləq

\{0,1,4,5,6,9\}

çoxluğundadır (bu,

x\equiv 0,1,\dots,9

hallarını bir-bir kvadratlaşdırmaqla alınır). Həlledici müşahidə budur:

k\ge 5

olduqda

k!

hasilində həm

2

, həm də

5

vuruğu var, deməli

10\mid k!

və

k!\equiv 0\ (\mathrm{mod}\ 10)

, yəni belə faktorialların son rəqəmi

0

-dır. Ona görə

n\ge 5

üçün

1!+2!+\dots+n!\equiv 1!+2!+3!+4!=33\equiv 3\ (\mathrm{mod}\ 10),

yəni cəmin son rəqəmi dəyişməz olaraq

3

qalır.

3

isə tam kvadratın son rəqəmi ola bilməz, deməli,

n\ge 5

üçün heç bir həll yoxdur. Beləliklə, yalnız yuxarıda tapdığımız iki hal qalır. Cavab:

n=1

və

n=3

Məsələ 13.

n

natural ədədi üçün

2n+1

və

3n+1

ədədlərinin hər ikisi tam kvadratdırsa,

40\mid n

olduğunu isbat edin.

Həll.

40=8\cdot 5

və

(8,5)=1

olduğundan planımız aydındır: ayrıca

8\mid n

, ayrıca

5\mid n

göstərəcəyik, sonra qarşılıqlı sadə bölənlər haqqındakı qaydaya (əgər

(a,b)=1

a\mid n

və

b\mid n

isə

ab\mid n

) əsasən

40\mid n

alacağıq.

2n+1=a^2

3n+1=b^2

olsun. Birincisi,

2n+1

təkdir, deməli

a

da təkdir və tək ədədin kvadratı üçün

a^2\equiv 1\ (\mathrm{mod}\ 8)

qaydasına görə

2n+1\equiv 1

, yəni

2n\equiv 0\ (\mathrm{mod}\ 8)

, buradan

4\mid n

— xüsusən

n

cütdür. İkincisi,

n

cüt olduğu üçün

3n+1

də təkdir, onda eyni qayda ilə

b^2\equiv 1\ (\mathrm{mod}\ 8)

, yəni

3n\equiv 0\ (\mathrm{mod}\ 8)

;

(3,8)=1

olduğundan ixtisar qaydasına görə

n\equiv 0\ (\mathrm{mod}\ 8)

, yəni

8\mid n

. İndi

\bmod\ 5

-ə keçək: kvadratların

5

modulunda mümkün qalıqları

\{0,1,4\}

-dür. Bunları birbaşa deyil, cəm vasitəsilə istifadə edək:

a^2+b^2=(2n+1)+(3n+1)=5n+2\equiv 2\ (\mathrm{mod}\ 5)

\{0,1,4\}

çoxluğundan götürülmüş iki ədədin cəmlərini yoxlayaq:

0+0=0

0+1=1

0+4=4

1+1=2

1+4=5\equiv 0

4+4=8\equiv 3

—

2

qalığını verən yeganə variant

1+1

-dir. Deməli, məcburi olaraq

a^2\equiv 1\ (\mathrm{mod}\ 5)

, yəni

2n+1\equiv 1

2n\equiv 0\ (\mathrm{mod}\ 5)

və

(2,5)=1

olduğundan

5\mid n

8\mid n

5\mid n

və

(8,5)=1

olduğundan

40\mid n

. (Belə

n

-lər həqiqətən var:

n=40

üçün

81=9^2

və

121=11^2

.) Cavab: İsbat olundu; ən kiçik nümunə

n=40

Məsələ 14. Avstriya-Polşa MO 2001 ·

10n-1

13n-1

və

85n-1

ədədlərinin hamısı tam kvadrat olacaq şəkildə neçə

n

natural ədədi vardır?

Həll. Üç şərtin hamısını eyni anda ödəmək çətindir, ona görə addım-addım

n

-i sıxışdıracağıq; işlədəcəyimiz yeganə alət kvadratların

\bmod\ 4

və

\bmod\ 8

qalıqlarıdır. Birinci addım (

\bmod\ 4

10\equiv 2\ (\mathrm{mod}\ 4)

olduğundan

10n-1\equiv 2n-1\ (\mathrm{mod}\ 4)

, bu isə həmişə təkdir, yəni

1

və ya

3

qalığını verir; kvadrat üçün

3

qadağandır, deməli,

2n-1\equiv 1

, yəni

2n\equiv 2\ (\mathrm{mod}\ 4)

və

n

təkdir. İkinci addım (

\bmod\ 8

n

tək olduğundan

10n-1

də təkdir, tək ədədin kvadratı isə

\bmod\ 8

-də

1

-dir, yəni

10n\equiv 2\ (\mathrm{mod}\ 8)

;

10\equiv 2

olduğundan

2n\equiv 2\ (\mathrm{mod}\ 8)

, buradan

n\equiv 1\ (\mathrm{mod}\ 4)

. Deməli,

n=4k+1

şəklindədir. Bunu digər iki ifadədə yerinə qoyaq:

13n-1=52k+12=4(13k+3),\qquad 85n-1=340k+84=4(85k+21).

Üçüncü addım:

4

tam kvadratdır, ona görə

4(13k+3)

tam kvadrat olması üçün

13k+3

də tam kvadrat olmalıdır (kvadratın kökü cütdür,

b=2b'

yazsaq

b'^2=13k+3

alınır); eyni ilə

85k+21

də tam kvadrat olmalıdır. İndi bu iki yeni şərti

\bmod\ 4

-də toqquşduraq:

13\equiv 1

3\equiv 3\ (\mathrm{mod}\ 4)

olduğundan

13k+3\equiv k+3

, və bunun

\{0,1\}

çoxluğunda olması üçün

k\equiv 1

və ya

k\equiv 2\ (\mathrm{mod}\ 4)

olmalıdır. Digər tərəfdən

85\equiv 1

21\equiv 1\ (\mathrm{mod}\ 4)

olduğundan

85k+21\equiv k+1

, və bunun

\{0,1\}

-də olması üçün

k\equiv 3

və ya

k\equiv 0\ (\mathrm{mod}\ 4)

olmalıdır. İki tələb

\{1,2\}

və

\{3,0\}

çoxluqlarını verir, onların kəsişməsi boşdur — ziddiyyət. Deməli, belə

n

ümumiyyətlə yoxdur. Cavab:

0

Məsələ 15. UMO 2009 ·

11^2+13^2+17^2,\quad 24^2+25^2+26^2,\quad 12^2+24^2+36^2,\quad 11^2+12^2+132^2

cəmlərindən neçəsi tam kvadratdır?

Həll. Dörd cəmi bir-bir yoxlayaq; birbaşa kök almaqdansa uyğun modulla işləmək daha sürətlidir. Birinci cəm:

11,13,17

— üçü də təkdir, tək ədədin kvadratı isə

\bmod\ 8

-də

1

verir, deməli cəm

\equiv 1+1+1=3\ (\mathrm{mod}\ 8)

. Tam kvadratlar

\bmod\ 8

-də yalnız

0,1,4

ola bildiyi üçün bu cəm tam kvadrat deyil. İkinci cəm: yenə

\bmod\ 8

götürək.

24=8\cdot 3

olduğundan

24^2\equiv 0

;

25

təkdir,

25^2\equiv 1

;

26=2\cdot 13

və

26^2=4\cdot 169

169

tək olduğundan

26^2\equiv 4\ (\mathrm{mod}\ 8)

. Cəm

\equiv 0+1+4=5\ (\mathrm{mod}\ 8)

, bu da

\{0,1,4\}

-də olmadığı üçün tam kvadrat deyil. Üçüncü cəm: burada ortaq vuruq var —

12^2+24^2+36^2=12^2(1^2+2^2+3^2)=144\cdot 14=2016

144=12^2

tam kvadrat olduğundan cəmin tam kvadrat olması üçün

14

tam kvadrat olmalıdır, halbuki

3^2<14<4^2

. Daha rəsmi olaraq

2016=2^5\cdot 3^2\cdot 7

kanonik ayrılışında

2

-nin qüvvəti

5

— təkdir, tam kvadratda isə bütün qüvvətlər cüt olmalıdır; deməli, tam kvadrat deyil. Dördüncü cəm:

121+144+17424=17689

, və

133^2=17689

olduğundan bu, tam kvadratdır. Beləliklə, dörd cəmdən yalnız biri tam kvadratdır. Cavab:

1

Məsələ 16. Junior Balkan MO 1997 ·

n_1,n_2,\dots,n_{1998}

natural ədədləri

n_1^2+n_2^2+\dots+n_{1997}^2=n_{1998}^2

bərabərliyini ödəyir. Bu ədədlərdən ən azı neçəsi cüt olmalıdır?

Həll. Sual «ən azı neçəsi» olduğu üçün iki iş görməliyik: aşağıdan qiymətləndirmə (bundan az ola bilməz) və nümunə (bu qədəri mümkündür). Bütün hesablamanı

\bmod\ 8

aparırıq, çünki tək ədədin kvadratı

\bmod\ 8

-də dəqiq

1

-dir, cüt ədədin kvadratı isə

0

və ya

4

ola bilər — bu, cüt/tək sayını izləmək üçün ən əlverişli süzgəcdir. Fərz edək ki, sol tərəfdəki

1997

ədədin hamısı təkdir. Onda sol tərəf

\equiv 1997\ (\mathrm{mod}\ 8)

, və

1997=8\cdot 249+5

, yəni sol tərəf

\equiv 5\ (\mathrm{mod}\ 8)

. Lakin sağ tərəf tam kvadratdır və

\bmod\ 8

-də yalnız

0,1,4

ola bilər — ziddiyyət. Deməli, soldakılar arasında ən azı bir cüt ədəd var. İndi göstərək ki, ümumilikdə ən azı iki cüt ədəd olmalıdır. Tutaq ki, soldakılar arasında dəqiq bir cüt ədəd var; onda tək ədədlərin sayı

1996

-dır və sol tərəf

\equiv 1996\cdot 1+e\ (\mathrm{mod}\ 8)

, burada

e\in\{0,4\}

cüt ədədin kvadratının qalığıdır.

1996\equiv 4\ (\mathrm{mod}\ 8)

olduğundan sol tərəf

\equiv 4

və ya

0\ (\mathrm{mod}\ 8)

, yəni hər halda cütdür, deməli

n_{1998}^2

cütdür və

n_{1998}

də cütdür — bu artıq ikinci cüt ədəddir. Əgər soldakı cüt ədədlərin sayı

2

-dən azdırsa, tək variant onun

1

olmasıdır (sıfır olmadığını yuxarıda gördük), o hal da indicə göstərildiyi kimi

n_{1998}

-i cüt edir; deməli, hər halda ən azı

2

cüt ədəd var. Nəhayət,

2

sayının əldə oluna bildiyini nümunə ilə görək:

n_1=\dots=n_{1996}=1

n_{1997}=498

n_{1998}=500

götürək. Doğrudan da

1996\cdot 1+498^2=1996+248004=250000=500^2

, və burada cüt olanlar yalnız

498

ilə

500

-dür. Cavab:

2

3Kublar və daha yüksək qüvvətlərKvadratlar üçün işlətdiyimiz üsul heç bir dəyişiklik olmadan kublara və daha yüksək qüvvətlərə keçir: tam ədədləri modula görə bir neçə hala ayırırıq, hər halda qüvvəti açırıq və alınan qalıqlar siyahısına baxırıq. Yeganə fərq odur ki, hər qüvvət üçün öz ən əlverişli modulu var. Kvadratların ən əlverişli modulları 4 və 8-dirsə, kubların ən əlverişlisi 9-dur. Bu seçimin səbəbi təsadüfi deyil. Bir modulun bizim üçün faydalı olmasının yeganə ölçüsü budur: həmin modula görə baxılan qüvvətin ala biləcəyi qalıqların sayı az olsun. Nə qədər az qalıq varsa, ziddiyyət qurmaq üçün bir o qədər çox «boş yer» qalır. Məsələn, mod 9-a görə ümumiyyətlə 9 qalıq mövcuddur, lakin kublar onlardan yalnız üçünü tutur — yəni qalıqların üçdə ikisi kublar üçün qadağan olunmuş zonadır. Məhz bu qadağan olunmuş zona bizim əsas silahımızdır.

Teorem 3.1 (9 moduluna görə kublar). İstənilən tam

n

ədədi üçün

n^3 \equiv 0,\ 1\ \text{və ya}\ -1 \pmod 9 .

Başqa sözlə, heç bir tam ədədin kubu mod 9-a görə

2,3,4,5,6,7

qalıqlarından birini vermir.

İsbat. Qalıqlı bölmə haqqında teorem (Dərs 2)

n

ədədini 3-ə böldükdə üç haldan birinin baş verdiyini deyir:

n=3k

n=3k+1

və ya

n=3k+2

. Sonuncu halda mənfi qalıqdan (nümayəndədən) istifadə edib

n=3k-1

yazmaq daha rahatdır (Dərs 5); bu, eyni haldır, sadəcə

k

-nı bir vahid böyük götürürük. Diqqət yetirin ki, biz

n

-i 3-ə görə hallara ayırırıq, halbuki cavab 9 moduluna görədir — səbəbi az sonra aydın olacaq: kubu açanda bütün aralıq hədlər

9

-un bölünəni (misli) olur. I hal.

n=3k

. Onda

n^3=(3k)^3=27k^3=9\cdot(3k^3),

yəni

9\mid n^3

və deməli

n^3\equiv 0 \pmod 9

. II hal.

n=3k+1

. Kubu açırıq:

(3k+1)^3=27k^3+3\cdot 9k^2\cdot 1+3\cdot 3k\cdot 1+1 =27k^3+27k^2+9k+1 .

Burada ilk üç həddin hər biri 9-a bölünür:

27k^3=9(3k^3)

27k^2=9(3k^2)

9k=9\cdot k

. Deməli

n^3=9\,(3k^3+3k^2+k)+1\equiv 1 \pmod 9 .

III hal.

n=3k-1

. Eyni açılış, sadəcə işarələr növbələnir:

(3k-1)^3=27k^3-27k^2+9k-1 =9\,(3k^3-3k^2+k)-1\equiv -1 \pmod 9 .

Üç halın hamısı yoxlandı və başqa hal yoxdur, ona görə də

n^3

mod 9-a görə yalnız

0

1

-1

qalıqlarını ala bilər. Mənfi qalıqları müsbət qalıqlarla əvəz etsək, siyahı

\{0,1,8\}

olur.

Qeyd. Sübutun əsl mahiyyəti ikinci halda göründü:

(3k\pm1)^3

açılışındakı bütün «qarışıq» hədlərdə

3

-ün ən azı iki nüsxəsi var (

27k^3

27k^2

9k

), ona görə də hamısı

9

-a bölünür. Məhz buna görə kublar üçün

9

işləyir, amma məsələn

27

işləmir —

9k

həddi

27

-yə bölünmür. Yəni, modulu təsadüfən yox, açılışdakı əmsallara baxaraq seçirik.

Nəticə 3.2. Üç tam kubun cəmi mod 9-a görə yalnız

0,\ \pm1,\ \pm2,\ \pm3

qalıqlarını ala bilər. Deməli,

9k+4

və

9k+5

şəklində olan heç bir ədəd üç tam kubun cəmi kimi yazıla bilməz.

İsbat. Tutaq ki,

N=a^3+b^3+c^3

. Teoremə görə

a^3,b^3,c^3

-ün hər biri mod 9-a görə

-1,0,1

ədədlərindən birinə konqruentdir. Üç belə ədədin cəmi ən azı

-3

, ən çoxu

+3

ola bilər, yəni cəm

\{-3,-2,-1,0,1,2,3\}

çoxluğundan bir qiymətə konqruentdir. Bu qalıqları

0

ilə

8

arasına gətirsək,

\{0,1,2,3,6,7,8\}

alınır. Bu siyahıda

4

və

5

yoxdur. İndi

N\equiv 4 \pmod 9

olsun. Onda

N

üç kubun cəmi olarsa,

4

yuxarıdakı siyahıda olmalı idi — ziddiyyət. Eyni mühakimə

N\equiv 5 \pmod 9

üçün də keçir. Qeyd edək ki,

9k-4

və

9k+5

eyni sinifdir, çünki

-4\equiv 5\pmod 9

Qeyd. Bu, «ola bilməz» tipli iddianın çox tipik nümunəsidir: məsələn

4

13

22

31

\dots

və

5

14

23

32

\dots

ədədlərinin heç biri üç tam kubun cəmi deyil. Diqqət: burada kublar mənfi də ola bilər — mühakimə buna heç nə ilə mane olmur, çünki teorem bütün tam ədədlər üçün doğrudur. Bu, məsələnin gücünü artırır: hətta mənfi ədədlərə icazə versək belə, cəm alınmır.

Teorem 3.3 (7 moduluna görə kublar). İstənilən tam

n

üçün

n^3\equiv 0,\ 1\ \text{və ya}\ -1 \pmod 7 .

İsbat. Burada

n

-i birbaşa

7

-yə görə hallara ayırırıq:

n

mod 7 üzrə

0,1,2,3,4,5,6

qalıqlarından birinə konqruentdir və Dərs 5-in qaydasına görə

a\equiv b

olduqda

a^3\equiv b^3

. Deməli, yalnız yeddi ədədin kubunu hesablamaq kifayətdir. Hesabı yüngülləşdirmək üçün

4,5,6

əvəzinə mənfi qalıqları (nümayəndələri) götürürük:

4\equiv-3

5\equiv-2

6\equiv-1

. Onda kubun tək qüvvət olması sayəsində

(-a)^3=-a^3

, yəni yeni heç nə hesablamağa ehtiyac qalmır:

\begin{array}{c|ccccccc} n \bmod 7 & 0 & 1 & 2 & 3 & -3 & -2 & -1\\\hline n^3 & 0 & 1 & 8 & 27 & -27 & -8 & -1\\\hline n^3 \bmod 7 & 0 & 1 & 1 & -1 & 1 & -1 & -1 \end{array}

Burada

8=7+1\equiv 1

və

27=28-1\equiv-1

istifadə olunub. Cədvəldə cəmi üç müxtəlif qiymət var:

0

1

-1

. Müsbət qalıqlarla isə bu,

\{0,1,6\}

deməkdir.

Qeyd. İki teoremi yan-yana qoyanda maraqlı bir simmetriya görünür: həm mod 7, həm də mod 9 üçün kublar yalnız

\{0,\pm1\}

qiymətlərini alır. Bunun arxasında dərin bir səbəb var və onu Dərs 7-də açacağıq. Praktikada isə hər iki modulu əldə saxlamaq lazımdır, çünki biri işləməyəndə digəri işləyə bilər — bunu

2026

nümunəsində birbaşa görəcəyik.

Teorem 3.4 (Dördüncü qüvvətlər). İstənilən tam

n

üçün

n^4\equiv 0\ \text{və ya}\ 1 \pmod 5, \qquad n^4\equiv 0\ \text{və ya}\ 1 \pmod{16}.

İsbat. Mod 5.

n

-in beş qalığını yoxlayırıq; yenə mənfi qalıqlardan istifadə edirik:

3\equiv-2

4\equiv-1

. Dördüncü qüvvət cüt qüvvət olduğundan işarə itir,

(-a)^4=a^4

\begin{array}{c|ccccc} n \bmod 5 & 0 & 1 & 2 & -2 & -1\\\hline n^4 & 0 & 1 & 16 & 16 & 1\\\hline n^4 \bmod 5 & 0 & 1 & 1 & 1 & 1 \end{array}

Yəni

5\mid n

olduqda

n^4\equiv 0

, əks halda

n^4\equiv 1 \pmod 5

. Mod 16. Burada beş yerinə on altı hala baxmaq yorucudur; bunun əvəzinə

n

-in cüt və ya tək olmasına görə iki hala ayırırıq. I hal: $n$ cütdür, yəni

n=2t

. Onda

n^4=(2t)^4=16t^4\equiv 0 \pmod{16}.

II hal: $n$ təkdir. Burada Bölmə 2-də isbat etdiyimiz mühüm faktı işə salırıq: tək ədədin kvadratı mod 8-ə görə

1

-ə konqruentdir. Bu o deməkdir ki, elə tam

t

var ki,

n^2=8t+1 .

İndi hər iki tərəfi kvadrata yüksəldirik —

n^4=(n^2)^2

olduğuna diqqət yetirin:

n^4=(8t+1)^2=64t^2+16t+1 .

Sağ tərəfdəki ilk iki hədd

16

-ya bölünür:

64t^2=16\cdot 4t^2

və

16t=16\cdot t

. Deməli

n^4=16\,(4t^2+t)+1\equiv 1 \pmod{16}.

Beləliklə, hər iki halda

n^4

0

-a, ya da

1

-ə konqruentdir.

Qeyd. Sonuncu addım tipik bir «yüksəltmə» hərəkətidir: mod 8-də bildiyimiz zəif fakt kvadrata yüksəldiləndə mod 16-da daha güclü fakta çevrildi. Səbəb budur ki,

(8t+1)^2

açılışındakı ikiqat hədd

2\cdot 8t=16t

-dir və o, artıq

16

-ya bölünür. Bu üsulu yadda saxlayın — «kvadratı kvadrata yüksəltmək modulu iki dəfə gücləndirir».

Teorem 3.5 (Beşinci qüvvət və son rəqəm). İstənilən tam

n

üçün

n^5\equiv n \pmod{10},

yəni

n^5

ədədinin son rəqəmi həmişə

n

-in son rəqəmi ilə üst-üstə düşür.

İsbat.

10=2\cdot 5

olduğundan iddianı iki hissəyə bölürük. Addım 1: $2\mid n^5-n$ .

n

cütdürsə,

n^5

də cütdür (cüt ədədin qüvvəti cütdür), onda fərq cütdür.

n

təkdirsə,

n^5

də təkdir, tək ədədlərin fərqi yenə cütdür. Hər iki halda

n^5\equiv n \pmod 2

. Addım 2: $5\mid n^5-n$ .

n

-in beş qalığını yoxlayırıq (Dərs 5-ə görə

a\equiv b \Rightarrow a^5\equiv b^5

, yəni yalnız qalıqları hesablamaq kifayətdir):

\begin{array}{c|ccccc} n \bmod 5 & 0 & 1 & 2 & 3 & 4\\\hline n^5 & 0 & 1 & 32 & 243 & 1024\\\hline n^5 \bmod 5 & 0 & 1 & 2 & 3 & 4 \end{array}

Hər sütunda aşağıdakı sətir yuxarıdakı ilə eynidir, yəni

n^5\equiv n \pmod 5

. Addım 3: birləşdirmə. İndi

2\mid n^5-n

və

5\mid n^5-n

(2,5)=1

olduğundan Dərs 4-dəki qaydaya görə (

(a,b)=1

a\mid N

b\mid N

\Rightarrow ab\mid N

) alırıq

10\mid n^5-n

, yəni

n^5\equiv n \pmod{10}

. Nəhayət, bir ədədin son rəqəmi onun mod 10 qalığıdır (Dərs 5), deməli,

n^5

ilə

n

-in son rəqəmləri eynidir.

Qeyd. Addım 3-dəki qayda olmasa, iddianı birbaşa mod 10-da on hala ayırıb da isbat etmək olardı — amma o zaman

9^5

kimi böyük ədədləri hesablamalı olurduq. İki kiçik moduldan böyüyünü qurmaq həmişə daha əlverişlidir. Diqqət: bu birləşdirmə yalnız modullar qarşılıqlı sadə olduqda işləyir. Məsələn,

4\mid N

və

6\mid N

olmasından

24\mid N

alınmır.

Nümunə 3.1.

2026

ədədi tam kubdurmu? Birinci cəhd — mod 9. Rəqəmlərinin cəmi

2+0+2+6=10

, ondan da

1+0=1

, deməli

2026\equiv 1 \pmod 9

(Dərs 5-in 9-a bölünmə əlaməti). Lakin kublar mod 9-a görə

\{0,1,-1\}

qalıqlarını alır və

1

bu siyahıdadır. Deməli mod 9 heç bir ziddiyyət vermir — bu modul bizə kömək etmir. İkinci cəhd — mod 7.

2026=7\cdot 289+3

, yəni

2026\equiv 3 \pmod 7

. Kublar isə mod 7-yə görə yalnız

\{0,1,-1\}=\{0,1,6\}

qalıqlarını alır.

3

bu siyahıda yoxdur, deməli,

2026

tam kub deyil. Nəzarət üçün:

12^3=1728

və

13^3=2197

, yəni

2026

həqiqətən iki ardıcıl kubun arasındadır.

Qeyd. Bu nümunə metodun ən vacib xüsusiyyətini göstərir: bir modulun ziddiyyət verməməsi heç nə isbat etmir. Mod 9 susdu, mod 7 danışdı. Ona görə də olimpiadada bir modul işləməyəndə dərhal təslim olmayın — siyahıdakı digər modulları da yoxlayın. Eyni zamanda əks tərəfi də unutmayın: əgər bütün sınadığınız modullar susursa, bu, ədədin kub olduğunu sübut etmir; onda başqa alətə keçmək lazımdır.

Hansı qüvvət üçün hansı modul. Aşağıdakı cədvəl olimpiadada ən çox istifadə olunan seçimləri toplayır. Sol sütunda baxdığımız obyekt, sağda isə həmin obyektin mümkün qalıqları durur.

\begin{array}{c|c|c} \text{obyekt} & \text{modul} & \text{mümkün qalıqlar}\\\hline n^2 & 3 & 0,1\\ n^2 & 4 & 0,1\\ n^2 & 5 & 0,1,4\\ n^2 & 8 & 0,1,4\\ n^2 & 9 & 0,1,4,7\\ n^2 & 16 & 0,1,4,9\\\hline n^3 & 7 & 0,1,-1\\ n^3 & 9 & 0,1,-1\\\hline n^4 & 5 & 0,1\\ n^4 & 16 & 0,1\\\hline n^5 & 11 & 0,1,-1\\ n^5 & 10 & n^5\equiv n \end{array}

İstifadə qaydası belədir:

1. Məsələdə hansı qüvvətin iştirak etdiyini müəyyən edin.
2. Cədvəldən həmin sətirdəki modulları bir-bir sınayın; əvvəlcə kiçikləri, çünki hesab daha yüngüldür.
3. İki müxtəlif qüvvət varsa (məsələn, həm kvadrat, həm kub), onların hər ikisi üçün eyni modulun məhdud siyahı verməsi ideal haldır.

Ümumi prinsip:

k

-cı qüvvətlər üçün modulu elə seçirik ki, həmin modula görə qüvvətin ala biləcəyi qalıqların sayı mümkün qədər az olsun. Kiçik siyahı

=

böyük qadağan olunmuş zona

=

ziddiyyət qurmaq üçün geniş imkan.

Qeyd. Cədvəldəki modulların seçimi təsadüfi görünə bilər, lakin arxasında dərin bir qanunauyğunluq var:

3=2\cdot1+1

7=3\cdot2+1

5=4\cdot1+1

11=5\cdot2+1

— yəni

k

-cı qüvvətlər üçün seçilən sadə modul

p

çox vaxt

p-1

-in

k

-ya bölündüyü sadə ədəddir. Bunun səbəbini Dərs 7-də Ferma teoremi ilə tam izah edəcəyik. Hələlik hər faktı bilavasitə hallara ayırmaqla isbat edirik — bu, həm tam dürüstdür (heç bir isbatlanmamış fakta söykənmirik), həm də imtahanda hər cədvəl sətrini 30 saniyəyə yenidən qurmağa imkan verir. Cədvəli əzbərləməkdənsə, onu qurmağı bacarmaq daha etibarlıdır.

Məsələ 17. Məşq ·

2023

və

2025

ədədlərindən hər hansı biri tam kub ola bilərmi?

Həll. Tam kubları « tutmaq» üçün ən əlverişli modul

9

-dur, çünki istənilən

n

üçün

n^{3}\equiv 0,\ 1

və ya

-1 \pmod 9

olur (bunu

n\equiv 0,\pm1,\pm2,\pm3,\pm4

hallarını yoxlamaqla görmək olar). Üstəlik,

9

modulu ilə işləmək çox rahatdır: ədədin özünü deyil, rəqəmləri cəmini götürmək kifayətdir.

2023

üçün rəqəmlər cəmi

2+0+2+3=7

, yəni

2023\equiv 7\pmod 9

; lakin

7\notin\{0,1,8\}

olduğundan

2023

tam kub deyil. İndi

2025

-ə baxaq: rəqəmlər cəmi

2+0+2+5=9

, yəni

2025\equiv 0\pmod 9

— bu modul heç bir ziddiyyət vermir, çünki

0

mümkün qalıqdır. Ona görə də ikinci alətə, yəni

7

moduluna keçirik: burada da

n^{3}\equiv 0,\pm1 \pmod 7

-dir.

2025=7\cdot 289+2

olduğundan

2025\equiv 2\pmod 7

, halbuki

2\notin\{0,1,6\}

; deməli,

2025

də tam kub deyil. (Nəzarət üçün:

12^{3}=1728

13^{3}=2197

, yəni hər iki ədəd ardıcıl iki kubun arasındadır.) Cavab: Heç biri tam kub deyil.

Məsələ 18. Məşq · Sübut edin ki,

2029

ədədi üç tam ədədin kublarının cəmi kimi yazıla bilməz.

Həll. Fərz edək ki,

2029=a^{3}+b^{3}+c^{3}

olacaq şəkildə

a,b,c

tam ədədləri var. Belə məsələlərdə modulun seçimi tamamilə kubların davranışı ilə diktə olunur:

9

modulunda kublar yalnız

0,\ 1,\ -1

qalıqlarını alır, yəni üç kubun cəmi

-3

-dən

3

-ə qədər olan qalıqlardan birinə bərabər olmalıdır. Başqa sözlə,

a^{3}+b^{3}+c^{3}

ifadəsi

9

-a bölündükdə

4

və ya

5\ (\equiv -4)

qalığını verə bilməz — bu, « üç kubun cəmi

9k\pm 4

formasında ola bilməz» faktıdır. İndi

2029

-un

9

-a görə qalığını rəqəmlər cəmi ilə tapaq:

2+0+2+9=13

və

1+3=4

, yəni

2029\equiv 4\pmod 9

(doğrudan da

2029=9\cdot 225+4

). Deməli, sol tərəf

9

-a görə

4

qalığını verməlidir, sağ tərəf isə bunu heç vaxt verə bilməz. Alınan ziddiyyət göstərir ki, belə

a,b,c

mövcud deyil. Qeyd edək ki, mühakimə mənfi ədədləri də əhatə edir, çünki

9

modulunda qalıqlar haqqındakı fakt bütün tam ədədlər üçün doğrudur. Cavab: Yazıla bilməz.

Məsələ 19. Məşq ·

1\le n\le 100

şərtini ödəyən neçə

n

tam ədədi üçün

n^{3}-n

ifadəsi

24

-ə bölünür?

Həll. Əvvəlcə ifadəni vuruqlara ayıraq:

n^{3}-n=n(n^{2}-1) =(n-1)n(n+1)

, yəni bu, üç ardıcıl tam ədədin hasilidir.

24=8\cdot 3

və

(8,3)=1

olduğundan

24

-ə bölünməni iki müstəqil şərtə parçalaya bilərik:

3

-ə bölünmə və

8

-ə bölünmə. Üç ardıcıl ədəddən biri həmişə

3

-ə bölündüyünə görə

3\mid (n-1)n(n+1)

şərti heç bir məhdudiyyət qoymur — bütün iş

8

-ə bölünmədədir. Əgər

n

təkdirsə,

n-1

və

n+1

ardıcıl iki cüt ədəddir, onlardan biri mütləq

4

-ə bölünür, deməli, hasilləri

2\cdot 4=8

-ə bölünür və şərt avtomatik ödənilir. Əgər

n

cütdürsə,

n-1

və

n+1

təkdir, ona görə bütün

2

-lik vuruqlar yalnız

n

-dən gəlir və

8\mid n

olmalıdır. Beləliklə, şərt «

n

tək, yaxud

8\mid n

» kimi yazılır:

1

-dən

100

-ə qədər

50

tək ədəd var,

8

-ə bölünənlər isə

8,16,\dots ,96

, yəni

12

ədəddir. Bu iki hal kəsişmədiyi üçün cavab

50+12=62

-dir. Cavab:

62

Məsələ 20. Məşq ·

x^{4}+y^{4}+z^{4}=2026

tənliyinin tam ədədlərdə həllinin olmadığını göstərin.

Həll. Dördüncü qüvvətlər üçün ən güclü iki alət

5

və

16

modullarıdır; burada sağ tərəf

5

-ə bölünmə baxımından maraqsız olduğundan

16

modulunu seçirik. Doğrudan da,

n

cüt olarsa

n=2m

və

n^{4}=16m^{4}\equiv 0\pmod{16}

;

n

tək olarsa

n^{2}\equiv 1\pmod 8

, yəni

n^{2}=8k+1

və

n^{4}=64k^{2}+16k+1\equiv 1\pmod{16}

. Beləliklə, hər tam

n

üçün

n^{4}\equiv 0

və ya

1\pmod{16}

. Onda üç dördüncü qüvvətin cəmi

16

modulunda yalnız

0,1,2,3

qalıqlarından birini verə bilər. Sağ tərəfi hesablayaq:

2026=16\cdot 126+10

, yəni

2026\equiv 10\pmod{16}

10\notin\{0,1,2,3\}

olduğundan bərabərlik mümkün deyil və tənliyin tam ədədlərdə həlli yoxdur. Cavab: Həlli yoxdur.

Məsələ 21. Məşq ·

1^{5}+2^{5}+3^{5}+\dots +2026^{5}

cəminin son rəqəmini tapın.

Həll. Son rəqəm sualı

10

modulunda işləmək deməkdir və beşinci qüvvətlər üçün bu modulda çox rahat bir fakt var: hər tam

n

üçün

n^{5}\equiv n\pmod{10}

. Bunu görmək üçün

n^{5}-n

ifadəsinin həm

2

-yə, həm də

5

-ə bölündüyünü yoxlamaq kifayətdir (məsələn,

n

-in

5

-ə görə

0,\pm1,\pm2

qalıqlarını yerinə yazmaqla),

(2,5)=1

olduğundan onda

10\mid n^{5}-n

. Bu konqruensiyanı

n=1,2,\dots ,2026

üçün yazıb topladıqda cəm sadə bir arifmetik cəmə çevrilir:

1^{5}+\dots +2026^{5}\equiv 1+2+\dots +2026 =\frac{2026\cdot 2027}{2}=1013\cdot 2027\pmod{10}.

İndi yalnız hasilin son rəqəmini tapmaq qalır:

1013\equiv 3

və

2027\equiv 7\pmod{10}

, deməli, hasil

3\cdot 7=21\equiv 1\pmod{10}

. Beləliklə, cəmin son rəqəmi

1

-dir. Cavab:

1

Məsələ 22. Türkiyə MO (UMO) 2005 ·

n<2005

müsbət tam ədəddir. Heç biri

5

-ə bölünməyən istənilən

a_{1},a_{2},\dots ,a_{n}

müsbət tam ədədləri üçün

a_{1}^{4}+a_{2}^{4}+\dots +a_{n}^{4}

cəminin

5

-ə bölünməsini təmin edən ən böyük

n

qiymətini tapın.

Həll. Şərtdə

5

-ə bölünmə və dördüncü qüvvətlər var, ona görə təbii modul

5

-dir.

5\nmid a

olduqda

a\equiv \pm1,\pm2

olur və

a^{2}\equiv 1

və ya

4\equiv -1

, deməli hər iki halda

a^{4}=(a^{2})^{2}\equiv 1\pmod 5

; yəni

5

-ə bölünməyən ədədin dördüncü qüvvəti həmişə

1

qalığını verir. Onda cəm çox sadələşir:

a_{1}^{4}+\dots +a_{n}^{4}\equiv \underbrace{1+1+\dots +1} _{n\ \text{dəfə}}=n\pmod 5 .

Deməli, cəmin

5

-ə bölünməsi

a_{i}

-lərin seçimindən asılı olmayaraq yalnız və yalnız

5\mid n

şərtinə bərabərdir. Əgər

5\nmid n

olsaydı, bütün

a_{i}=1

götürməklə cəmi

n

edərdik və o,

5

-ə bölünməzdi — yəni « istənilən

a_{i}

üçün» şərti pozulardı. Beləliklə,

n

ədədi

5

-ə bölünməli və

n<2005

olmalıdır; belə ən böyük ədəd

2000

-dir. Doğrudan da,

n=2000

üçün cəm

2000\equiv 0\pmod 5

, yəni şərt həmişə ödənilir. Cavab:

n=2000

Məsələ 23. Polşa MO 2003 ·

p

sadə ədəd,

x,y,z

tam ədədləri isə

0<x<y<z<p

şərtini ödəyir.

x^{3},\ y^{3},\ z^{3}

ədədləri

p

-yə bölündükdə eyni qalığı verirlərsə,

x^{2}+y^{2}+z^{2}

cəminin

x+y+z

ədədinə bölündüyünü isbat edin.

Həll. Şərti konqruensiya dilinə çevirək:

p\mid x^{3}-y^{3} =(x-y)(x^{2}+xy+y^{2})

. Burada

0<y-x<p

olduğundan

p

sadə ədədi

x-y

vuruğunu bölə bilməz, ona görə Evklid lemmasına əsasən

p\mid x^{2}+xy+y^{2}

; eyni qayda ilə

p\mid y^{2}+yz+z^{2}

və

p\mid x^{2}+xz+z^{2}

(qeyd edək ki,

0<x<y<z<p

şərti üçün

p\ge 5

olmalıdır). Birinci iki ifadənin fərqini alaq:

(x^{2}+xy+y^{2})-(y^{2}+yz+z^{2})=(x-z)(x+y+z)

, və yenə

p\nmid x-z

olduğundan

p\mid x+y+z

alırıq.

0<x+y+z<3p

olduğundan

s=x+y+z

p

-yə, ya da

2p

-yə bərabərdir. İndi

A=x^{2}+y^{2}+z^{2}

B=xy+yz+zx

işarə edək: üç konqruensiyanı toplasaq

p\mid 2A+B

s^{2}=A+2B

və

p\mid s

olduğundan isə

p\mid A+2B

; bunlardan

2(2A+B)-(A+2B)=3A

ifadəsinin

p

-yə bölündüyü çıxır, yəni

p\ge 5

olduğu üçün

p\mid A

. Əgər

s=p

-dirsə, isbat bitdi. Əgər

s=2p

-dirsə,

s

cütdür və

n^{2}\equiv n\pmod 2

olduğundan

A\equiv x+y+z=s\equiv 0\pmod 2

, yəni

A

həm

2

-yə, həm də

p

-yə bölünür;

(2,p)=1

olduğundan

2p=s\mid A

. Hər iki halda

x+y+z\mid x^{2}+y^{2}+z^{2}

. Cavab: İsbat olundu.

Məsələ 24. Junior Balkan MO 1999 · Hər

n\ge 0

tam ədədi üçün

a_{n}=2^{3n}+3^{6n+2}+5^{6n+2}

olaraq təyin olunub.

\text{ƏBOB}(a_{0},a_{1},\dots ,a_{1999})

ifadəsinin qiyməti neçədir?

Həll. Sonsuz sayda ədədin ƏBOB-unu birbaşa hesablamaq mümkün deyil, ona görə iki tərəfdən sıxışdırırıq: əvvəlcə ƏBOB-un böldüyü konkret bir ədəd tapırıq, sonra da bütün

a_{n}

-ləri bölən ədədi göstəririk.

n=0

üçün

a_{0}=1+9+25=35

, deməli, axtarılan ƏBOB

35=5\cdot 7

ədədinin bölənidir, yəni yalnız

1,\ 5,\ 7,\ 35

ola bilər. İndi

7

modulunu yoxlayaq və qüvvətlərin dövriliyindən istifadə edək:

2^{3}=8\equiv 1

, deməli

2^{3n}=(2^{3})^{n}\equiv 1\pmod 7

. Sonra

3^{2}\equiv 2,\ 3^{3}\equiv 6,\ 3^{6}\equiv 6^{2}=36\equiv 1 \pmod 7

, ona görə

3^{6n+2}=(3^{6})^{n}\cdot 3^{2}\equiv 9 \equiv 2\pmod 7

; eyni qayda ilə

5^{2}\equiv 4,\ 5^{3}\equiv 6,\ 5^{6}\equiv 36\equiv 1

və

5^{6n+2}\equiv 25\equiv 4\pmod 7

. Cəmləsək,

a_{n}\equiv 1+2+4=7\equiv 0\pmod 7

, yəni

7

bütün

a_{n}

-ləri bölür. Nəhayət

5

-in ortaq bölən olmadığını göstərək:

5

modulunda

a_{1}=2^{3}+3^{8}+5^{8}

üçün

2^{3}=8\equiv 3

3^{4}=81\equiv 1

olduğundan

3^{8}\equiv 1

5^{8}\equiv 0

, yəni

a_{1}\equiv 3+1+0=4\not\equiv 0\pmod 5

. Deməli, ƏBOB

5

-ə bölünmür və yeganə qalan qiymət

7

-dir. Cavab:

7

4«Mümkünsüzlük» (Ola bilməz) metoduİndi bütün alətləri bir metoda yığırıq. Olimpiadada ən çox rast gəlinən suallardan biri budur: « filan ifadə tam kvadrat ola bilərmi?», « filan tənliyin tam həlli varmı?». Belə suallarda cavab çox vaxt xeyr-dir və bunu isbat etməyin ən qısa yolu uyğun modulu seçib qalıqları müqayisə etməkdir. Metodun məntiqi çərçivəsi son dərəcə sadədir və Dərs 5-dəki «mümkünsüzlük» (əksini fərz etmə) mühakiməsi ilə eynidir. Tutaq ki, bərabərlik doğrudur. Bərabər ədədlərin istənilən modula görə qalıqları da bərabərdir. Deməli, sol tərəfin mümkün qalıqları çoxluğu ilə sağ tərəfin mümkün qalıqları çoxluğu kəsişməlidir. Əgər biz elə bir modul tapsaq ki, bu iki siyahının ortaq elementi olmasın, ilkin fərziyyə yanlışdır — bərabərlik mümkün deyil.

İş sxemi — dörd addım.

1. Sadələşdir və obyekti tanı. İfadəni açın, vuruqlara ayırın, tam kvadrata ayırın — məqsəd məsələdə hansı obyektin (tam kvadrat, tam kub, qüvvət, qüvvətlər cəmi) iştirak etdiyini aydın görməkdir. Bu addım atlanarsa, sonrakı modul seçimi kor-koranə olur.
2. Modulu seç. Tanıdığınız obyektin məhdud qalıq siyahısı olan modulu Bölmə 2–Bölmə 3 cədvəllərindən götürün. Əgər ifadədə açıq şəkildə bir ədəd görünürsə (məsələn, $5(n^2+2)$ ifadəsindəki $5$ , və ya $121$ -ə bölünmə sualındakı $11$ ), çox vaxt modul da elə odur.
3. Hər iki tərəfin qalığını hesabla. Sol tərəfin ala biləcəyi bütün qalıqları siyahıla, eyni şeyi sağ tərəf üçün et. Burada Dərs 5-in bütün əməliyyat qaydaları sərbəst işlədilir: konqruensiyaları toplamaq, vurmaq, qüvvətə yüksəltmək olar.
4. Müqayisə et. İki siyahının ortaq elementi yoxdursa — ziddiyyət, deməli, iddia edilən bərabərlik heç bir tam ədəd üçün mümkün deyil. Ortaq element varsa, bu modul nəticə vermir; başqa modul sınayın.

Nümunə 4.1 (Klassik nümunə 1). Ardıcıl beş tam ədədin kvadratları cəmi heç vaxt tam kvadrat ola bilməz. Həll. Beş ardıcıl ədədi elə işarələyək ki, hesab ən yüngül olsun: mərkəzi ədədi

n

götürüb ədədləri

n-2,\ n-1,\ n,\ n+1,\ n+2

kimi yazırıq. Bu seçim vacibdir — simmetriya sayəsində bütün xətti hədlər qarşılıqlı ixtisar olunacaq. Cəmi hesablayaq:

\begin{array}{l} (n-2)^2+(n-1)^2+n^2+(n+1)^2+(n+2)^2 =\\[2pt] \quad (n^2-4n+4)+(n^2-2n+1)+n^2+(n^2+2n+1)+(n^2+4n+4). \end{array}

n

-li hədlər:

-4n-2n+2n+4n=0

. Sabitlər:

4+1+0+1+4=10

. Deməli, cəm

S=5n^2+10=5\,(n^2+2).

İndi fərz edək ki,

S=m^2

bir tam kvadratdır.

5\mid S

olduğundan

5\mid m^2

;

5

sadə ədəd olduğuna görə Evklid lemmasına (Dərs 4) əsasən

5\mid m

. Onda

m=5r

və

m^2=25r^2

, yəni

25\mid S

. Amma

S=5(n^2+2)

olduğundan bu,

5\mid n^2+2

deməkdir, yəni

n^2\equiv -2\equiv 3 \pmod 5 .

Burada Bölmə 2-nin faktı işə düşür: tam kvadratlar mod 5-ə görə yalnız

0

1

4

qalıqlarını alır.

3

bu siyahıda yoxdur — ziddiyyət. Deməli,

S

heç bir tam

n

üçün tam kvadrat deyil.

Qeyd. Bu həlldə iki addımı qarışdırmamaq lazımdır.

5\mid S

olması özlüyündə heç bir ziddiyyət vermir — axı

5

-ə bölünən ədəd kvadrat ola bilər (məsələn,

25

). Ziddiyyəti verən

5

deyil,

25

-dir: kvadratda sadə vuruq həmişə cüt qüvvətlə iştirak etməlidir (Dərs 3, tam kvadratın əlaməti). Ən çox buraxılan səhv şagirdin

5\mid S

alıb dərhal

n^2+2\equiv 0

nəticəsinə keçməsidir — bu keçidin əsaslandırılması məhz yuxarıdakı Evklid lemması addımıdır.

Nümunə 4.2 (Klassik nümunə 2).

n^2+3n+5

ifadəsi heç bir tam

n

üçün

121

-ə bölünmür. Həll.

121=11^2

olduğundan işə

11

modulundan başlayırıq. Fərz edək ki, hansısa

n

üçün

121\ \big|\ n^2+3n+5 .

Addım 1 — tam kvadrata ayırmaq.

n^2+3n+5

ifadəsi içərisində

n

-in əmsalı tək olduğuna görə birbaşa tam kvadrat çıxarmaq kəsrlərə aparır. Bunun qarşısını almaq üçün ifadəni

4

-ə vururuq:

4(n^2+3n+5)=4n^2+12n+20=(2n+3)^2+11,

çünki

(2n+3)^2=4n^2+12n+9

və

20-9=11

. Bu eyniliyi istənilən vaxt bir sətirdə yenidən yoxlamaq olar. Addım 2 — $11$ -ə bölünmə. Fərziyyəmizə görə

121\mid n^2+3n+5

, deməli

121\mid 4(n^2+3n+5)

, yəni

121\ \big|\ (2n+3)^2+11 .

Xüsusən

11\mid (2n+3)^2+11

, buradan

11\mid (2n+3)^2

. Addım 3 — Evklid lemması.

11

sadə ədəddir və

11\mid (2n+3)\cdot(2n+3)

, deməli

11\mid 2n+3

. Addım 4 — kvadratı götürmək.

2n+3=11s

yazsaq,

(2n+3)^2=121s^2

, yəni

121\mid (2n+3)^2

. Addım 5 — ziddiyyət. İndi

121

həm

(2n+3)^2+11

ədədini, həm də

(2n+3)^2

ədədini bölür. Onda fərqi də bölməlidir (Dərs 2, xətti kombinasiyanın xassəsi):

121\ \big|\ \big[(2n+3)^2+11\big]-(2n+3)^2=11 .

Lakin

121>11>0

, yəni

121

ədədi

11

-i bölə bilməz — ziddiyyət. Deməli,

n^2+3n+5

heç vaxt

121

-ə bölünmür. Nəzarət.

n^2+3n+5

ifadəsi

11

-ə bölünə bilir:

n=4

üçün

16+12+5=33=3\cdot 11

n=15

üçün

225+45+5=275=25\cdot 11

n=26

üçün

676+78+5=759=69\cdot 11

. Göründüyü kimi, hər dəfə

11

məhz bir dəfə iştirak edir — teorem də bunu deyir.

Qeyd. Addım 1-dəki

4

-ə vurmanın niyə həllin məntiqinə zərər vurmadığını izah edək:

4

ilə

121

qarşılıqlı sadədir, ona görə də

121\mid X

ilə

121\mid 4X

eyni güclü şərtlərdir. Belə vurmaları edərkən həmişə yoxlayın ki, vurduğunuz ədəd modulla qarşılıqlı sadədir — əks halda məlumat itirmiş olarsınız.

Nümunə 4.3 (Klassik nümunə 3 — son rəqəm mühakiməsi). Bütün rəqəmləri eyni olan ikirəqəmli və daha uzun ədədlərin (

11,22,\dots,99,111,222,\dots

tipli) heç biri tam kvadrat deyil. Həll. Belə ədədi

N=\underbrace{dd\dots d}_{k}

kimi yazaq, burada

d\in\{1,2,\dots,9\}

və

k\ge 2

. Addım 1 — son rəqəm süzgəci. Bölmə 2-yə görə tam kvadratın son rəqəmi yalnız

0,1,4,5,6,9

ola bilər.

d\ne 0

olduğundan

d\in\{1,4,5,6,9\}.

Addım 2 — mod 4 süzgəci. Bir ədədin

4

-ə görə qalığı yalnız son iki rəqəmindən asılıdır, çünki

100=4\cdot 25

və deməli

N=100\cdot(\text{qalan hissə})+\overline{dd}

yazılışında birinci hədd

4

-ə bölünür. Son iki rəqəm

\overline{dd}=11d

olduğundan

N\equiv 11d\equiv 3d \pmod 4 .

Tam kvadratlar mod 4-ə görə yalnız

0

və

1

qalıqlarını alır. Addım 1-dən qalan namizədləri yoxlayaq:

\begin{array}{c|ccccc} d & 1 & 4 & 5 & 6 & 9\\\hline 3d \bmod 4 & 3 & 0 & 3 & 2 & 3 \end{array}

d=1,5,9

üçün qalıq

3

-dür,

d=6

üçün

2

— bunların heç biri kvadrat qalığı deyil. Yeganə sağ qalan namizəd

d=4

-dür. Addım 3 — $d=4$ halı. Bu halda

N=\underbrace{44\dots4}_{k} =4\cdot\underbrace{11\dots1}_{k}=4R_k,

burada

R_k

yalnız birlərdən ibarət ədəddir.

4=2^2

tam kvadrat olduğundan

N

tam kvadratdır o zaman və yalnız o zaman ki,

R_k

tam kvadratdır. Doğrudan da,

N=m^2

olsa,

m

cütdür (çünki

N

cütdür),

m=2u

, onda

4u^2=4R_k

, yəni

R_k=u^2

. Lakin

R_k

-nın son iki rəqəmi

11

-dir (

k\ge 2

), deməli

R_k\equiv 11\equiv 3 \pmod 4 ,

və

3

kvadrat qalığı deyil. Ziddiyyət. Beləliklə, bütün

d

qiymətləri aradan çıxdı: iki və daha çox eyni rəqəmdən ibarət heç bir ədəd tam kvadrat deyil.

Qeyd. Bu həll iki müxtəlif süzgəcin ardıcıl tətbiqinə gözəl nümunədir: mod 10 (son rəqəm) namizədləri beşə endirdi, mod 4 isə birə. Sonuncu namizədi kənarlaşdırmaq üçün əlavə bir üsul — kvadrat vuruğun ayrılması — lazım gəldi. Bu, tipik bir mənzərədir: bir modul çox vaxt hamını yox, çoxunu kəsir, qalan tək-tük halı ayrıca əl ilə yoxlamaq lazım olur. Belə hallarda « demək olar ki, hamısı alınmadı, deməli hamısı alınmır» demək səhvdir — qalan halı sona qədər araşdırmaq zəruridir.

Nümunə 4.4 (Klassik nümunə 4).

x^2+y^2=2027

tənliyinin tam həlli yoxdur. Həll. Modulu seçmək üçün sağ tərəfə baxırıq:

2027=4\cdot 506+3,\qquad\text{yəni}\qquad 2027\equiv 3 \pmod 4 .

Sağ tərəf

4k+3

şəklindədir — bu, dərhal mod 4-ü işarə edir. Sol tərəfi hesablayaq. Bölmə 2-yə görə hər tam kvadrat mod 4-ə görə

0

və ya

1

-dir. Deməli

x^2+y^2

üçün cəmi dörd kombinasiya var:

\begin{array}{c|cc} & y^2\equiv 0 & y^2\equiv 1\\\hline x^2\equiv 0 & 0 & 1\\ x^2\equiv 1 & 1 & 2 \end{array}

Yəni

x^2+y^2\equiv 0,1

və ya

2 \pmod 4

; qalıq

3

heç vaxt alınmır. Sol tərəfin mümkün qalıqları

\{0,1,2\}

, sağ tərəfinki isə

\{3\}

. Bu iki siyahı kəsişmir, deməli, bərabərlik heç bir tam

x,y

üçün mümkün deyil.

Qeyd. Bu mühakimədə

2027

-nin sadə olub-olmamasının heç bir rolu yoxdur — yalnız

4

-ə görə qalığı əhəmiyyətlidir. Eyni mühakimə

3

7

11

2023

2031

və ümumiyyətlə

4k+3

şəklindəki istənilən ədəd üçün işləyir. Metodun birtərəfli işləməsini isə yenə xatırladaq: mod 4 mühakiməsi

4k+1

şəklindəki ədədlər haqqında heç nə demir — onların bəziləri iki kvadratın cəmidir (

5=1+4

), bəziləri isə deyil (

21

Sıfıra bərabərləşdirmə və tam kvadrata ayırma üsulu. İki texniki addım metodun tətbiq dairəsini xeyli genişləndirir. 1) Sıfıra bərabərləşdirmə. Bərabərliyin bütün hədlərini bir tərəfə keçirib

F(x,y,\dots)=0

şəklinə salın, sonra mod götürün. Onda sağ tərəfin qalıq siyahısı ən sadəsi — yalnız

\{0\}

— olur və bütün iş sol tərəfin mümkün qalıqlarını sadalamağa gəlir. Sual sadələşir: «

F

heç

0

qalığını verə bilirmi?» 2) Tam kvadrata ayırma.

ax^2+bx+c

şəklindəki ifadə ilə işləyəndə kəsrlərdən qaçmaq üçün onu

4a

-ya vururuq:

4a\,(ax^2+bx+c)=4a^2x^2+4abx+4ac =(2ax+b)^2+(4ac-b^2).

Doğrudan da,

(2ax+b)^2=4a^2x^2+4abx+b^2

və qalan hissə

4ac-b^2

-dir. Beləliklə, məchul

x

artıq yalnız bir tam kvadratın içərisində qalır, ifadənin qalanı isə sabitdir. İndi kvadratların qalıq cədvəlini birbaşa tətbiq etmək olar. Bu düsturun praktik oxunuşu belədir:

4a\cdot(\text{ifadə})

ilə

(2ax+b)^2

ədədləri bir-birindən sabit

D=b^2-4ac

qədər fərqlənir. Klassik nümunə 2-də

a=1

b=3

c=5

idi, deməli

4ac-b^2=20-9=11

— elə yuxarıda istifadə etdiyimiz

+11

. Xəbərdarlıq.

4a

-ya vurmaq yalnız o zaman məlumat itirmir ki,

4a

ilə işlədiyiniz modul qarşılıqlı sadə olsun. Modul

2

-yə və ya

a

-nın vuruğuna bölünürsə,

4a\mid

vurması ilə süni həllər yarana bilər — belə hallarda vurma əvəzinə birbaşa hallara ayırmaq daha təhlükəsizdir.

Qeyd. Vacib bir həqiqəti açıq deyək: bəzi tənliklərin tam həlli yoxdur, lakin bunu heç bir modul göstərə bilmir — istənilən

m

üçün tənlik mod

m

-ə görə həll oluna bilir, buna baxmayaraq tam ədədlərdə həll yoxdur. Klassik nümunə

x^2-34y^2=-1

tənliyidir. Bu tənliyin tam həlli yoxdur (kiçik aralıqda birbaşa yoxlamaq olar:

y

-in bir neçə min qiyməti üçün

34y^2-1

heç vaxt tam kvadrat olmur), lakin kompüterlə yoxlasanız,

400

-ə qədər bütün modullar üçün konqruensiyanın həlli var — yəni heç bir modul ziddiyyət vermir. Deməli bu tənliyi «mümkünsüzlük» (ola bilməz) metodu ilə heç vaxt bağlaya bilməzsiniz. Nəticə: modul üsulu güclü, lakin universal deyil. Əgər siyahıdakı modulların hamısını sınayıb heç birindən nəticə almırsınızsa, iki ehtimal var: ya cavab əslində var-dır (yəni həll mövcuddur və onu tapmaq lazımdır), ya da mümkünsüzlüyü başqa alətlə göstərmək lazımdır — məsələn, ölçü/böyüklük mühakiməsi (ifadəni iki ardıcıl kvadratın arasına sıxışdırmaq), vuruqlara ayırma, və ya sonsuz eniş üsulu. Modulu sınamağa sərf olunan vaxt məhdud olmalıdır: iki-üç modul susdusa, alət dəyişin.

Məsələ 25. Məşq ·

x^{2}+y^{2}+z^{2}=2023

tənliyinin tam ədədlərdə həllinin olmadığını göstərin.

Həll. « Mümkünsüzlük» sxeminin birinci addımı uyğun modulu seçməkdir; kvadratlar üçün ən çox məlumat verən kiçik modul

8

-dir, çünki orada kvadratların qalıqları cəmi üç ədəddən ibarətdir:

n^{2}\equiv 0,\ 1

və ya

4\pmod 8

(cüt

n

üçün

0

və ya

4

, tək

n

üçün

1

). İkinci addım — sol tərəfin mümkün qalıqlarını tapmaq. Üç belə qalığı bütün mümkün üsullarla toplasaq:

0+0+0=0

0+0+1=1

0+1+1=2

1+1+1=3

0+0+4=4

0+1+4=5

1+1+4=6

0+4+4=8\equiv 0

1+4+4=9\equiv 1

4+4+4=12\equiv 4

— yəni

x^{2}+y^{2}+z^{2}

ifadəsi

8

-ə bölündükdə

0,1,2,3,4,5,6

qalıqlarından birini verir, lakin heç vaxt

7

qalığını vermir. Üçüncü addım — sağ tərəfi hesablamaq:

2023=8\cdot 252+7

, yəni

2023\equiv 7\pmod 8

. Dördüncü addım — ziddiyyət: bərabərliyin sol tərəfi

8

modulunda

7

ola bilmədiyi halda sağ tərəf məhz

7

-dir. Deməli, tənliyin heç bir tam ədəd həlli yoxdur. Cavab: Həlli yoxdur.

Məsələ 26. Məşq · Sübut edin ki, heç bir

n

tam ədədi üçün

3n^{2}-1

və

3n^{2}+2

ifadələri tam kvadrat ola bilməz.

Həll. Hər iki ifadədə

3n^{2}

toplananı var, yəni ifadələr

3

modulunda çox sadə görünür — bu, modulun seçimini birbaşa diktə edir.

3\mid 3n^{2}

olduğundan

3n^{2}-1\equiv -1\equiv 2\pmod 3

və eyni səbəbdən

3n^{2}+2\equiv 2\pmod 3

; yəni hər iki ifadə

3

-ə bölündükdə həmişə

2

qalığını verir. Digər tərəfdən kvadratların

3

modulunda qalıqları yalnız

\{0,1\}

çoxluğundandır:

n\equiv 0

olduqda

n^{2}\equiv 0

n\equiv \pm1

olduqda isə

n^{2}\equiv 1\pmod 3

. Fərz edək ki, hansısa

n

üçün

3n^{2}-1=k^{2}

; onda

k^{2}\equiv 2\pmod 3

alınır ki, bu da mümkün deyil. Eyni ziddiyyət

3n^{2}+2=k^{2}

fərziyyəsi üçün də alınır. Beləliklə, hər iki ifadə heç bir tam

n

üçün tam kvadrat deyil. Cavab: İsbat olundu.

Məsələ 27. Kanada MO 1971 · Sübut edin ki, heç bir

n

tam ədədi üçün

n^{2}+2n+12

ifadəsi

121

-ə bölünmür.

Həll.

121=11^{2}

olduğundan işi əvvəlcə

11

modulunda aparmaq, sonra isə tam kvadrata ayırmaq təbiidir:

n^{2}+2n+12=(n+1)^{2}+11

. Fərz edək ki, hansısa

n

üçün

121\mid (n+1)^{2}+11

. Onda xüsusi halda

11\mid (n+1)^{2}+11

olur, buradan

11\mid (n+1)^{2}

11

sadə ədəd olduğundan Evklid lemmasına görə

11\mid n+1

, yəni

n+1=11k

şəklindədir. Bunu ifadədə yerinə yazaq:

(n+1)^{2}+11=121k^{2}+11

. Bu ədədin

121

-ə bölünməsi

121\mid 11

deməkdir ki, bu da açıq-aydın yanlışdır (

121k^{2}

121

-ə bölünür, qalıq isə

11

olur). Alınan ziddiyyət fərziyyəni tamamilə təkzib edir:

n^{2}+2n+12

ədədi

11

-ə bölünə bilər, lakin heç vaxt

121

-ə bölünmür. Cavab: İsbat olundu.

Məsələ 28. Türkiyə MO (UMO) 1993 ·

x^{2}+(x+1)^{2}+(x+2)^{2}=y^{2}

tənliyinin

x,y

tam ədəd olmaqla neçə

(x,y)

həll cütü vardır?

Həll. Əvvəlcə sol tərəfi açıb sadələşdirək:

x^{2}+(x^{2}+2x+1)+(x^{2}+4x+4)=3x^{2}+6x+5

. İndi

3x^{2}+6x=3(x^{2}+2x)

toplananının

3

-ə bölündüyünü görürük — bu,

3

modulunu seçmək üçün açıq bir işarədir. Doğrudan da, hər tam

x

üçün

3x^{2}+6x+5\equiv 5\equiv 2\pmod 3

, yəni sol tərəf həmişə

3

-ə bölündükdə

2

qalığını verir. Digər tərəfdən

y^{2}

kvadratının

3

modulunda mümkün qalıqları yalnız

0

və

1

-dir. Deməli,

3x^{2}+6x+5=y^{2}

bərabərliyi

2\equiv 0

və ya

2\equiv 1\pmod 3

kimi mümkünsüz bir nəticəyə gətirir. Beləliklə, tənliyin heç bir tam həlli yoxdur; ardıcıl üç ədədin kvadratları cəmi heç vaxt tam kvadrat ola bilməz. Cavab:

0

Məsələ 29. Məşq · a)

2007,\ 2009,\ 2010,\ 2011

ədədlərindən neçəsi iki tam ədədin kvadratları cəmi kimi yazıla bilər? b)

55555555,\ 3333333,\ 1111111,\ 44444444,\ 2222222

ədədlərindən hansı iki tam ədədin kvadratları fərqi kimi yazıla bilməz?

Həll. a) İki ədədin kvadratları cəmi üçün əsas alət

4

modulu- dur:

x^{2},y^{2}\in\{0,1\}

olduğundan

x^{2}+y^{2}\equiv 0,1,2\pmod 4

, yəni

4k+3

formalı ədəd belə yazıla bilməz.

2007=4\cdot 501+3

və

2011=4\cdot 502+3

olduğundan bu iki ədəd dərhal aradan çıxır.

2010\equiv 2\pmod 4

olduğundan

4

modulu burada işləmir; ona görə

3

modulundakı fakta müraciət edirik:

3\mid x^{2}+y^{2}

olarsa

3\mid x

və

3\mid y

, deməli

9\mid x^{2}+y^{2}

. Lakin

2010=3\cdot 670

və

670

3

-ə bölünmür, yəni

9\nmid 2010

— ziddiyyət,

2010

da yazıla bilməz. Nəhayət

2009=28^{2}+35^{2}=784+1225

, yəni yalnız bir ədəd —

2009

— iki ədədin kvadratları cəmidir. b) Fərqlə iş tamam başqa cürdür:

x^{2}-y^{2} =(x-y)(x+y)

və

x-y

ilə

x+y

eyni cütlükdədir (fərqləri

2y

cütdür). Deməli, hasil ya tək, ya da

4

-ə bölünəndir; başqa sözlə

4k+2

formalı ədəd iki kvadratın fərqi ola bilməz. Verilən ədədlərdən

55555555

3333333

1111111

təkdir (tək

m

üçün

m=\left(\frac{m+1}{2}\right)^{2} -\left(\frac{m-1}{2}\right)^{2}

44444444=4\cdot 11111111

isə

4

-ə bölünür (

4m=(m+1)^{2}-(m-1)^{2}

). Yalnız

2222222=4\cdot 555555+2

ədədi

4

-ə bölündükdə

2

qalığını verir və buna görə iki kvadratın fərqi kimi yazıla bilməz. Cavab: a) yalnız

1

ədəd (

2009

); b)

2222222

Məsələ 30. Məşq · Sübut edin ki, əgər bir tam kvadratın onluqlar rəqəmi tək ədəddirsə, onda onun birlər rəqəmi mütləq

6

-dır.

Həll. Sual son iki rəqəm haqqında olduğundan

100

modulunda işləməliyik.

n

ədədini

n=10a+b

şəklində yazaq, burada

b

onun son rəqəmidir. Onda

n^{2}=100a^{2}+20ab+b^{2}\equiv 20ab+b^{2}\pmod{100}

, yəni

n^{2}

-nin son iki rəqəmi yalnız

20ab+b^{2}

ilə təyin olunur.

20ab

toplananının onluqlar rəqəmi

2ab

-nin son rəqəmidir və o həmişə cütdür, birlər rəqəminə isə heç bir təsiri yoxdur. Deməli

n^{2}

-nin onluqlar rəqəminin cütlüyü

b^{2}

-nin onluqlar rəqəminin cütlüyü ilə eynidir, birlər rəqəmi isə

b^{2}

-nin birlər rəqəmi ilə. İndi

b=0,1,\dots ,9

üçün

b^{2}

qiymətlərinə baxaq:

0,1,4,9,16,25,36,49,64,81

— onluqlar rəqəmləri uyğun olaraq

0,0,0,0,1,2,3,4,6,8

-dir. Bunlardan yalnız

b=4

(

16

) və

b=6

(

36

) hallarında onluqlar rəqəmi təkdir, hər iki halda isə

b^{2}

-nin birlər rəqəmi

6

-dır. Beləliklə, tam kvadratın onluqlar rəqəmi tək olarsa, birlər rəqəmi hökmən

6

olur (məsələn,

4^{2}=16

6^{2}=36

14^{2}=196

16^{2}=256

). Cavab: İsbat olundu.

Məsələ 31. Məşq · Sübut edin ki, dörd ardıcıl natural ədədin hasili heç vaxt tam kvadrat ola bilməz.

Həll. Hasili

P=n(n+1)(n+2)(n+3)

ilə işarə edək. Burada modul seçmək əvəzinə cəbri quruluşdan istifadə etmək daha səmərəlidir: kənar və orta vuruqları cütləşdirək —

n(n+3)=n^{2}+3n

və

(n+1)(n+2)=n^{2}+3n+2

m=n^{2}+3n

işarə etsək,

P=m(m+2)=m^{2}+2m=(m+1)^{2}-1

alınır, yəni hasil həmişə bir tam kvadratdan

1

vahid azdır. Fərz edək ki,

P=k^{2}

(

k\ge 0

); onda

(m+1)^{2}-k^{2}=1

, yəni

(m+1-k)(m+1+k)=1

. Tam ədədlərdə hasili

1

olan iki vuruq ya hər ikisi

1

, ya hər ikisi

-1

olmalıdır;

m+1+k>0

olduğundan

m+1-k=m+1+k=1

, buradan

k=0

və

m=0

. Lakin

n\ge 1

üçün

m=n^{2}+3n\ge 4>0

, yəni ziddiyyət alınır. Beləliklə,

P

heç vaxt tam kvadrat deyil; qeyd edək ki,

P+1=(m+1)^{2}=(n^{2}+3n+1)^{2}

isə həmişə tam kvadratdır. Cavab: İsbat olundu.

Məsələ 32. Rumıniya MO 2003 ·

p_{1}<p_{2}<\dots <p_{31}

sadə ədədləri üçün

p_{1}^{4}+p_{2}^{4}+\dots +p_{31}^{4}

cəmi

30

-a bölünürsə, bu sadə ədədlər arasında üç ardıcıl sadə ədədin olduğunu isbat edin.

Həll.

30=2\cdot 3\cdot 5

olduğundan hər bir sadə vuruğu ayrıca öyrənib sonra Dərs 4-dəki qaydaya (

(a,b)=1

a\mid n

b\mid n\Rightarrow ab\mid n

) əsasən birləşdirmək lazımdır. Tutaq ki,

p\ge 7

sadə ədədidir, yəni

p

ədədi

2,3,5

-ə bölünmür. Onda

p

tək olduğu üçün

p^{4}\equiv 1\pmod 2

;

p\equiv \pm 1\pmod 3

olduğundan

p^{2}\equiv 1

və

p^{4}\equiv 1\pmod 3

; nəhayət bu dərsin dördüncü qüvvətlər haqqındakı teoreminə görə

5\nmid p

olduqda

p^{4}\equiv 1\pmod 5

. Deməli,

2,3,5

ədədlərinin hər biri

p^{4}-1

ifadəsini bölür və onlar cüt-cüt qarşılıqlı sadə olduğundan

30\mid p^{4}-1

, yəni hər

p\ge 7

sadə ədədi üçün

p^{4}\equiv 1\pmod{30}

. Kiçik sadə ədədlər üçün isə istisnalar var:

2^{4}=16

3^{4}=81\equiv 21

5^{4}=625\equiv 25\pmod{30}

. İndi siyahıdakı

2,3,5

sadə ədədlərindən ibarət alt çoxluğu

T

ilə işarə edək; qalan

31-|T|

ədədin hər birinin dördüncü qüvvəti

1

qalığını verdiyindən cəm

\sum_{q\in T}q^{4}+(31-|T|)\pmod{30}

qalığına bərabərdir. Bütün səkkiz halı yoxlayaq:

T=\emptyset

üçün

31\equiv 1

;

T=\{2\},\{3\},\{5\}

üçün uyğun olaraq

16,\ 21,\ 25

;

T=\{2,3\},\{2,5\},\{3,5\}

üçün

6,\ 10,\ 15

; və yalnız

T=\{2,3,5\}

halında

16+21+25+28=90\equiv 0\pmod{30}

alınır. Deməli, cəmin

30

-a bölünməsi yalnız və yalnız

2

3

və

5

ədədlərinin hər üçünün siyahıda iştirakı deməkdir; bunlar isə ardıcıl üç sadə ədəddir və isbat tamamlanır. Cavab:

p_{1}=2,\ p_{2}=3,\ p_{3}=5

, yəni üç ardıcıl sadə ədəd mütləq iştirak edir.