Reja Taqqoslamalar va ularning xossalari

6-Misol. Agar a va b – ixtiyoriy butun sonlar, p – tub son bo’lsa, quyidagi taqqoslamani isbotlang

(a + b)^p  a^p + b^p (mod p).
Yechilishi. Binomni yoyish formulasidan:
.
O’ng tomonda ikkinchi qo’shiluvchidan boshlab, p-1 –nchi qo’shiluvchigacha barcha qo’shiluvchilar p ga bo’linadi, chunki
= , bu yerda k < p.
Demak, , i = 1, 2, ..., (p-1).
Bu yerdan (a + b)^p  a^p + b^p (mod p) kelib chiqadi.

Chegirmalar sinflari. Eyler va Ferma teoremalari

m natural songa bo’linganida bir xil r qoldiq qoladigan barcha butun sonlar to’plami m modul bo’yicha sonlar sinfini tashkil qiladi. Bu sinfning har bir soni umumiy holda mk+r, kZ ko’rinishda yoziladi. Barcha sinflar soni m ga teng.
Sinfning ixtiyoriy soni m modul bo’yicha chegirma deyiladi (shu sinfning boshqa sonlariga nisbatan).
Har bir sinfdan ixtiyoriy ravishda bittadan olingan sonlar to’plami berilgan m modul bo’yicha chegirmalarning to’la sinfi deyiladi.
Odatda chegirmalarning to’la sinfi sifatida berilgan m bo’yicha eng kichik manfiy bo’lmagan chegirmalar, ya’ni 0, 1, 2,..., m - 1 sistema olinadi.
Ba’zan berilgan m modul bo’yicha chegirmalardan absolyut qiymati bo’yicha eng kichik musbat bo’lmagan chegirmalarning to’la sistemasi ham qaraladi: -(m-1), -(m-2),..., -2, -1, 0. m modul bo’yicha absolyut qiymati jihatidan eng kichik chegirmalarning to’la sinfi ham ishlatiladi. Masalan, m = 7 bo’lganda bu sistema -3, -2, -1, 0, 1, 2, 3 chegirmalardan iborat bo’ladi; m = 8 bo’lganda esa -3, -2, -1, 0, 1, 2, 3, 4 yoki –4, -3, -2, -1, 0, 1, 2, 3 chegirmalardan tashkil topadi.
Chegirmalarning to’la sistemasidan olingan va m modul bilan o’zaro tub bo’lgan chegirmalar m modul bo’yicha chegirmalarning keltirilgan sistemasi deyiladi. Kelitirilgan sistemada chegirmalar soni φ(m)- Eyler funksiyasining qiymatiga teng.
Chegirmalarning to’la sistemasidagi kabi keltirilgan sistemaning ham uch turi ishlatiladi: eng kichik musbat chegirmalarning keltirilgan sistemasi, absolyut qiymati bo’yicha eng kichik manfiy chegirmalarning keltirilgan sistemasi va absolyut qiymati bo’yicha eng kichik chegirmalarning keltirilgan sistemasi.
x₁, x₂,..., x_s butun sonlar sistemasi s = m va i  j da x_i  x_j (mod m) bo’lganda va faqat shu holda m modul bo’yicha chegirmalarning to’la sistemasidan iborat bo’ladi. (a, m) = 1 bo’lganda ax + b chiziqli formaning qiymatlari m modul bo’yicha chegirmalarning to’la sistemasidan iborat bo’lishi uchun x qabul qiladigan qiymatlar ham chegirmalarning to’la sistemasidan iborat bo’lishi zarur va yetarlidir.
x₁, x₂,..., x_s butun sonlar sistemasi s = (m) va i  j, (x_i, m) = 1 da x_i  x_j (mod m) bo’lganda va faqat shu holda m modul bo’yicha chegirmalarning keltirilgan sistemasidan iborat bo’ladi. (a, m) = 1 bo’lganda ax chiziqli formaning qiymatlari m modul bo’yicha chegirmalarning keltirilgan sistemasidan iborat bo’lishi uchun x qabul qiladigan qiymatlar ham chegirmalarning keltirilgan sistemasidan iborat bo’lishi zarur va yetarlidir.
m > 1 va (a, m) = 1 bo’lganda quyidagi taqqoslama o’rinli:
a^(m)  1 (mod m),
bu yerda (m) –Eyler funksiyasi (Eyler teoremasi).
p tub son va (a, p) = 1 bo’lganda quyidagi taqqoslama o’rinli:
a^p-1  1 (mod p) (Ferma teoremasi).
a butun sonni o’zida saqlaydigan m bo’yicha chegirmalar sinfini a mod m bilan belgilaymiz. Demak,
a mod m = a + mZ = {a + km  k  Z}.