Oddiy oqim. Raqamlar nazariyasi. • "Shkolkovo", 2020-2021 o‘quv yili

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
Izoh. Ushbu xususiyatga qaramay, agar siz ikkita raqamni modul bo'yicha solishtirish
mumkinligini tekshirmoqchi bo'lsangiz, har birining qolgan qismini topishga urinishdan ko'ra,
ularning farqini hisobga olish qulayroqdir.
Taqqoslash xususiyatlari.
1. a ÿ b (mod m) ÿ a va b raqamlari bir xil qoldiq moduli m ni beradi.
Agar b = 4 ga bo'linganda a = 26 ning qoldig'ini topmoqchi bo'lsak, u holda b = 4 ga
bo'linadigan a dan kichik bo'lgan eng yaqin son 24 = 4 6 ga teng, demak 26 = 4 6 + 2, qolgan
qismi esa bo'ladi. 2 = 26 ÿ 24.
2. a ÿ b (mod m), c ÿ d (mod m) ÿ a + c ÿ b + d (mod m). Isbot. a
ÿ b (mod m), c ÿ d (mod m) bo'lgani uchun aÿb m ga bo'linadi va cÿd m ga bo'linadi. Demak,
ularning yig'indisi (a - b) + (c - d) = (a + c) - (b + d) ham m ga bo'linadi, ya'ni a + c ÿ b + d (mod
m)
Salbiy a uchun ham xuddi shunday ishlaydi. Agar a = -5, b = 3 bo'lsa, u holda 3 ga bo'linadigan
a dan katta bo'lmagan eng yaqin son -6 (-3 emas, chunki biz a dan katta bo'lmagan sonni
qidiramiz), ya'ni -5 = (ÿ3) 2 + 1, shuning uchun -5 3 ga bo'linganda 1 qoldig'iga ega.
Ta'rif. Agar a = bk + r, 0 r < b va k ÿ Z bo'lsa, a soni r qoldig'i bilan b natural soniga bo'linadi.
b ga bo'linganda a sonining qolgan qismini topish uchun b ga bo'linuvchidan oshmaydigan eng
yaqin sondan ayirish kerak.
3. a ÿ b (mod m), c ÿ d (mod m) ÿ a - c ÿ b - d (mod m). Isbot.
Xuddi shunday, a ÿ b (mod m), c ÿ d (mod m) bo'lgani uchun a - b m ga bo'linadi va c - d m
ga bo'linadi. Demak, ularning farqi (a ÿ b) ÿ (c ÿ d) = (a ÿ c) ÿ (b ÿ d) m ga bo‘linadi, ya’ni a ÿ c
ÿ b ÿ d (mod m) ga bo‘linadi.
Ta'rif. Ayirmasi m ga bo‘linadigan butun sonlar m ga mos modul deyiladi. Yozing: a ÿ b
(mod m).
Masalan:
4. a ÿ b (mod m) ÿ ka ÿ kb (mod m).
Masalan: 11
ÿ 6 (mod 5), chunki 11 - 6 = 5 2 ÿ 5
(mod 3), 2 - 5 = -3 7 ÿ 17 (mod 5),
chunki 7 - 17 = -10 - 4 ÿ 2 (mod 3) -4 -
2 = -6 dan beri
Modullarni taqqoslash
Machine Translated by Google

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
(mod 1004); 1003 ÿ -1 (mod 1004). Bu taqqoslashlarni 4-xususiyatga ko'paytiramiz 1000 1001 1002 1003 ÿ
(ÿ4) (ÿ3) (ÿ2) (ÿ1) = 24 (mod 1004) yoki 1000 1001 1002 1003ÿ ÿ 24 ga boÿlinadi 104
. m (ifoda x . m va ka ÿ
kb (mod m).
kk ÿ b
Masalan, ushbu masalaning (a) bandida 1000 ÿ 1 (mod 999); 1001 ÿ 2 (mod 999); 1002 ÿ 3
.
(mod m) har qanday tabiiy k uchun.
.
Keling, tasdiqlangan xususiyatlardan foydalangan holda bir nechta muammolarni hal qilaylik.
(mod 999); 1003 ÿ 4 (mod 999). Bu taqqoslashlarni 4-xususiyatga ko'paytiramiz 1000 1001 1002 1003
ÿ 1 2 3 4 = 24 (mod 999) yoki 1000 1001 1002 1003 - 24 999 ga bo'linadi
5. a ÿ b (mod m), c ÿ d (mod m) ÿ ac ÿ bd (mod m). Isbot. Oldingi
xususiyatdan foydalanamiz. Chunki a ÿ b (mod m), keyin ac ÿ bc (mod m) va c ÿ d (mod m) dan keyin bc ÿ
bd (mod m). Demak, ac va bc lar m ga bo‘linganda bir xil, bc va bd esa m ga bo‘linganda bir xil qoldiqga ega
bo‘ladi, shuning uchun ac va bd m ga bo‘linganda bir xil qoldiqga ega bo‘ladi, demak ac ÿ bd (mod m).
1. 1000 1001 1002 1003 ÿ 24 soni (a) 999 ga bo‘linishini isbotlang; (b) 1004 da.
Isbot.
Modullarni
taqqoslash bizga ifodalardagi raqamlarni almashtirish imkonini beradi.
Isbot. Chunki a ÿ b (mod m), keyin a - b .
6. a ÿ b (mod m) ÿ a Isbot. a
= c va b = d uchun oxirgi xossani qo'llasak, (mod m) ni olamiz. k = 2 uchun isbotlangan. Endi biz oxirgi
xususiyatni (mod m) yana qo'llaymiz. Shunday qilib, siz xohlaganingizcha qila olasiz
.
2 2 3 3 va c = a uchun b = d ÿ b va har
qanday natural k uchun k (mod m) ni
olamiz . ÿb
asl raqamlar bilan taqqoslanadigan boshqa, qulayroq raqamlarga o'zgartiring.
bu x y ga bo'linadi), shuning uchun ka - kb = k(a - b) .
k marta, shuning uchun a
. y degani
2 nima a
Ushbu masalaning (b) bandida 1000 ÿ -4 (mod 1004); 1001 ÿ ÿ3 (mod 1004); 1002 ÿ ÿ2
.
2 ÿ b
Machine Translated by Google

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
(c) Birinchi ikkita xatboshidagidek oddiy bu erda ishlamaydi. Birinchidan, 13 raqamini
4 (13555 ÿ 4 (mod 9)) bilan almashtiring va 9 ga bo‘linganda qoldiqlar 4 ning kuchini qanday berishini ko‘ring. 1 ÿ
4 (mod 9) 4 ÿ 16 ÿ 7 (mod 9) ÿ 7 4 ÿ
28 ÿ 1 (mod 9)
2. Bo'limning qolgan qismini toping: 7 ga;
(c) 13555 ga 9. (a) 4
Isbot.
(a) 4 ÿ 1 (mod 3). Oxirgi xususiyatga ko'ra ÿ 1 ga ko'tarilishi mumkin (mod 3)
185 daraja va 4 ni oling
Izoh. Bundan tashqari, qoldiqlar tsikli, chunki qaysi qoldiq darajani beradi, faqat qolgan oldingi darajani nima
berishiga bog'liq (agar 4 ÿ r (mod 9), keyin 4 ÿ 4r (mod 9)). Bu erda 9 ga bo'linganda 4 ning vakolatlarining
qoldiqlari 4-7-1-4-7-1-... ekanligini aytish mumkin va bu seriyadagi 555 ta qoldiq 1 bo'lishini tushunish mumkin. ÿ
1 (mod 9) ) va 555 = 3 185, shuning uchun biz taqqoslashni ko'taramiz Endi bilamizki, 4
ham beradi
Isbot. Shartni moduli m mos kelishiklar shaklida qayta yozamiz. Berilgan: a ÿ 2b (mod m); c ÿ
3d
(mod m) Biz isbotlashimiz kerak: ac ÿ 6bd
(mod m), lekin bu
bizga berilgan ikkita taqqoslashning mahsulotidir.
m ga bo'linadi.
4
2 4
(b) 6 ÿ -1 (mod 7). Oxirgi xususiyat kuchga ko'tarilishi mumkin, shuning uchun 2017 ÿ (ÿ1) 2017 = ÿ1 (mod 7).
Lekin -1 qoldiq emas, chunki u 0 dan kichik, lekin -1 6 7 ga bo'linganda 6 ning qoldig'ini beradi (chunki -1 = 7 1
+ 6), shuning uchun 6 7 ga bo'linganda 6 ning qoldig'idir. .
ÿ 1 (9ga qarshi).
3 da; (b) 6
Izoh. Bu erda 4 ni 3-chi kuchga ko'tarish kerak emas, oldingi taqqoslash etarli
3 4
3. Ma’lumki, aÿ2b m ga, cÿ3d esa m ga bo‘linadi. acÿ6bd ekanligini isbotlang
daraja, shuning uchun 4
4 ga ko'paytiring. ÿ 1 4 ÿ 4
(mod 9)
4
555
2017 yil
2017 yil
kÿ1
k
555
2018
3
2018
Machine Translated by Google

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
(Barmoqlarda: biz har bir sumkadan bitta raqamni oldik va biz olgan raqamlar to'plami - bu PSV)
1. PSV + a = PSV
bu raqamlar modul m turli qoldiqlarni berishi kerak
PSV xususiyatlari.
Isbot. Aksincha. PSV = (x1, x2, ..., xm) va (x1 + a, x2 + a, ..., xm + a) PSV emas. Keyin, ikkinchi ta'rifga ko'ra,
bir xil qoldiqlarga ega bo'lgan ikkita xi + a va xj + a soni bo'lishi kerak (aks holda bu PSV bo'lar edi), lekin keyin xi
va xj bir xil qoldiqlarga ega va bu bo'lishi mumkin emas.
Izoh. a ning m ga bo‘linmaslik sharti yetarli emas, chunki bu holda (xiÿxj )a ning m ga bo‘linishi xiÿxj ning m ga
bo‘linishini bildirmaydi , chunki a va m umumiy bo‘luvchiga ega bo‘lishi mumkin. 1 dan katta.
Ta'rif. To'liq qoldiq tizimi (RRS) moduli m - m moduli turli qoldiqlarni beradigan m sonlar to'plami. Bunday
holda, bunday to'plamda modul bo'yicha barcha mumkin bo'lgan qoldiqlar bo'lishi aniq, shuning uchun ikkala ta'rif
ham
Barcha tamsayÿlar to'plamini ko'rib chiqing .., -2, -1, 0, 1, 2, ... va ularni 0, 1, ..., m - 1 raqamlari bilan
"sumkalar" ga bo'ling, bu erda sumkada k soni bilan k moduli m (m ga bo'linganda qoldig'i k ga teng bo'lganlar)
bilan taqqoslanadigan raqamlarni beradi. Endi bitta sumkadagi barcha raqamlarni teng ravishda qabul qilish
mumkin.
2. a PSV = PSV, agar gcd(a, m) = 1. (gcd(a, b) ni (a, b) shaklida yozamiz) Isbot. Aksincha. PSV = (x1, x2, ...,
xm) va (ax1, ax2, ..., axm) PSV emas. Keyin, ikkinchi ta'rifga ko'ra, qoldiqlari bir xil bo'lgan ikkita axi va axj
soni bo'lishi kerak (aks holda bu PSV bo'lar edi), keyin o'q - axj = a(xi - xj ) m ga bo'linadi va (a, m) ) = 1 boÿlsa,
xi ÿ xj m ga boÿlinadi, lekin xi va xj ni bera olmaydi.
kuchli.
Ta'rif. To'liq qoldiq tizimi (RRS) moduli m - barcha mumkin bo'lgan qoldiqlarni modul m beradigan m sonlar
to'plami. Faqat m qoldiq bo'lgani uchun hammasi
bir xil qoldiqlar.
Chegirmalarning to'liq tizimi
Machine Translated by Google

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
Chegirmalarning qisqartirilgan tizimi
pÿ1
Fermaning kichik teoremasi. Har qanday asosiy p va p bilan ko‘paytirish uchun a ÿ 1 (mod p)
Keling, raqamlar to'plami haqida bilishingiz kerak bo'lgan bir nechta xususiyatlarni tuzamiz,
ÿ 1 (mod p)
Birinchi xususiyat, shubhasiz, qanoatlantiriladi, shuningdek, ikkinchisi (a, m = p) = = 1. Uchinchi
xususiyat qoniqtirilmasin. U holda qoldiqlari bir xil bo'lgan ikkita axi va axj sonlari bo'lishi kerak , u
holda axi ÿ axj = a(xi ÿ xj ) m ga bo'linadi va (a, m) = 1 bo'lgani uchun xi ÿ xj m ga bo'linadi, lekin xi va
xj bir xil qoldiqni bera olmaydi. Shunday qilib, barcha uchta xususiyat qoniqtiriladi.
Keling, ushbu xususiyatlar to'plamidan foydalangan holda PrSV ekanligini tekshirib ko'ramiz.
Keling, tushunaylik, agar biz PRSP ni (a, m = p) = 1 ga ko'paytirsak, biz PRSPni olamiz.
yoki a
faqat moduli m bilan mos keladigan sonlarni olsak, olinadigan sonlardan. (ya'ni, biz faqat m uchun
nisbatan asosiy bo'lgan sumkalarni olamiz)
Isbot. Ikki xil PRS moduli p ni olaylik va har biridagi barcha sonlarni ko'paytiramiz. Qoldiqlar
to'plami bir xil bo'lganligi sababli, hosil bo'lgan mahsulotlar p moduliga mos keladi.
Ta'rif. Qisqartirilgan qoldiq tizimi (RRS) moduli m to'plamidir
pÿ1
to‘g‘ri, a
PRVdan chiqib ketadi.
Agar unga a qo'shilsa, PrSV bilan nima sodir bo'lishini tushunmoqchiman.
Afsuski, PrV + a deyarli hech qachon PrV emas, masalan, agar p = 5 bo'lsa va PrV = [1, 2, 3, 4] ga 2
qo'shsangiz, siz [3, 4, 5, 6] ni olasiz, keyin 5 emas. 5 bilan tenglashtiring.
o'ng tomonda yozilgan - bu PrSV) va har biridagi barcha raqamlarni ko'paytiring.
Keyin ikkita shunday PSVni ko'rib chiqamiz: [1, 2, ..., p - 1] va [a, 2a, ..., (p - 1)a] (bu
Keling, m = p tub bo'lgan holatdan boshlaylik. Keyin p ga bo'linadigan sumka
Bu ERP ekanligini da'vo qilish uchun: 1)
p - 1 raqamlari
2) Barcha raqamlar p ga ko'paytiriladi.
3) To'plamdagi raqamlar har xil qoldiqlarni yoki barcha mumkin bo'lgan umumiy qoldiqlarni beradi.
Shubhasiz, agar barcha qoldiqlar boshqacha bo'lsa, ular barcha mumkin bo'lgan qoldiqlarni beradi va aksincha.
Biz 1 2 .... (pÿ1) ÿ a 2a .... (pÿ1)a (mod p) yoki (pÿ1) ni olamiz! ÿ (pÿ1)!a pÿ1 (mod pÿ1 (pÿ1)!ÿ(pÿ1)!
= (a pÿ1ÿ1)(pÿ1)! p). Endi buni farq sifatida
qayta yozamiz, ya'ni p-1 - 1 p ga bo'linadi, p ga bo'linadi.
gcd((p - 1)!, p) = 1 ekan, bundan a
Machine Translated by Google

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
Eyler teoremasi. Har qanday m soni uchun va m soni a, s(m) ÿ 1 (mod m) bilan
birlashing, bu a
ERP ekanligini da'vo qilish uchun raqamlar: 1)
raqamlar s (m)
2) Barcha raqamlar m ga ko'paytiriladi.
3) To'plamdagi raqamlar har xil qoldiqlarni yoki barcha mumkin bo'lgan umumiy qoldiqlarni beradi.
Shubhasiz, agar barcha qoldiqlar boshqacha bo'lsa, ular barcha mumkin bo'lgan qoldiqlarni beradi va aksincha.
Keling, to'plam haqida bilishingiz kerak bo'lgan bir nechta xususiyatlarni yana tuzamiz
Birinchi nuqtadan boshlaylik. Keling, qandaydir naqsh topishga harakat qilaylik.
Keling, ushbu xususiyatlar to'plamidan foydalangan holda PrSV ekanligini tekshirib ko'ramiz. Keling
m = 5 uchun qoldiqlar [1, 2, 3, 4] mavjud. m = 6 uchun qoldiqlar mavjud [1, 5]. m = 10 uchun
qoldiqlar mavjud [1, 3, 7, 9]. PrSV dagi elementlar soni nimaga teng ekanligi aniq emas,
shuning uchun Eyler funksiyasini kiritamiz.
Savol tug'iladi: m kompozitsion haqida ham shunday deyish mumkinmi? Ma'lum
bo'lishicha, unday emas, chunki (m - 1)! kamaytirish mumkin emas, chunki m va (m - 1)!
o'zaro asosiy emas. Kompozit son m uchun shunga o'xshash narsani olish uchun biz PrV
ni ko'paytiramiz, lekin endi bizga, birinchidan, qandaydir tarzda ushbu to'plamdagi
elementlar sonini hisoblash kerak, ikkinchidan, yana PrVV ni ko'paytirish mumkinligini tekshiring.
Agar biz PrSVni (a, m) = 1 ga ko'paytirsak, PrSV ni olishimizni tushunamiz.
Ta'rif. Eyler funksiyasining qiymati s(m) natural soniga teng
Isbot. Ikki xil PRS moduli m ni olaylik va har biridagi barcha sonlarni ko'paytiramiz.
Qoldiqlar to'plami bir xil bo'lganligi sababli, hosil bo'lgan mahsulotlar m moduliga mos
keladi.
m ga teng.
Birinchi ikkita xususiyat (a, m) = 1 bo'lganligi sababli qanoatlantirilishi aniq. Uchinchi
xususiyat qoniqtirilmasin. U holda qoldiqlari bir xil bo'lgan ikkita axi va axj sonlari bo'lishi
kerak , u holda axi ÿ axj = a(xi ÿ xj ) m ga bo'linadi va (a, m) = 1 bo'lgani uchun xi ÿ xj m ga
bo'linadi, lekin xi va xj bir xil qoldiqni bera olmaydi. Shunday qilib, barcha uchta xususiyat
qoniqtiriladi.
m dan oshmaydigan raqamlar va m ga ko'paytiriladi, yoki PSVdagi raqamlar soni bir xil
bo'ladi.
Eyler teoremasi
Machine Translated by Google

---

2
2
s(m)
k
2018
2018
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
ÿ 1 (mod m).
Keling, a = b, ya'ni a - 1 = (a - 1)(a + 1) p ga bo'linishi mumkinmi, deb o'ylab
ko'raylik. Demak, a - 1 yoki shunday bo'lsa, aa + 1 p ga bo'linadi,
chunki p tubdir. Keyin a ÿ 1
yoki a ÿ -1 ÿ p - 1 (mod m). (Bu erda p ning tub bo'lishi muhim, chunki agar p 8 ga teng bo'lsa, a 5 ga
teng bo'lishi mumkin)
Keyin biz ikkita shunday PrSV ni ko'rib chiqamiz: [x1, x2, ..., xs(m) ] (bu har qanday PSV moduli m)
va [ax1, ax2, ..., axw(m) ] (Yozuvda nima yozilgan) o'ng - a· PrSV) va har biridagi barcha sonlarni
ko'paytiring. Biz buni olamiz: axÿ(m) (mod
m) yoki xÿ(m) ÿ ax1 ax2
ÿ(m) (mod m). x1x2...
xph ( m) ÿ
x1x2 ... xÿ (m) a (a ÿ(m) ÿ
1)x1x2...xÿ(m) m ga bo‘linadi. s(m) ÿ 1 m yoki ga bo‘linadi
a
Misol: p = 7
Isbot. Keling, ikkita shunday RPni ko'rib chiqaylik: [1, 2, ..., p-1] va [a, 2a, ..., (p-1)a]. Shunday qiziq
faktni qayd qilaylikki, ikkinchi PCSda p ga bo'linganda 1 ning qoldig'ini beradigan aniq bitta raqam
mavjud, ya'ni ab ÿ 1 (mod m) bo'ladigan aniq bitta b qoldiq mavjud. Qolgan b ga a ning teskarisi deyiladi.
1 1 ÿ 1; 2 4 ÿ 1; 3 5 ÿ 1; 6 6 ÿ 1; Shuning uchun 6! ÿ 1 6 (2 4) (3 5) ÿ ÿ1
chap tomonda bir nechta raqamni belgilashingiz mumkin, shunda
(p - 1)! ÿ ÿ1 (mod p)
....
....
Endi Eyler teoremasi bo‘yicha ba’zi masalalarni yechamiz.
Yechim. Biz chapga bir nechta raqamlarni qo'shmoqchimiz va 2 ni olamiz
Izoh. Masalalarda nafaqat Uilson teoremasidan, balki har bir qoldiq moduli p ning teskari bo‘lishidan
ham foydalaniladi.
x1 x2 _ _
. Kerak
uni qandaydir tarzda qoldiqlar va taqqoslashlar tiliga tarjima qiling. 2 raqamini kiriting
2. 2 soni yana ikkining darajasi
ekanligini isbotlang.
(p - 1)! ÿ 1 · (p - 1) · (a1b1) ·
Endi biz 1 va pÿ1 dan tashqari barcha qoldiqlarni (a, b) juftlarga ajratamiz, shunday qilib ab ÿ 1
(mod m) va a = b.
....
ÿ p - 1 ÿ -1 (mod m), chunki har bir juftlikda
Vilson teoremasi. p qandaydir tub son bo'lsin. Buni isbotlang
mahsulot 1 ga teng.
Machine Translated by Google

---

n
.
narsa k bu 2
Ko'rinib turibdiki, s(i) har doim kamida 1 bo'ladi, chunki har qanday i soni uchun i dan oshmaydigan
va i ga o'zaro tub bo'lgan 1 bo'ladi va s(i) har doim eng ko'p i bo'ladi, chunki ta'rifiga ko'ra s(i) ) 1 dan i
gacha bo‘lgan natural sonlar va i ga nisbatan tub sonlarga teng. Demak, barcha g'alati i uchun j mavjud
< 102018, shuning uchun
.
2 ÿ(i) ÿ 1 (mod i), shuning uchun agar 1 ÿ(i) 1000 bo'lsa, j = ž(i) bizga mos keladi.
Yechim. Boshlash uchun shuni ta'kidlaymizki, raqamlar yig'indisi n ga teng bo'lgan raqamning o'ng
tomoniga istalgan nol sonini qo'shishimiz mumkin va raqamlar yig'indisi o'zgarmaydi. Shuning uchun,
agar n = 2a5 bk bo'lsa, bu erda gcd(k, 10) = 1, u holda n ga bo'linadigan kerakli sonni topish uchun k
ga bo'linadigan sonni topish kifoya.
n ta raqam. Keyin y 2 soni 2 k 2 bo'lishi
uchun
n ga bo'linadigan n ga teng.
2 ga bo'linadi
k 2
ÿ 2 ÿ(5n)
.
5. Har qanday natural n soni uchun raqamlar yig‘indisi bo‘lgan son mavjudligini isbotlang,
.
Keling, 2019 yil raqamlari bo'lgan birinchi raqam 102018 ekanligini
tushunaylik, lekin 2 mu n 2018, bu bizga 2 ni beradi
i 1000, j raqami bor, 1 j 1000,
n ). Bu shuni anglatadiki, biz 2018+s(5n ) ni k, keyin esa 2 ni olishimiz mumkin
= 22018(2kÿ2018ÿ1 ). . .2 n5 n . Avval chapdagi ifoda har doim 2 ga bo'linishini
isbotlaymiz
va 2 ta oxirgi n ta raqam bir xil bo'lsa, oxirgi n ta raqam
nolga teng bo'lishi yoki 10n ga bo'linishi kerak . Shunday qilib, bizning
masalamiz quyidagi masalaga aylandi: 2 soni o'nli kasr tizimida n ta raqamga ega bo'lsin.
Biri borligini isbotlang (mod 10n ).
Ushbu yechim ortidagi ikkinchi g'oya raqamlar yig'indisi 1 va qolgan 1 mod k bo'lgan KO'P sonlarni
topishdir. Agar biz n ta shunday sonni topib, ularni qo'shsak, raqamlar yig'indisi qo'shiladi (umid qilamiz)
va natijada olingan son n modul k va n k ga teng bo'ladi.
.
ÿ 1 (mod5n ) .
Endi 2 n ) =
1 bo'lgan k ni topish qolganligi sababli ,
Eyler teoremasi bo'yicha 2 s(5n) gcd(2, 5 ÿ 1 (mod ÿ 1 (mod p) 5 ekanligini
eslashimiz mumkin.
.
Yechim. Shubhasiz, hatto i uchun 2 j - 1 soni i ga to'liq bo'linmaydi. Demak, i soni mutlaqo toq,
gcd(i, 2) = 1, ya’ni Eyler teoremasi qo‘llanilishi mumkin.
4. i ning nechta qiymati uchun, bu erda 1 2 j -
1 i ga bo'linadigan bo'ladi?
.
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
2018
2018
2018
- 2
n
2018
ÿ 2
k
2018
2018
- 2
kÿ2018
ÿ1 . 5
kÿ2018
k
k 2018 ÿ 2
n
2018
kÿ2018
yoki 2
Machine Translated by Google

---

2..
2
2
2
2 ..
ÿ2 ..
2 ..
2
t
t
Izoh. Ko'rsatkich har doim yuqoridan pastgacha boradi, ya'ni 2
Ushbu raqamlardan biri sifatida biz 10ÿ(k) ni olishimiz mumkin (Eyler teoremasiga ko'ra, 10p(k) ÿ 1 (mod k))
va bu erda taqqoslashlarni bir darajaga, ya'ni 10a s ga oshirish mumkinligini eslash vaqti keldi. (k) ÿ 1 (mod k),
shuning uchun 10a s(k) ko‘rinishdagi istalgan raqam bajariladi . Ustunga bunday n sonni qo'shganda, bu
raqamlar har xil raqamlarda birlarga ega bo'lishi sababli, siz n raqamlari yig'indisi va k ga bo'linadigan raqam
olasiz. Bunga faqat o'ngdagi ko'p (max(a, b)) nollarni qo'shish va raqamlar yig'indisi bo'lgan raqamni olish kifoya.
6. . 2 ning 1 dan n gacha
bo‘lgan barcha sonlarga bo‘linishini isbotlang.
Biz allaqachon bazani isbotladik, bu o'tishni isbotlash uchun qoladi.
= 22
= 22 ..
2 .. ÿ 2
(Induktsiya g'oyasi shundan iboratki, biz ikkita faktni isbotlaymiz: agar ba'zi n soni uchun bizning shartimiz
to'g'ri bo'lsa, u n + 1 uchun ham to'g'ri bo'ladi (yechimning bu qismi "o'tish" deb ataladi) va bizning shartimiz ba'zi
bir minimal n soni uchun to'g'ri bo'ladi, bizda 2 uchun (yechimning bu qismi "asosiy" deb ataladi) Bu ikki faktni
bilib, aytishimiz mumkinki, n = 2 uchun bu to'g'ri, u holda n + 1 = uchun. 3 (1 fakt bo'yicha) va 3 uchun bir marta,
keyin 4 uchun va hokazo.
x (bu aniq, chunki 2 ning kuchi 2 ga bo'linadi
= 216
ÿ 1
n va n ga bo'linadigan.
(22 .. ÿ 1), qavs ichidagi 2 ning kuchi (uni t deb ataymiz) oldingi induksiya bosqichidagi
raqam, ya’ni t 1 dan n ÿ 1 gacha bo‘lgan sonlarga bo‘linadi va bizga (2t ÿ 1) kerak bo‘ladi. 1 dan n gacha bo'lgan
barcha sonlarga bo'linadi . 1 dan n gacha bo'lgan ba'zi bir k sonni olaylik va k
ni 2 xm sifatida ifodalaymiz , bu erda m toq. Endi biz buni isbotlashimiz kerak 2
> nx) va 2
Ikkinchi qism to‘g‘ri, chunki m = 1 bo‘lsa, s(m) < m (m = 1 holatda o ÿ 1 tasdiqi m ga bo‘linishi aniq), chunki
s(m) da biz 2 bo‘ladigan sonlarni ko‘rib chiqamiz. m dan oshmaydi va ko‘paytiriladi va m = 1
bo‘lgani
uchun m m ga ko‘paytma bo‘lmaydi, ya’ni s(m) m dan kamida 1 ga kichik.Demak, s(m) < n va t s ga bo‘linadi. (m),
(birinchi hadda n ta ikkita, ikkinchisida n - 1 ta)
Ko'rinib turibdiki, 2
iborani ko'rib chiqish har ikkala kuchda ham bir ikkilik ko'proq va isbotda bo'ladi
Endi buni isbotlang 2
Yechim. Biz induksiya bilan isbotlaymiz. Avval n = 2 borligini tekshirib ko‘raylik. ÿ 2 1 ga ham, 2 ga ham
bo‘linishi mumkin, keyin quyidagi amallarni bajaramiz:
m ga bo'linadi.
2 .. 2
Kichikroq ikkitalik uchun biz hamma narsani isbotladik, deb taxmin qilish o'rinli.
Izoh. 1 dan n gacha bo'lgan barcha sonlarga bo'linadi va n ga bo'linadi! - bu umuman bir xil narsa emas.
Misol uchun, n = 6 ni olaylik: 60 soni 1 dan 6 gacha bo'lgan barcha sonlarga bo'linadi, lekin 6 ga bo'linmaydi! =
720
2
2
2 .. ÿ 2
2
2
2
2
2
2
4
2
2
2
2 2 2 ..
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
Machine Translated by Google

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
t
shuning uchun 2
ÿ 1 m ga bo‘linardi.
Machine Translated by Google

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
mn juft bo‘lib o‘zaro
Agar bu yerda barcha qoldiqlar moduli har xil ekanligini isbotlasak, ular orasida y moduli
b qoldiqli son albatta bo'ladi, ya'ni bizning raqamlar to'plamimiz PSV moduli b (b raqamlar
to'plami) ekanligini isbotlamoqchimiz. turli qoldiqli modul b) modul b).
biz a.
Xitoy qoldiqlari teoremasi Ikki koÿp modulli a va b boÿlsin
oddiy. Keyin a1, a2, har qanday butun sonlar uchun . . . , an butun i uchun x ÿ ai (mod mi)
bo'ladigan butun x bor . Bundan tashqari, x bir nechta M = m1m2 ... mn qo'shilishiga qadar
yagona aniqlanadi .
Buning sababi shundaki, x, a + x, 2a + x, ..., (b - 1)a + x to'plamini PSV b - 1 dan olish
mumkin, agar biz avval a ga ko'paytirsak (buni bajarish mumkin, chunki gcd( a, b)
= 0, 1,
2, ..., 1) va keyin har biriga x qo'shing.
(gcd(a, b) = 1) va ikkita qoldiq x va y mavjud. Keyin N ÿ x (mod a) bo'lgan N son
mavjud; N ÿ y
(mod b).
Bungacha biz faqat bitta modul ustida ishlaganmiz. Agar raqamni bir vaqtning o'zida bir
nechta modulda ko'rib chiqsak, nima bo'lishi qiziq. Misol uchun, agar biz sonning 2 moduli
3 ga mos kelishini bilsak, u holda 7 moduli haqida biror narsa aytishimiz mumkinmi? Ma'lum
bo'lishicha, yo'q, bu raqam istalgan modul qoldig'ini berishi mumkin. Xitoy qoldiq teoremasi
aynan shunday deydi.
Agar bizda ham N ÿ z (mod c) va gcd(a, c) = gcd(b, c) = 1 sharti mavjud bo‘lsa-chi?
Keling, avval isbotlangan teorema bo'yicha H ni topamizki, H ÿ x (mod a); H ÿ y (mod b).
Chunki gcd(a, c) = gcd(b, c) = 1, keyin gcd(ab, c) = 1, shuning uchun yana CRT dan
foydalanamiz va shunday N ÿ H (mod ab) va N ÿ z (mod) sonni topamiz. c). U holda N - H
ham a, ham b ga bo'linadi va N ÿ H ÿ x (mod a); N ÿ H ÿ y
(mod b), N ÿ z (mod
c), ya’ni biz yana mos
N ni topdik.
Keling, CTO ni umumiy shaklda tuzamiz.
Isbot. Qabul qilinganda x ning qolgan qismini beradigan b raqamlarini ko'rib chiqaylik
,
Biz uni birinchi navbatda ikkita raqam uchun shakllantiramiz
Xitoy qoldiq teoremasi m1, m2, raqamlari bo'lsin . . .
x, a + x, 2a + x, ...,(b - 1)a + x
JSSV
Machine Translated by Google

---

Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
p-qiymatiga erishiladi. Yechim.
Shartni N = 101 k + m va N = mt + p deb yozamiz. Biz bilamizki, m 101 ga bo'linganda qoldiq, shuning
uchun m 100, p 99 ga o'xshaydi. Endi biz p = 99 va m = 100 uchun N bor yoki yo'qligini tekshirishimiz kerak,
shundayki:
aynan 1 marta sodir bo'ladi.
Bizda faqat m1m2 ... mn to'plamlari borligi va ularning barchasi har xil bo'lgani uchun, har bir qoldiq to'plami
Mavjud bo'lishi mumkin bo'lgan turli xil qoldiqlar to'plamining maksimal soni qancha? a1 uchun bizda bor
Isbot. 1 dan m1m2...mn gacha bo'lgan har bir songa mn (a1, a2, ..., a) to'plamini belgilaymiz .
Keling, CTO bo'yicha bir nechta muammolarni hal qilaylik
m1 variantlari, a2 uchun bizda m2 variantlari va hokazo, ya'ni jami m1m2...mn qoldiqlar mavjud.
m1, m2, modullar ustidagi qoldiqlar . . .
3. 3 ga bo‘linganda 2 ga, 4 ga bo‘linganda 3 ga, 5 ga bo‘linganda 4 ga, 6 ga bo‘linganda 5 ga, 7 ga
bo‘linganda qolgan 6 ni beradigan eng kichik natural sonni toping. Bizga berilgan: x ÿ 2 (mod 3); x ÿ 3 (mod 4);
x ÿ 4 (mod 5); x ÿ 5 (mod 6); x ÿ 5
(mod 7) Buni x ÿ ÿ1 (mod
3) sifatida qayta
yozish mumkin; x
ÿ ÿ1 (mod 4); x ÿ
ÿ1 (mod 5); x ÿ ÿ1
(mod 6); x ÿ ÿ1
(mod 7) Keyin x+ 1 3, 4, 5, 6, 7 ga
bo‘linadi va ularning
LCM(3, 4, 5, 6, 7) =
420. U holda minimal
mos keladigan x 419
ga teng.
Ikki sonda bir xil qoldiqlar to'plami bo'lishi mumkinmi? X va Y bir xil qoldiqlar to'plamiga ega bo'lsin. U holda
har qanday i uchun X ÿ Y mi ga boÿlinadi , yaÿni X ÿ Y m1m2...mn ga boÿlinadi, chunki sonlar juft juft tub
sonlar, lekin X va Y 1 dan m1m2...mn gacha. Qarama-qarshilik, ya'ni barcha to'plamlar boshqacha.
N ÿ 100 (mod 101) va N ÿ 99 (mod 100)
,
4. Dimaga N natural soni berildi. U uni 101 ga bo'ldi va qolgan m > 0 ni oldi. Keyin Dima N ni m ga bo'ldi va
qolgan p ni oldi. Olingan p ning eng katta qiymatini toping va keyin bu uchun eng kichik N ni toping
,
Machine Translated by Google

---

2 ,
2
2
2
1
2
2
2
3
N
p 1 da
2 , CRT ga ko'ra, x shunday bo'ladi: x ÿ -1
(mod p
Agar bizga bunday minimal N ni topish kerak bo'lmasa, unda KTOga ko'ra bunday N mavjud deb
aytishimiz va shu erda to'xtashimiz mumkin edi. Oldingi masala N ÿ ÿ1 (mod 101) va N ÿ ÿ1 (mod
100) ni bajaramiz. Keyin bu bizga mos keladi
Izoh. Ko'pincha CTO oldingi va keyingi masalada bo'lgani kabi ketma-ket (turli) raqamlar uchun
turli modullarga bo'linganda qoldiqlarni o'rnatish uchun ishlatiladi.
)
a) tub son yoki tub sonning darajasi; (b) natural sonning
darajasi (ikkinchidan kam bo'lmagan).
hisoblanadi
x ÿ ÿ2 (betga qarshi
x ÿ ÿ1000 (mod p1999 p2000)
Keyin x + 1, ...., x + 1000 bajariladi .
Keling, keyingi varaqqa o'tamiz.
...
N \u003d 101 100 - 1 \u003d 10099 va 10100 CRT moduliga ko'ra, bu N yagona, ya'ni javob 10099.
...
Yechim. Raqam hech qanday tub sonning darajasi bo'lmasligi uchun uning kamida 2 ta tub bo'luvchisi
bo'lishi kerak. X ni topish uchun CTO dan foydalanamiz, x ÿ ÿ1 (mod 2 3) x ÿ ÿ2 (mod 5 7)
)
oddiy.
x ÿ ÿN (betga qarshi
2. n + 4 9 ga karrali, n + 9 esa 25 ga karrali 4 ga karrali n butun son bormi? Yechim. Bizdan n ÿ
0 (mod 4) bo'lgan n bor-yo'qligi so'raladi; n ÿ ÿ4 (mod 9); N ÿ -9 (mod 25). JSST ma'lumotlariga
ko'ra, bunday x mavjud, chunki 4, 9, 25 o'zaro juftlikdir.
8. Har birida bo'lmagan 1000 ta ketma-ket son borligini isbotlang
)
7. Agar u natural sonning kvadratiga boÿlinadigan boÿlsa, uni yaxshi deb ataylik > 1. Qaysi N
uchun ketma-ket N ta yaxshi son bor? (N = 3: 48, 49, 50 uchun misol). Javob. Har qanday N yechim
uchun.
Keling, N ta turli juft juft
tub sonlarni (masalan, N tub sonlar) p1, p2, ..., pN olaylik va x + 1 ba'zi x va boshqalar uchun
bo'linishini xohlaymiz. Bunday sonlar mavjud, shuning uchun x + 2 px + 3 ga bo'linadi. p ga bo'linadigan
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
Machine Translated by Google

---

2
2
1 2
2
2
2
x + 2 ÿ p2 (mod p
Ikkinchi xatboshida shuni e'tiborga olingki, agar sonning birinchi bo'linmasida tub bo'luvchi bo'lsa, bu
erda p - tub,
Yechim. Keling, birinchi navbatda seriyani ko'rib chiqaylik
hamma n ta uchun birinchi n sonning yig'indisi n ga bo'linardi.
va keyin A yaxshi
. n, lekin bu seriya bizga mos kelmaydi,
2
)
11. Natural qatorlar sonlarini shunday tartibga solish mumkinligini isbotlang
Shunga qaramay, JSST tomonidan biz shunday x ni
topamiz: x + 1 ÿ p1 (mod p
. .
Keling, qatorimizni shunday qilaylik. Keling, 1, 3, 2
dan boshlaylik. Endi men yana 4 ni qo'ymoqchiman, shunda u yo'qolib qolmasligi va bizning qatorimizda
bo'ladi, lekin u to'rtinchi o'ringa to'g'ri kelmaydi, shuning uchun qatorimizni quyidagicha kengaytiramiz: 1,
3 , 2, x, 4, shuning uchun x + 6 4 ga bo'linadi va x + 10 5 ga bo'linadi. JSST ma'lumotlariga ko'ra, bunday
x (masalan, x = 10) mavjud va ularning cheksiz ko'pi bor (chunki x + 20, x + 40, ... bizga mos keladi).
Endi biz 1, 3, 2, 10, 4, y, 5 qatorlarimizni davom ettiramiz. Biz y + 20 6 ga bo'linishini va y + 25 ni 7 ga
bo'linishini xohlaymiz va CTO bo'yicha bunday raqamlar juda ko'p.
2 4 6 8 10 12 .
daraja, u holda, albatta, daraja emas, ya'ni agar A ÿ p soni (mod p keyin A p ga
bo'linadi va p ga bo'linmaydi.
)
Endi umumiy shaklda shakllantiramiz. Bizda allaqachon x1, x2, ..., xn qatorlari bo'lsin . Biz n + 2 ga
eng kichik foydalanilmagan b sonni qo'shmoqchimiz. U holda JSST tomonidan z ni shunday topishimiz
mumkin: x1 + x2 + ... + xn + z n + 1 ga bo'linadi x1 +
x2 + ... + xn + z + b n + 2 ga bo'linadi Endi x1,
x2 , ..., xn, z, b, qator shartga to‘g‘ri keladi va
foydalanilmagan minimal son endi kattaroqdir, shuning uchun biz uni qatorimizga qo‘shganda har
qanday son uchun moment mavjud.
chunki bu qatorda 1 raqami o'ringa ega bo'lmaydi. Ya'ni, bizning seriyamizda barcha raqamlar bo'lishi
kerakligini unutmaslik kerak.
...
n(n + 1)
Birinchi n ning yig'indisi 2 · = n(n + 1) bo'ladi.
.
Keyin x + 1, ...., x + 1000 qatorlari bajariladi.
x + 1000 ÿ p1000 (mod p 1000)
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
Machine Translated by Google

---

va ÿ a
239
- 1 aniq
239
s(m)
ÿ 1 (mod m) agar (a, m) = 1. a ning m ga bo‘linganida a ning 1 qoldig‘i borligini biz bilamizmi? Aslida, u
mumkin, eng oddiy holat ÿ
1 (mod m = 7), s (m = 7) = 6 bo'lsa-da, keyin a = 1 yoki biroz murakkabroq a = 2 va a s (m) har doim ham emas. minimal daraja. Keyin buni
minimal deb ataymiz
x
239
e'lonlar juft bo'lib qiyoslab bo'lmaydigan modul m
239
d
,
3
Ko'rsatkichlar
minimal daraja ham bor.
d2 ÿ a
eng kichik natural son d shundayki, a inglizcha so'z tartibidan
kelib chiqqan holda deyiladi. Xususiyatlari
d1 3. a
Isbot. Bu ravshan, chunki hech bo'lmaganda a ning 1 ga teng bo'lgan darajasi (a s(m) ÿ 1) mavjud bo'lsa, biz
natural sonlar orasidan qidiramiz, shuning uchun
Biz ko'rsatkichlar uchun bir nechta muammolarni hal qilamiz
.
1. Ko'rsatkich mavjud.
= a
Isbot. m modulining qolgan quvvatlarini ko'rib chiqing. Biz allaqachon bilamizki, birinchi ordm a = d qoldiqlari
har xil va d-chi qoldiq 1 ga teng. Oldin ko'rsatganimizdek, barcha qoldiqlar sikldan o'tadi, d + 1 qoldiq yana a
bo'ladi va bu ikkinchi qoldiq bo'ladi, bu a teng (birinchi d qoldiqlari har xil bo'lgani uchun) va demak, uzunlik (mod
m), agar va faqat bizning siklimizning d1 ÿ d2 ga teng bo'lsa va a (mod d) 4. d s (m) ning bo'luvchisi. ). s(m) Isbot.
Shunday qilib, a s (m). d
2. Ordm a = d bo'lsin. Keyin a, a2 raqamlari Isbot.
Aksincha. a (mod m) va xÿa yy (a xÿy ÿ1) m ga bo‘linadigan darajada x va y (x > y) bo‘lsin . (a, m) =
1 boÿlgani uchun (a x ÿ y ÿ 1) m ga boÿlinadi va undan kichikroq quvvatni (x ÿ y < xd) topdik, shundayki a x ÿ y
ÿ 1 (mod m) .
Yechim. 2 bo'lsin
(mod m) agar va faqat agar d1 ÿ d2 (mod d);
5. 1 dan 200 gacha bo‘luvchi nechta bo‘luvchida 2 raqami bor
239. .d, chunki Eyler
teoremasi 2 boÿyicha 2 hech qanday
juft songa boÿlinmaydi), lekin bundan kelib chiqadiki, 239 > k s(k) d, 1 esa d = 1 va 2 ni bildiradi.
Shunday qilib
ÿ 1 (mod k) (uni ishlatish mumkin, chunki 2
d2 ÿ a
Ta'rif 1. gcd(a, m) = 1 bo'lsin. m modulining ko'rsatkichi ÿ 1 (mod m). Belgilash ordm a
. . ,
ÿ 1?
, .
daraja ko'rsatkichi.
ÿ 1 k ga bo‘linadi, ya’ni k faqat 1 ga teng bo‘lishi mumkin.
.
ÿ 1 taxminan 200 k 1 va d = ordk 2 ga bo‘linadi , keyin ÿ 1 (mod k). Demak, d =
1 yoki d = 239. Xuddi shunday, s(k) . . .d
ÿ 1 (mod m) va qoldiqlarning aylanish uzunligi d, keyin
d1
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
Machine Translated by Google

---

2
.
.
r
r
.
nÿx
n
n
n
x
2r
2 p
2
2 n+1
2
2
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
.
2 ÿ 1.
Yechim. Keling, zudlik bilan hamma narsani taqqoslash tilida qayta yozaylik. Ma'lumki, q
.
ÿ ÿ1 (mod p), shuning uchun a
,
. ord2p -12. ord2 pÿ12 nimaga teng? Keling, ord2 pÿ12 = p ekanligini tushunaylik , chunki birinchidan,
p mos keladi, chunki 2 p ÿ 1 (mod 2pÿ1), x < p 2 xÿ1 < 2 pÿ1 uchun, shuning uchun 2 xÿ1 boÿlishi mumkin emas. 2 p
- 1 ga bo'linadigan . Keyin 2 p - 2 = 2 (2p - 1 - 1) ekanligini isbotlashimiz kerak . Agar p = 2 bo'lsa, bu aniq, agar p
= 2 bo'lsa, bu Eyler teoremasi bo'yicha to'g'ri.
.
2 Qaror. a
)
2
p Yechim. 2
.
.
8. A, n > 1 natural sonlari berilgan. Har bir toq pro + 1 uchun p ÿ 1 soni 2 n+1 ga bo‘linishini isbotlang.
.
q
(mod p). Keling, bu tengsizlikni kvadratga aylantiramiz. Biz q 2r ni olamiz. 1 holat d =
2r
Keyin, oxirgi xususiyatga ko'ra, p - 1 = s (p) . d = 2r 2 holat d = 1 U holda q - 1. - 1 = (p - 1) (p
+ 1) . 3 holat d = 2 U holda q 4 holat d = r Agar r = 2 bo'lsa, 3 holatni olamiz,
shuning uchun r = 2 deb faraz
qilaylik. Keyin oxirgi xossa bo'yicha pÿ1 = s(p) . d = r va pÿ1 .
.
.
va tamom
.
ÿ -1 ÿ
1 (mod p), shuning uchun
. p.
. p.
ÿ 1 (mod p), bu 2 n+1 ni bildiradi . d = ordp2. 2 n+1
bu
yerda xn + 1. Agar x = n + 1 bo'lsa, u holda p - 1 = s (p) . ÿ 1
(mod p). Qarama-qarshilik.
.
. 2, shuning uchun pÿ1 . 2r.
ÿ 4 soni 2 p ÿ 1 ga bo‘linadi.
2018-04-22
p i q -
. 2r yoki q
.
ÿ4 = 4 (22 pÿ2ÿ1) 2 pÿ1 ga bo‘linishi kerak va 2 pÿ2ÿ1 ning o‘zi 2 pÿ1 ga bo‘linishi aniq. Agar
amalning kuchi 2 2 minus birning qandaydir songa bo'linishini istashimizni
isbotlamoqchi bo'lsak, u holda
aslida 2 p - 2 ekanligini isbotlashimiz kerak.
.
Bundan kelib chiqadiki, d = 2x yaxshi.
Agar xn bo'lsa, a
. p
.
.
4. Toq tub son p, shuningdek q va r tub sonlar berilgan. Ma'lumki, + 1.
.
.
7. P. tub son berilgan. Buni isbotlang 2
= (a
a ning 2 yuzinchi bo'luvchisi p
.
. p.
d = ordpq va r asosiy bo'lgani uchun d qiymat uchun 4 ta variantga ega.
.
.
. p. p - 1 ekanligini isbotlang.
Machine Translated by Google

---

2
2
2
2
2
2
.
2
2
2
2
2
2
2
2
ÿ 9 =
ÿ a (mod p) yoki hech bo'lmaganda mavjudligini tushunish
shunday x.
.
ÿ b (mod p)), u holda ab ham kvadrat qoldiqdir, chunki (xy)
, shuning uchun to'rtlik
ÿ a (mod p)) va b — quad ÿ ab
2 va bu yagona echimlar ekanligi aniq, chunki x
Ta'rif. Taqqoslash x uchun o'shalarni a = 0 deb ataylik
Isbot. Agar a kvadrat qoldiq bo'lsa (x
.
Qoldiq xususiyatlari
ratik qoldiq (y (mod p). 2.
Agar
kvadrat qoldiq kvadrat bo‘lmagan qoldiqga ko‘paytirilsa, kvadratik qoldiq bo‘lmagan bo‘ladi.
Keling, PRW moduli p ni ko'rib chiqaylik
Isbot. Agar a kvadratik qoldiq bo'lsa (x CV (1, 2, ..., p-1) a marta, biz
CV (a, 2a, ..., (p-1)a) ni olamiz.
= (x - 3)(x + 3) . 7. Ammo x tenglamani ko'rib chiqsak, hech qanday ildiz
bo'lmaydi (plastinkaga qarang) x ±1 ±2
±3
2018-04-22 _ - va
nolga teng bo'lmagan yechim, kvadrat qoldiqlar bo'yicha va yechimi bo'lmaganlar uchun kvadratik
Taqqoslash x ni yechmoqchimiz
ratik qoldiqlar ham
2
Bu shuni anglatadiki, ularning barchasi har xil, ya'ni kvadrat qoldiqlar doimo p - 1
2
bo'ladi.
ÿ a (mod p) mavjud
2 x
ÿ a (mod p)), agar bo'lsa
Misol uchun, agar bizda x tenglama bo'lsa
.
1
4 2
irqiy chegirma.
1. Agar kvadrat qoldiq kvadrat qoldiqga ko'paytirilsa, siz to'rtburchakni olasiz.
ÿ 2 (mod 7), ya'ni x ÿ ±3 (mod 7) ÿ 2 ÿ 9 (mod 7) va x ÿ 3 (mod
7) yechimlari, keyin u
allaqachon mavjud
.
Birinchidan, p = 2 bilan shug'ullanamiz. E'tibor bering, a = 1 kvadratik ÿ 1 (mod p) har doim qoldiq eritma
moduliga ega, chunki xx = 1 moslik. 0 dan
boshlab, bu ÿ 1 (mod 2), keyin p = 2 uchun har qanday toq son
moduli 2 kvadratik qoldiqdir. Bundan tashqari, hamma joyda biz p > 2 deb hisoblaymiz, chunki p = 2 eng qiziqarli
holat emas. p - 1 p > 2 bo'lsin, ±1, ±2, ..., ± ni ko'rib chiqing va ularni kvadratga aylantiring. Biz 2 p - 1 1, 4, ..., ( )
ni olamiz. p - 1 bo'lsin. p, lekin 0 < x, y . Qarama-qarshilik. 2 p - 1 2
2 x
ratik hisob-kitoblar.
. p, ya'ni x = y yoki x + y
.
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
Kvadrat qoldiqlar
Machine Translated by Google

---

2
,
2
2
pÿ1
pÿ1
pÿ1
pÿ1
2
2
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
a
p
a
kvadratik ayirma.
(pÿ1)/2 (mod p) (Eyler mezoni);
(p > 2 uchun), bu quyidagicha aniqlanadi:
a
p
dan
Agar a kvadrat qoldiq bo'lsa, u holda
p
pÿ1
1 ÿ x
(c)
ÿ 1 (mod p), shuning uchun T
Isbot. Keling, shunga o'xshash dalil keltiraylik. Agar d kvadrat bo'lmagan qoldiq bo'lsa, d, 2d, ..., (p - 1)d ni
ko'paytirsak, d, 2d, ..., (p - 1)d ni olamiz. Kvadrat qoldiq va kvadrat bo'lmagan qoldiqlar soni bir xil va bir-biriga teng
bo'lib qoldi, bilamizki, kvadrat qoldiqni d ga ko'paytirsak, kvadratik qoldiq bo'lmaydi, ya'ni d ga ko'paytirilganda
kvadratik bo'lmagan bo'ladi. qoldiqlar kvadratik qoldiqlarga aylanadi.
p
= 1 ÿ a
Legendre belgisining xususiyatlari. (a)
chegirmalar va chegirmalar teng ravishda -
(b)
a
agar b qoldiq bo'lmasa. e'tibor bering, bu
kvadrat qoldiq va kvadrat bo'lmagan qoldiqlar bir xil bo'lib qoladi va biz bilamizki, kvadrat qoldiqni a ga ko'paytirsak,
yana kvadrat qoldiq hosil bo'ladi, ya'ni a ga ko'paytirilganda kvadratik bo'lmaganlar ham kvadrat bo'lib qoladi.
p
. p, ya'ni b
a
kvadratik qoldiqlar, shuning uchun kvadratik qoldiq bo'lmagan uchun b
2 (mod p), ya'ni (kvadrat chegirma)
b
p
p
2 ÿ -1 (p ga qarshi).
pÿ1
2 dona;
(ko'plik).
= -1, agar a qoldiq bo'lmagan modul p bo'lsa;
pÿ1 , lekin x tenglama
pÿ1
2 .
Isbot. Biz yuqorida birinchi ikkita xususiyatni isbotladik. (pÿ1)/2 (mod p) .
= 0, agar a p ning karrali bo'lsa.
.
Taqqoslash x ni ko'rib chiqing
p
= 1, agar a kvadratik qoldiq moduli p bo'lsa;
qoldiq bo'lmaganlar.
a
Ta'rif 2. Legendre belgisi - bilan belgilangan ifoda
2 ÿ 1 (p ga qarshi).
a
=
•
2 ÿ ±1 (mod p), ildiz
moduli p (Biz bu faktning isbotini o'tkazib yuboramiz,
shuning uchun siz bunga ishonishingiz kerak) va bu aniq.
ÿ a (mod p) va uni quvvatga ko'taring
pÿ1
ÿ a
ÿ a
p
Keling, T = b = b pÿ1 ÿ1 = (T ÿ1)(T + 1) bilan solishtirish mumkin
bo'lgan narsani tushunamiz . 2 ÿ 1 ko'pi bilan pÿ1 mavjud
T
3. Kvadrat qoldiq bo‘lmagan kvadratik qoldiqga ko‘paytirilsa, u holda hosil bo‘ladi.
•
•
Machine Translated by Google

---

2
2
2
2
2
2
2
2
(p-1)/2 b (p-1)/2
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
javob.
. q toq tub q uchun, u holda
3
= -1 ÿ b (p-1)/2 (mod p).
9-bet. 4k + 1 ko‘rinishdagi tub sonlar
cheksiz ko‘p ekanligini isbotlang.
ÿ 2)(x
p
kv. chegirma, ya'ni bizga to'g'ri kelmaydigan yagona holat
ÿ1
...
2 , agar x
6
Yechim. Agar p = 2 yoki p = 3 bo'lsa, u holda x = p bajariladi. Aks holda, y ÿ 6) ÿ 0 (mod p), agar 2, 3
yoki 6 2 bo‘lsa
.
= -1,
ab
+1.
. Qarama-qarshilik.
Isbot. Shubhasiz, tub sonlar cheksiz ko'p. Hammasi oddiy
ÿ 3)(x
Keling, ajratmalar uchun muammolarni hal
qilaylik. 4. ÿ1 kvadrat qoldiq moduli p ÿÿ p = 4k+1 ekanligini isbotlang.
p
b
= 1 va q 4k + 1 ko'rinishidagi tub sondir. Yana tasavvur qiling
ÿ 3)(x
p
= -1, lekin
(p ga qarshi)
Keling, vazifamizga qaytaylik. Biz bilamizki, -1 faqat 4k + 1 kabi tub sondagi kvadrat qoldiqdir, shuning
uchun agar x -1 bo'lsa.
3
.
p
ÿ a
2 x
6
5. Taqqoslash (x
p
q 4k+1 ko’rinishdagi tub sonlar soni chekli va bu yerda ular q1, ...., qm. (2q1...qm) + 1 sonni ko‘rib
chiqaylik , u 2 ga bo‘linmaydi, uning 4k + 3 ko‘rinishdagi bo‘luvchilari yo‘q (chunki q toq tub son uchun .q,
u holda q 4k ko‘rinishdagi tub sondir. + 1) va unday emas
p
ÿ 6) ÿ 0 (mod p) har doim
a
= -1,
=
Agar b kvadrat bo'lmagan qoldiq bo'lsa, u holda
=
ÿ=
+1.
ÿ ÿ1 (mod q),
2
ÿ 2)(x
b
4k + 1 tub songa boÿlinmaydi. Qarama-qarshilik.
ÿ (ab) (pÿ1)/2
3 guruhga bo'linadi: p =
2; p =
4k + 1; p =
4k + 3. Avval
4k + 3 ko'rinishdagi cheksiz ko'p sonlar mavjudligini qarama-qarshilik bilan isbotlaymiz. p1 , ...., pn 4k +
3 ko‘rinishdagi barcha raqamlar bo‘lsin. 4 p1 pn ÿ 1 raqamini ko‘rib chiqaylik. Uning 4k + 3 ko‘rinishdagi
bo‘luvchilari yo‘q va toq, shuning uchun shaklning barcha tub bo‘luvchilari. 4k + 1 , lekin raqamning o'zi
-1 moduliga mos keladi 4. Qarama-qarshilik.
Taqqoslash yechim bo'ladi (x
Yechim. ÿ1 kvadratik qoldiq moduli p ÿÿ 1 = ÿ (ÿ1)(pÿ1)/2 (mod p) ÿÿ (ÿ1)(pÿ1)/2 = 1
ÿÿ p = 4k + 1 .
p
p
p
Machine Translated by Google

---

3
4
3
har xil qoldiqlar bo'ladi, lekin men ular
nafaqat har xil qoldiqlar, balki barcha mumkin bo'lgan modul m bo'lishini istardim.
Ta'rif. Raqam ibtidoiy ildiz rejimi deb ataladi
.
Bir vaqtlar .
Keyin har bir tub qj uchun shunday sonlarni topamiz va ularni ko'paytiramiz. Oldingi lemma bo‘yicha
mahsulotning ko‘rsatkichi LCM(d1, . . . , dpÿ1) ga teng.
.
NOK(d1, .. ., dpÿ1) = q
ÿ 1.
ÿ 2 (mod 7) ÿ
6 (mod 7) ÿ 4
(mod 7) ÿ 5
(mod 7) ÿ 1
(mod 7)
di = q
) ÿ 1 (modp). Nima uchun bu daraja minimal
ekanligini tushunish qoladi. ordpab = t bo'lsin . Keyin (ab) ÿ 1 (mod p).
. dk, shuning uchun t = dk
Isbot. d1, bo'lsin . . . , dpÿ1 1 , sonlarining ko‘rsatkichlari. . . , p-1 mos ravishda
ÿ 1 (mod p), ya'ni kt. . k, ya'ni
t.
Masalan, agar m = 7 bo'lsa, a = 3 ni ko'rib chiqing. 3 ÿ
3 (mod 7) 3
ÿ (a
lu m, agar uning ko'rsatkichi aynan s (m) bo'lsa.
a1 . q 1 .
Ozroq.
3
6
3
.
Agar d = ordma bo'lsa, a, a deb aytdik
.
.
ÿ a kt(b k
k quvvatga ko'taring. (ab) ) . d, chunki (d, k) =
1. Xuddi shunday, t.
t .
. Keyin di bor .
1 , , qan
.
. p va agar k1 < k mavjud bo'lsa , a
ko'rsatkich k, chunki .
p, u holda a ko'rsatkichga ega bo'ladi
a1 . q 1 ,
Birinchidan, biz foydali lemmani isbotlaymiz.
Asosiy lemma. Agar ba'zi ikkita a va b sonlarning darajalari mos ravishda d va k ga teng bo'lsa, (d, k) =
1 bo'lsa, ko'rsatkichi ordpab = dk ga teng bo'lgan son mavjudligini isbotlang .
)
.
lekin.
X. Demak, ko'rsatkichi q bo'lgan son (i X) mavjud
, ...,
. ordpa = d i
(b
Teorema. Har qanday asosiy modul p ibtidoiy ildizga ega.
Agar a ning dk indeksi bo'lsa, u holda a raqamini aytmoqchimiz
ÿ 1.
Isbot. Birinchidan, (ab)
Endi teoremaning isbotiga qaytamiz.
.
3
5
2
t
d
d
kt
ÿ a
dk
a
1
1 .
d
dk
k
d a
t
n
k
2
kt
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
A'1
dk1
A'1
A'1
ibtidoiy ildiz
Machine Translated by Google

---

.
H
H
2
pÿ1
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
p - 1.
va ravvin so'raydi: - Qancha
to'laysiz? - Aslo yo'q, aziz
Rebbe. Biz ravvinlarni tekinga kesib tashladik. Ishlarning bu burilishidan xursand
bo'lgan ravvin jo'nab ketdi.
Shubhasiz, g teng kuchlarga (g
ÿ 1 (mod p). Bir tomondan, ildizlar zarar ko'rmaydi
.
Pop so'raydi: -
Sizdan qancha qarzim bor, azizim, soch olish uchun? -
Aslo, ota. Biz pravoslav ruhoniylarini bepul kesib tashladik. Ertasi kuni ertalab sartarosh
sartaroshxona eshigidan 12 shisha aroq topib oldi.
ÿ 1 (p ga qarshi),
ÿ 1 (p ga qarshi).
. . , gpÿ1 har xil va g
.
Keling, bu darajalarning qaysi biri kvadrat ekanligini o'ylab ko'raylik. ajratmalar.
Sartarosh haqida bir daqiqalik hazil Qi ga katolik pastor keladi
H dan kichikroq. Boshqa tomondan, H. ÿ 1 (mod p), ya'ni kamida p - 1 va H p - 1 yechimlari. Biz oxirgi 2
ta faktni birlashtiramiz va biz H = p - 1 ni olamiz, ya'ni biz ibtidoiy ildizni topamiz.
(2k+1) (pÿ1)/
2 (mod p); g
qarama-qarshi holatda g
va bu bo'lishi mumkin emas, chunki barcha qoldiqlar g, g2 , .
Biz hozirgina isbotladikki, har qanday p moduli uchun primitiv mavjud
H i p - 1 H.
, g4 ,
. indikator xususiyati bo'yicha di = ordpi . Shunday qilib, p - 1.
Ertasi kuni ertalab sartarosh o'z sartaroshxonasi eshigi oldida o'n ikki ... ravvinlarni ko'rdi !!! ..
. har qanday i uchun di , shuning uchun i
. . .
Tez orada pravoslav ruhoniy sartaroshga keladi. Sartarosh ham sochini kestirib oldi.
chunki ularning har biri kvadrat va g toq darajalar kvadratdir. qoldiqsiz, 2k+1 dan beri
H = LCM(d1, . . ., dpÿ1) = p ÿ 1 ekanligini isbotlash qoladi.
Keling, x taqqoslashini ko'rib chiqaylik
Bir necha kundan keyin ravvin sartaroshga keladi. Sartarosh sochini kesdi,
pÿ1
ÿ x
.
, gpÿ1 ) - bularning barchasi kvadrat. chegirmalar,
rulnik. U uni
tonladi, pastor so'radi: - Mendan qancha? -
Hechqisi yo'q, hurmatli.
Men katolik ruhoniylaridan soch olish uchun pul olmayman. Yoqimli ajablanib, pastor chiqib ketdi. Ertasi
kuni sartarosh kelib, sartaroshxona eshigi ostida 12 shisha eng yaxshi monastir sharobini ko'radi.
2 ÿ x
turli ildiz g. Endi biz barcha qoldiqlarni g, g2 , deb ifodalashimiz mumkin . . . , gpÿ1 .
(pÿ1)/2
ÿ g
Machine Translated by Google

---

pÿ1
pÿ1
2
2
.
,
i
10
k
5
5
pÿ1
p
k
2
pÿ1
k
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
kd
g
p - 1 = kd bo'lsin. PrSV g, g2 , k kuchga ko'tarilganda . . . , gpÿ1 ni olamiz, g2k , . . . gdk = 1, g(d+1)k = g
pÿ1 2 ÿ g
men g
.
+ 2i + . . . + (p - 1)i ÿ g
Vilson teoremasining isboti (p - 1)! ÿ gg2 . . . gpÿ1 ÿ
g
Numerator p ga bo'linadi, chunki g
Bir tomondan, g (p-1),
biz
g ni olamiz
.
, ....)
. . , gpÿ1 . Raqamlar
uchun u 239 ga bo'linadi, shuning uchun bizning qurilishimiz
ÿ 1 (mod p) ÿ kd .
(pÿ1)
2 ÿ g
iÿ1 i+1 ÿ
gg
Yechim. Biz qiladigan birinchi narsa, barcha qoldiqlarni g ning darajalariga o'zgartiramiz. Keyin
(pÿ1)i ÿ 1 i
g
(pÿ1)i
2i + . . . + g = g
ÿ 1
pÿ1
g
, g(pÿ1)k va aniq d vaqtlar bo'lishi aniq
Yechim. Keling, 1, 2, raqamlarimizni olaylik. . . , 238, sifatida g, g2 , . . . , gpÿ1 ,
Biz qachon tushunmoqchimiz
men 1
+ g
, g10, g15 = g
. ,
men 1
ÿ ÿ1 (mod p)
, g20 = g
- va
.
ÿ 1 (mod 1) va 0 < ip - 2 dan beri, biz
. p - 1 Ya'ni, agar k p - 1 ga nisbatan tub bo'lsa, u holda d = p - 1 va p -1
bo'lsa , k p - 1 ga o'zaro tub bo'lmasa, u holda d = (p - 1,k)
. . .
Endi o'ylab ko'raylik: modulo p necha xil ibtidoiy ildizlar mavjud?
.
2 ni 1 bilan taqqoslab bo'lmaydi, aksincha (p-1)/2 ÿ 1 (mod p) kvadratiga aylanganda,
shuning
uchun (p - 1)! ÿg
238 ni aylana bo'ylab shunday joylashtirish
mumkinki, soat yo'nalishi bo'yicha har qanday ketma-ket uchta a, b, c sonlar uchun b soni 239 ga
bo'linadi.
son p ga bo'linmaydi, shuning uchun bu yig'indi p ga bo'linadi.
iÿ1 i i+1 2i g , g , g Birlashmada
hamma narsa yaxshi, chunki g va g
p+1 p raqamlari g va g sifatida ifodalanishi mumkin.
. p.
ibtidoiy ildiz hisoblanadi. d = ordpg bo'lsin
3. Natural sonlar 1, 2, ekanligini isbotlang.
k
g shaxsiy balanslar. Bu muammo 5-chi kuchlar haqida bo'lgan hollarda foydali bo'lishi mumkin, keyin o'n birinchi
modul haqida gapirish qulay, chunki u atigi 2 marta chiqadi.
2 (p ga qarshi)
6. P tub son va natural son 0 < ip ÿ 2 berilgan. Buni isbotlang
shaxsiy balanslar (g
Bu
erda g - ibtidoiy ildiz va biz ularni aylana shaklida joylashtiramiz, chunki bizni faqat modul 239 raqamlarining
qiymatlari qiziqtiradi. Keling, g, g2 kabi aylanadan joylashtiramiz .
+ 2i + . . . + (p - 1)i .
Machine Translated by Google

---

2
2
2
2
2
2
2
2
2
2
Oddiy oqim. Raqamlar nazariyasi. • “Shkolkovo”, 2020–2021 o‘quv yili
lekin ikkita kvadratning yig'indisi sifatida tasavvur qiling.
2 kalamush va biz -x ni olamiz
Birinchidan, keling, Thue lemmasini isbotlaylik.
0 < x2 + y
+ va
Lemma Thue. n natural son, a butun son bo‘lsin. U holda (x, y) = (0, 0), ax - y bo'ladigan x va y butun sonlar
mavjud. n, va |x|, |y| ÿn. Isbot. 0 x ÿ n, 0 y ÿ n ((0, 0) dan tashqari)
bo'lgan (x, y) juftlarni ko'rib chiqing. X uchun variantlar aynan [ ÿ n]+1 > ÿ n (0, 1, ...., [ÿ n]) va y uchun
variantlar ham xuddi shunday > ÿ n, shuning uchun juftlar > n yoki n+1, lekin biz tashqariga tashlashimiz kerak
(0, 0), shuning uchun par n. Har bir juftlik uchun siz ax ÿ y ning qiymatini hisoblashingiz mumkin va bizda ax ÿ y
n ga bo'linadigan juftlik mavjud yoki ax ÿ y qiymatlarining barcha juftlari uchun n ga bo'linmaydi. U holda, kamida
n ta juft bo'lgani uchun, 2 ta (x1, y1) va (x2, y2) juftlar mavjudki , ular uchun ax1 - y1 va ax2 - y2 bir xil qoldiq
moduli n bo'ladi. U holda (ax1ÿy1)ÿ(ax2ÿy2) = a(x1ÿx2)ÿ(y1ÿy2) n, ÿ n x1ÿx2 ÿ ÿ n va ÿ n y1 ÿ y2 ÿ ÿ n ga
bo‘linadi , ya’ni , biz mos x = x1 - x2 va y = y1 - y2 ni topdik.
+ va
2 - hatto p moduli, shuning uchun a bor
= p.
va x butun sondir.
2 2 x
2018-03-22 _ . p va
.
+ va
< ÿp
2 ÿ b
2 ta tasvirni x sifatida
1 dan 2p - 1 gacha va p ga bo'linadi, shuning uchun x
Yechim. Birinchidan, aytaylik, p = 4k + 3 tub son uchun yo'q
faqat 0, 1 va 2 qoldiqlarini berishi mumkin.
+ va
Teoremani isbotlashga qaytamiz. p = 4k + 1 bo'lgani uchun -1 kvadratdir. siz ÿ ÿ1 (mod p). x, y bo‘yicha
toping
.
Fermaning Rojdestvo teoremasi 4k+1 ko'rinishdagi har qanday tub p soni uchun,
va 1 modul 4, ya'ni x
Bundaylar uchun lemma. Bizda ax ÿ b (mod p), to'rt ÿ (ax) (mod p), y = b oling, biz x = 2p ni olamiz, chunki (x, y)
= (0, 0) va x = ÿ p chunki p. asosiy hisoblanadi
. Buning sababi, kvadratlar faqat 0 ning qoldiqlarini beradi.
+ va
.
+ ÿp
Machine Translated by Google