MathTest.uz
Algebra

Qoldiqli bo'lish. Oxirgi raqam.

ortacha 50 daqiqa qoldiqli bo'lishoxirgi raqammodular arifmetikataqqoslash (kongruensiya)davriylik

Nima uchun muhim?

2^{50} sonining oxirgi raqami nechaga teng? Bu sonni to'liq hisoblash (u 15 xonadan ortiq) shart emas — chunki oxirgi raqamlar DAVRIY tarzda takrorlanadi. Bu mavzu "Natural sonlar" va "Bo'linish belgilari" mavzularidagi bo'lish algoritmini "taqqoslash" (kongruensiya) tiliga o'tkazadi — bu til son nazariyasi, kriptografiya va olimpiada matematikasida universal vosita hisoblanadi. Milliy sertifikat va xalqaro olimpiadalarda "oxirgi raqamni toping" turidagi masalalar juda tez-tez uchraydi, va bu mavzu ularni tizimli yechish usulini beradi.

O'quv maqsadlari

  • Taqqoslash (kongruensiya) belgisi $a \equiv b \pmod{m}$ ning ma'nosini tushunish va qo'llay olish
  • Taqqoslashlarning qo'shish, ayirish, ko'paytirish amallariga nisbatan saqlanish xossasini bilish
  • Sonlarning darajalarida oxirgi raqam davriy takrorlanishini aniqlash va davr uzunligini topish
  • Juda katta ko'rsatkichli darajalarning oxirgi raqamini (yoki oxirgi bir necha raqamini) davriylik orqali tez hisoblash
  • Real hayotdagi 'haftaning qaysi kuni' turidagi davriy masalalarni qoldiqli bo'lish orqali yechish
1801-yilda buyuk matematik Karl Fridrix Gauss "taqqoslash" (congruence) tushunchasini kiritdi: agar ikkita son bir xil songa (modulga) bo'linganda bir xil qoldiq bersa, ular shu modul bo'yicha "taqqoslanadigan" (kongruent) deyiladi. Bu — bugungi kunda "modular arifmetika" deb ataladigan, butun matematik tilning boshlanishi bo'ldi. Eng oddiy va tanish misol — soat mexanizmi: soat 10 dan keyin 5 soat o'tsa, "15" emas, "3" bo'ladi (chunki 15 mod 12 = 3). Xuddi shunday, sonning "oxirgi raqami" — bu son 10 ga bo'linganda qoldiq, ya'ni $n \bmod 10$. Ajoyib xususiyat: agar biror sonning darajalarini ketma-ket hisoblasangiz ($2^1$,$2^2$,$2^3$,...), ularning oxirgi raqamlari DAVRIY takrorlanadi: 2,4,8,6,2,4,8,6,... (davr uzunligi 4). Bu davriylik istalgan darajali sonning oxirgi raqamini, hatto ko'rsatkich million bo'lsa ham, bir necha soniyada topish imkonini beradi.

Ta'riflar

Taqqoslash (kongruensiya)

Agar $(a-b)$ soni $m$ ga qoldiqsiz bo'linsa, $a$ va $b$ sonlari $m$ moduli bo'yicha taqqoslanadigan (kongruent) deyiladi: $a \equiv b \pmod{m}$

$a$ va $b$ sonlari $m$ ga bo'linganda BIR XIL qoldiq beradi.

Misol: $17 \equiv 2 \pmod{5}$, chunki $17=5 \times 3+2$ va $2=5 \times 0+2$ — ikkalasi ham $5$ ga bo'linganda $2$ qoldiq beradi.

Bu emas: $17 \not\equiv 3 \pmod{5}$, chunki $17 \mod 5=2$, lekin $3 \mod 5=3$ — qoldiqlar har xil.

💡 $\equiv$ belgisi 'teng' ($=$) belgisidan farqli — u 'bir xil qoldiqli' degan ma'noni bildiradi, sonlarning o'zi teng bo'lishi shart emas.

Sonning oxirgi raqami

$n$ natural sonining oxirgi raqami — $n$ ni $10$ ga bo'lgandagi qoldiq, ya'ni $n \bmod 10$.

Sonni o'ngdan birinchi raqami.

Misol: $2847$ sonining oxirgi raqami $7$ ($2847 \bmod 10 = 7$).

Bu emas: $2847$ sonining oxirgi raqami $2847$ EMAS — bu butun son, oxirgi raqam faqat bitta xonaviy qiymat ($0-9$ orasida).

💡 Umumiy holda, oxirgi $k$ ta raqam $n \bmod 10^k$ orqali topiladi (masalan oxirgi $2$ raqam uchun $\bmod 100$).

Davr (davriylik)

Agar $a^{n\bmod m}$ ketma-ketligi $n$ ortishi bilan $T$ qadamdan keyin o'zini takrorlay boshlasa (ya'ni $a^{n+T}\equiv a^{n}$ har bir yetarlicha katta $n$ uchun), $T$ — bu ketma-ketlikning davri deyiladi.

Darajalarning oxirgi raqami (yoki qoldig'i) qancha qadamdan keyin qaytadan boshidan takrorlanishini ko'rsatadigan son.

Misol: 2 ning darajalari oxirgi raqami: $2$,$4$,$8$,$6$,$2$,$4$,$8$,$6$,... — davr $T=4$.

Bu emas: Davr 3 EMAS — $2$,$4$,$8$ dan keyin $6$ keladi, $2$ emas, demak davr aynan $4$ qadamdan keyin takrorlanadi.

💡 Har bir raqam (0-9) uchun davr uzunligi turlicha: $0$,$1$,$5$,$6$ uchun $T=1$; $4$,$9$ uchun $T=2$; $2$,$3$,$7$,$8$ uchun $T=4$.

Fundamental tushunchalar

Taqqoslashning asosiy xossalari

Agar $a \equiv b \pmod{m}$ va $c \equiv d \pmod{m}$ bo'lsa, u holda: $(a+c) \equiv (b+d) \pmod{m}$, $(a-c) \equiv (b-d) \pmod{m}$, va $(a \times c) \equiv (b \times d) \pmod{m}$. Bu — taqqoslashlar bilan 'oddiy tenglik kabi' ishlash mumkinligini bildiradi (qo'shish, ayirish, ko'paytirish uchun).

$a \equiv b, c \equiv d \pmod{m} \implies a + c \equiv b + d, a \cdot c \equiv b \cdot d \pmod{m}$

MUHIM ISTISNO: bo'lish umumiy holda saqlanmaydi (agar $ac \equiv bc \pmod{m}$ bo'lsa, bundan $a \equiv b \pmod{m}$ har doim kelib chiqavermaydi, faqat $EKUB(c,m)=1$ bo'lganda).

Darajalarning oxirgi raqami davriyligi

Har qanday $a$ soni uchun $a^n \mod 10$ ketma-ketligi ($n=1,2,3,...$) chekli qiymatlar (0-9) orasida boʻlgani uchun, qaysidir bosqichda albatta takrorlanishi SHART (Dirixle qutichalar printsipi). Amalda: $2,3,7,8$ oxirgi raqamiga ega sonlar uchun davr=$4$; $4,9$ uchun davr=$2$; $0,1,5,6$ uchun davr=$1$.

$a^{n} \bmod 10 = a^{n \bmod T} \bmod 10 \quad (T — \text{дaвp}, n \bmod T=0 \text{ бo'лca oxirgi элементни olish kerak})$

Bu jadval barcha bir xonali raqamlar (0-9) uchun toʻgʻridan-toʻgʻri tekshirilib chiqarilgan.

Yig'indi va ko'paytmaning oxirgi raqamini topish

Ikki (yoki undan ortiq) sonning yig'indisi yoki ko'paytmasining oxirgi raqamini topish uchun FAQAT ularning oxirgi raqamlarini qo'shish/ko'paytirish, so'ng natijaning ham oxirgi raqamini olish yetarli — bu taqqoslash xossalarining to'g'ridan-to'g'ri natijasi.

$(a \times b) \bmod 10 = [(a \bmod 10) \times (b \bmod 10)] \bmod 10$

Bu usul katta sonlar ustida amallarni katta sonlarning o'zini hisoblamasdan tekshirish (masalan xatoni topish) uchun ham ishlatiladi.

Haftaning kuni va davriy masalalar

'Bugun payshanba, 100 kundan keyin qaysi kun bo'ladi' turidagi masalalar aslida $100 \bmod 7$ ni topib, shuncha kun payshanbadan keyinga siljitish kifoya.

$k_{un}(n) = (k_{un}(0) + n) \mod 7$

Bu — modular arifmetikaning eng ko'p uchraydigan amaliy qo'llanilishlaridan biri (kalendar hisob-kitoblari).

Formula kutubxonasi

Taqqoslash ta'rifi (modul bo'yicha)

$$a \equiv b \pmod{m} \iff m \mid (a-b)$$
  • $a,b$ — taqqoslanayotgan butun sonlar
  • $m$ — modul (musbat butun son)

a va b bir xil qoldiq beradi m ga bo'linganda.

Shart: m>0.

Xususiy holatlar: a≡0 (mod m) ⟺ a soni m ga qoldiqsiz bo'linadi.

Darajaning oxirgi raqami (davriylik orqali)

$$a^n \bmod 10 = a^{\,((n-1) \bmod T) + 1} \bmod 10$$
  • $a$ — asosning oxirgi raqami (0-9)
  • $n$ — daraja ko'rsatkichi
  • $T$ — a ning oxirgi raqami davri (1, 2 yoki 4)

Katta n uchun oxirgi raqamni to'g'ridan-to'g'ri hisoblamasdan, davr ichidagi mos qiymatni topish orqali aniqlash.

Shart: n ≥ 1.

Xususiy holatlar: T=1 bo'lgan raqamlar (0,1,5,6) uchun oxirgi raqam n ga bog'liq bo'lmaydi — har doim bir xil.

Teoremalar va isbotlar

📐 Taqqoslashlarning arifmetik xossalari

Agar $a \equiv b \pmod{m}$ va $c \equiv d \pmod{m}$ bo'lsa, u holda $a + c \equiv b + d \pmod{m}$, $a - c \equiv b - d \pmod{m}$, va $a \cdot c \equiv b \cdot d \pmod{m}$.

Agar ikki juft son mos ravishda bir xil qoldiq bersa, ularning yig'indisi va ko'paytmasi ham mos ravishda bir xil qoldiq beradi.

Isbotni ko'rsatish

Berilgan: $a\equiv b \pmod{m}$, $c\equiv d \pmod{m}$, ya'ni $m|(a-b)$ va $m|(c-d)$

Isbotlash kerak: $a+c\equiv b+d \pmod{m}$ va $a\cdot c\equiv b\cdot d \pmod{m}$

  1. QO'SHISH UCHUN: $(a+c)-(b+d) = (a-b)+(c-d)$. Ikkala qo'shiluvchi ham $m$ ga bo'linadi (berilgan shart), demak ularning yig'indisi ham $m$ ga bo'linadi. Shuning uchun $m|[(a+c)-(b+d)]$, ya'ni $a+c\equiv b+d \pmod{m}$
  2. KO'PAYTIRISH UCHUN: $a\cdot c-b\cdot d$ ni quyidagicha ajratamiz: $a\cdot c-b\cdot d = a\cdot c-a\cdot d+a\cdot d-b\cdot d = a(c-d)+d(a-b)$
  3. $a(c-d)$ — $m$ ga bo'linadi, chunki $(c-d)$ $m$ ga bo'linadi (berilgan) va $a$ butun songa ko'paytirilgan.
  4. $d(a-b)$ — $m$ ga bo'linadi, chunki $(a-b)$ $m$ ga bo'linadi (berilgan) va $d$ butun songa ko'paytirilgan.
  5. Ikkala had ham $m$ ga bo'lingani uchun ularning yig'indisi $a(c-d)+d(a-b)=a\cdot c-b\cdot d$ ham $m$ ga bo'linadi.

Demak $m|(a+c-b-d)$ va $m|(a\cdot c-b\cdot d)$, ya'ni $a+c\equiv b+d \pmod{m}$ va $a\cdot c\equiv b\cdot d \pmod{m}$. ∎

📐 Oxirgi raqamning davriyligi teoremasi

Har qanday $a$ ($0\le a\le 9$) uchun $a^n \bmod 10$ ketma-ketligi $n=1$ dan boshlab davriy bo'lib, davr uzunligi $T\le 4$ (aniqrog'i: $0,1,5,6$ uchun $T=1$; $4,9$ uchun $T=2$; $2,3,7,8$ uchun $T=4$).

Qoldiqlar to'plami chekli ($0$ dan $9$ gacha, $10$ ta variant) bo'lgani uchun, ketma-ket hisoblashda albatta takrorlanish yuz berishi shart.

Isbotni ko'rsatish

Berilgan: a — bir xonali raqam (0-9), $a^n \bmod 10$ ketma-ketligi $n=1,2,3,...$ uchun qaraladi.

Isbotlash kerak: Bu ketma-ketlik davriy, davr $T\le4$.

  1. $a^n \bmod 10$ har doim 0 dan 9 gacha bo'lgan (jami 10 ta) qiymatlardan birini oladi — chekli to'plam.
  2. $n=1,2,3,...,11$ uchun $a^1,a^2,...,a^{11}$larning $\bmod 10$ qiymatlarini qaraymiz — bu 11 ta qiymat, lekin faqat 10 ta mumkin bo'lgan variant bor.
  3. Dirixle qutichalar printsipiga ko'ra, kamida ikkita ko'rsatkich $i<j$ ($1\le i<j\le 11$) uchun $a^i\equiv a^j \pmod{10}$ bo'lishi SHART.
  4. $a^i\equiv a^j \pmod{10}$ bo'lsa, taqqoslash xossalariga ko'ra (ko'paytirish saqlanishi tufayli) $a^{i+k}\equiv a^{j+k} \pmod{10}$ barcha $k\ge0$ uchun ham to'g'ri bo'ladi — demak ketma-ketlik $j-i$ qadamdan keyin o'zini takrorlaydi.
  5. Har bir bir xonali $a$ uchun to'g'ridan-to'g'ri hisoblash (0-9 barchasini tekshirish) davr uzunligi har doim 4 dan oshmasligini tasdiqlaydi.

Demak, har qanday $a$ uchun $a^n \bmod 10$ ketma-ketligi davriy, va davr $T\le4$. ∎

Yechilgan misollar

oson $7^3$ sonining oxirgi raqamini toping.

💡 Maslahat: $7^3$ ni to'g'ridan-to'g'ri hisoblang: 343.

  1. $7^3=343$
  2. Oxirgi raqam: 3

✅ Javob: 3

Nega bu usul ishlaydi: Kichik darajalar uchun to'g'ridan-to'g'ri hisoblash eng oddiy usul.

Muqobil usul: 7 ning davri: 7,9,3,1 ($T=4$). $n=3$: 3-o'rindagi element — 3.

⚠️ $7^3$ ni 21 (7×3) deb noto'g'ri hisoblash — daraja ko'paytirish emas.

oson 23 sonini 6 ga boʻlganda hosil boʻladigan qoldiqni toping.

💡 Maslahat: Boʻlish algoritmi: 23=6q+r.

  1. 6×3=18, 6×4=24>23
  2. q=3, r=23−18=5

✅ Javob: r=5 (23≡5 mod 6)

Nega bu usul ishlaydi: Boʻlish algoritmining toʻgʻridan-toʻgʻri qoʻllanilishi.

⚠️ q ni notoʻgʻri (masalan 4) tanlab, manfiy yoki notoʻgʻri qoldiq olish.

ortacha $2^{100}$ sonining oxirgi raqamini toping.

💡 Maslahat: 2 ning oxirgi raqam davri $T=4$ ($2$, $4$, $8$, $6$). $100$ ni $4$ ga bo'ling.

  1. 2 ning davri: $2^1\rightarrow 2$, $2^2\rightarrow 4$, $2^3\rightarrow 8$, $2^4\rightarrow 6$, $2^5\rightarrow 2$, ... ($T=4$)
  2. $100 \bmod 4 = 0$, bu davrning 4-elementiga (oxirgisiga) mos keladi
  3. $2^4$ oxirgi raqami — $6$

✅ Javob: 6

Nega bu usul ishlaydi: $100 \bmod 4=0$ bo'lgani uchun davrning oxirgi (4-chi) elementini olamiz, davrning 'boshlanishi' emas.

Muqobil usul: $2^{100}=(2^4)^{25}=16^{25}$, $16$ oxiri $6$, $6$ ning istalgan darajasi oxiri $6$ bo'lib qoladi ($T=1$ uchun $6$).

⚠️ $100 \bmod 4=0$ bo'lganda '0-elementni' (mavjud bo'lmagan) emas, davrning OXIRGI elementini olish kerakligini unutish.

ortacha 3^{50} sonining oxirgi raqamini toping.

💡 Maslahat: 3 ning davri: 3, 9, 7, 1 ($T=4$). 50 mod 4 ni toping.

  1. 3 ning davri: $3^1 \to 3$, $3^2 \to 9$, $3^3 \to 7$, $3^4 \to 1$ ($T=4$)
  2. $50 \mod 4 = 2$ ($50=4 \times 12 + 2$)
  3. Demak 2-elementga mos: $3^2$ oxirgi raqami — 9

✅ Javob: 9

Nega bu usul ishlaydi: $50 \mod 4 = 2$ bo'lgani uchun davrning 2-elementini olamiz.

⚠️ Davr elementlarini index bilan chalkashtirib, 1-elementni (3) noto'g'ri javob deb olish.

ortacha 127 va 341 sonlarining ko'paytmasi 127×341 ning oxirgi raqamini, to'liq ko'paytirmasdan toping.

💡 Maslahat: Faqat oxirgi raqamlarni (7 va 1) ko'paytiring.

  1. $127 \bmod 10 = 7$, $341 \bmod 10 = 1$
  2. $(7 \times 1) \bmod 10 = 7$

✅ Javob: Oxirgi raqam — 7 (tekshirish: $127 \times 341 = 43307$, haqiqatan oxiri 7).

Nega bu usul ishlaydi: Ko'paytmaning oxirgi raqami faqat ko'paytuvchilarning oxirgi raqamlariga bog'liq (taqqoslash xossasi).

Muqobil usul: To'liq ko'paytirish: $127 \times 341 = 43307$.

⚠️ Butun sonlarni (127, 341) ko'paytirib, keyin oxirgi raqamni olish — usul to'g'ri, lekin bu 'qisqa yo'l'ning maqsadi katta sonlarda vaqtni tejash, shuni tushunmasdan uzun yo'l bilan yurish samarasiz.

murakkab 7¹⁰⁰⁰ sonining oxirgi ikki raqamini toping (mod 100).

💡 Maslahat: 7 ning mod 100 bo'yicha davrini toping: 7, 49, 43, 01, 07, ... davr $T=4$ ($7^4 \equiv 01 \pmod{100}$).

  1. $7^1 = 07$, $7^2 = 49$, $7^3 = 343 ightarrow 43$, $7^4 = 43 imes 7 = 301 ightarrow 01 \pmod{100}$
  2. $7^4 \equiv 1 \pmod{100}$ — demak davr $T=4$
  3. $1000 mod 4 = 0$, bu 4-elementga mos keladi: $7^4 \equiv 01 \pmod{100}$

✅ Javob: Oxirgi ikki raqam: 01

Nega bu usul ishlaydi: Xuddi oxirgi bitta raqam kabi, oxirgi IKKI raqam ham mod 100 bo'yicha davriy bo'ladi, faqat modul kattaroq bo'lgani uchun davr odatda uzunroq.

Muqobil usul: To'g'ridan-to'g'ri kichik darajalarni hisoblab, davrni tajriba yo'li bilan topish.

⚠️ mod 10 uchun ishlagan $T=4$ davrni mod 100 uchun ham bir xil deb, tekshirmasdan qo'llash — bu tasodifan to'g'ri chiqdi, lekin har doim alohida tekshirish kerak.

murakkab Bugun seshanba. 2024 kundan keyin haftaning qaysi kuni bo'ladi?

💡 Maslahat: 2024 mod 7 ni toping, so'ng seshankadan shuncha kun oldinga siljiting.

  1. $2024 \div 7 = 289$, qoldiq: $2024-289\times 7=2024-2023=1$
  2. Demak 2024 kun — $1$ kunga (mod $7$) teng
  3. Seshankadan $1$ kun keyin — chorshanba

✅ Javob: Chorshanba

Nega bu usul ishlaydi: Haftaning kunlari $7$ moduli bo'yicha davriy takrorlanadi, shuning uchun faqat qoldiq ($1$) muhim, $289$ to'liq hafta esa kunni o'zgartirmaydi.

⚠️ $2024$ ni $7$ ga bo'lishda hisoblash xatosi qilish yoki qoldiqni haftaning kunlari ro'yxatida noto'g'ri kundan (masalan dushanbadan) boshlab sanash.

murakkab n^2+1 soni hech qachon 4 ga bo'linmasligini isbotlang (n — istalgan butun son).

💡 Maslahat: n ning 4 bo'yicha barcha mumkin qoldiqlarini (0,1,2,3) alohida tekshiring.

  1. n mod 4 ning mumkin qiymatlari: 0,1,2,3.
  2. n≡0: n^2≡0, n^2+1≡1 (mod 4) — 4 ga bo'linmaydi.
  3. n≡1: n^2≡1, n^2+1≡2 (mod 4) — bo'linmaydi.
  4. n≡2: n^2≡4≡0, n^2+1≡1 (mod 4) — bo'linmaydi.
  5. n≡3: n^2≡9≡1, n^2+1≡2 (mod 4) — bo'linmaydi.
  6. Barcha 4 ta holatda ham n^2+1 4 ga bo'linmaydi (qoldiq faqat 1 yoki 2 bo'ladi, hech qachon 0 emas).

✅ Javob: Isbotlandi: n^2+1 hech qachon 4 ga bo'linmaydi, chunki n^2 mod 4 faqat 0 yoki 1 qiymat oladi, +1 esa bu qiymatlarni 1 yoki 2 ga aylantiradi. ∎

Nega bu usul ishlaydi: Barcha mumkin qoldiqlarni to'liq sanab (holatlarga ajratib) tekshirish — bu modular arifmetikadagi eng ishonchli isbot usuli, chunki qoldiqlar to'plami chekli.

⚠️ Faqat bitta yoki ikkita misolni (n=1,2) tekshirib, umumiy isbot uchun yetarli deb hisoblash — barcha 4 qoldiq holati tekshirilishi shart.

olimpiada $3^{3^{100}}$ sonining oxirgi raqamini toping (daraja ustida daraja).

💡 Maslahat: Avval ichki darajaning 4 bo'yicha qoldig'ini (chunki 3 ning oxirgi raqam davri T=4) toping.

  1. 3 ning oxirgi raqam davri T=4, shuning uchun $3^k$ ning oxirri raqamini topish uchun $k \bmod 4$ kerak.
  2. $k=3^{100}$ bo'lgani uchun, $3^{100} \bmod 4$ ni topamiz: $3\equiv-1 \pmod{4}$, demak $3^{100}\equiv(-1)^{100}=1 \pmod{4}$.
  3. Demak $3^{3^{100}}$ ning ko'rsatkichi mod 4 bo'yicha 1 ga teng (chunki $3^{100} \bmod 4=1$, va bu 0 emasligi uchun to'g'ridan-to'g'ri davr indeksi sifatida ishlatiladi).
  4. $3^1$ ning oxirgi raqami — 3.

✅ Javob: 3

Nega bu usul ishlaydi: Ikki bosqichli davriylik: avval ko'rsatkichning o'zini kichikroq modul (4) bo'yicha soddalashtirish, so'ng asosiy davrga qo'llash — bu 'daraja ustida daraja' masalalarining standart yechim texnikasi.

⚠️ $3^{100} \bmod 4$ ni hisoblamasdan, to'g'ridan-to'g'ri 100 mod 4=0 (asosiy ko'rsatkich uchun ishlatiladigan usul) ni ichki darajaga noto'g'ri qo'llash — ichki daraja alohida hisoblanishi kerak.

olimpiada Isbotlang: har qanday $n$ uchun $n^5$ va $n$ bir xil oxirgi raqamga ega ($n^5 \equiv n \pmod{10}$).

💡 Maslahat: $n$ ning oxirgi raqami (0-9) bo'yicha barcha holatlarni tekshiring, yoki Ferma kichik teoremasidan (mod 2 va mod 5 alohida) foydalaning.

  1. $n$ ning oxirgi raqami $d$ ($0 \le d \le 9$) bo'lsin — $n^5 \bmod 10 = d^5 \bmod 10$ ni tekshirish yetarli (chunki oxirgi raqam faqat oxirgi raqamga bog'liq).
  2. $d=0: 0^5=0. d=1: 1^5=1. d=2: 32 \to 2. d=3: 243 \to 3. d=4: 1024 \to 4. d=5: 3125 \to 5. d=6: 7776 \to 6. d=7: 16807 \to 7. d=8: 32768 \to 8. d=9: 59049 \to 9.$
  3. Barcha 10 ta holatda ham $d^5 \bmod 10 = d$ — ya'ni $n^5$ har doim $n$ bilan bir xil oxirgi raqamga ega.

✅ Javob: Isbotlandi: barcha 10 ta mumkin oxirgi raqam (0-9) uchun to'g'ridan-to'g'ri tekshirib chiqilganda, $d^5 \equiv d \pmod{10}$ ekanligi tasdiqlanadi. ∎ (Chuqurroq izoh: bu natija Ferma kichik teoremasining (mod 2 va mod 5 uchun alohida qo'llanilib, Xitoy qoldiqlar teoremasi bilan birlashtirilgan) natijasidir.)

Nega bu usul ishlaydi: 10 ta holatning barchasini to'liq sanab chiqish (bu yerda chekli va kichik to'plam bo'lgani uchun) qat'iy va to'liq isbot beradi.

Muqobil usul: Ferma kichik teoremasi: $n^5 \equiv n \pmod{5}$ har doim to'g'ri (Ferma teoremasi), va $n^5 \equiv n \pmod{2}$ ham to'g'ri (n juft/toqligiga qarab), Xitoy qoldiqlar teoremasi orqali $n^5 \equiv n \pmod{10}$ kelib chiqadi.

⚠️ Faqat bir nechta misol (masalan $n=2, 3$) tekshirib, 'isbotlandi' deb xulosa chiqarish — barcha 10 ta oxirgi raqam holatini (yoki umumiy teoremani) ko'rsatish zarur.

Umumiy xatolar

❌ Davr indeksini hisoblashda $n \bmod T = 0$ bo'lgan holatda 'nolinchi element' yoki bo'sh javob izlash.

Davr 1 dan $T$ gacha nomerlangan, 0 emas — $n \bmod T=0$ bo'lganda bu aslida davrning OXIRGI ($T$-chi) elementiga to'g'ri keladi.

✅ Agar $n \bmod T=0$ bo'lsa, $T$-chi (oxirgi) elementni oling, 0-chi emas.

$2^{12}$: $12 \bmod 4=0$, demak $2^4$ (davrning oxirgi elementi, oxiri 6) — $2^{12}$ oxiri 6, $2^0(=1)$ emas.

❌ Har bir raqam uchun davr uzunligini har doim 4 deb hisoblash.

Davr uzunligi raqamga qarab farq qiladi: 0,1,5,6 uchun $T=1$, 4,9 uchun $T=2$, faqat 2,3,7,8 uchun $T=4$.

✅ Avval asosning oxirgi raqamini aniqlang, so'ng shu raqamga mos davr uzunligini (jadvaldan yoki hisoblab) toping.

5 ning istalgan darajasi oxiri har doim 5 ($T=1$), $5^{100}$ oxiri ham 5, davr=4 deb 100 mod 4 hisoblashning hojati yo'q.

❌ a≡b \pmod{m} va c≡d \pmod{m} dan $a/c≡b/d \pmod{m}$ ni to'g'ridan-to'g'ri xulosa chiqarish.

Bo'lish taqqoslashlarda umumiy holda SAQLANMAYDI — faqat $EKUB(c,m)=1$ bo'lgan maxsus holatlarda muayyan shartlar bilan ishlaydi.

✅ Taqqoslashlar bilan faqat qo'shish, ayirish, ko'paytirish (va musbat butun darajaga ko'tarish) amallarini erkin bajaring; bo'lish uchun alohida (teskari element) usul kerak.

$6≡2 \pmod{4}$ va $3≡3 \pmod{4}$, lekin $6/3=2$ va $2/3$ butun son emas — to'g'ridan-to'g'ri bo'lish ma'nosiz.

Noto'g'ri tasavvurlar

'$\equiv$' (taqqoslash) va '$=$' (tenglik) bir xil narsa degan tasavvur.

$\equiv$ FAQAT qoldiqning bir xilligini bildiradi, sonlarning o'zi teng emas. 17$\equiv$2 (mod 5) to'g'ri, lekin 17$\neq$2. Taqqoslash — 'cheksiz ko'p sonlarni bitta guruhga' birlashtiruvchi kengroq munosabat.

'Har qanday sonning darajasi oxir-oqibat 0 ga tugaydi (kichrayib boradi)' degan noto'g'ri tasavvur.

Oxirgi raqam faqat DAVRIY takrorlanadi, 0 ga 'tugamaydi' (agar asosning o'zi 0 yoki 5 bilan tugamasa). Masalan $2$ ning darajalari hech qachon 0 bilan tugamaydi — doim 2,4,8,6 orasida aylanadi.

'$\tau(n)$ oxirgi raqamni topish uchun har doim to'liq sonni hisoblash kerak' degan tasavvur.

Aynan shu — bu mavzuning asosiy maqsadi — buni RAD ETADI: davriylikdan foydalanib, hatto million $xona$li son uchun ham oxirgi raqamni to'liq hisoblamasdan, faqat kichik modul bo'yicha hisoblash orqali topish mumkin.

Amaliy qo'llanilishi

Kalendar va vaqt hisob-kitoblari

Haftaning kunini, oyning necha kunligini, taqvimdagi takrorlanuvchi hodisalarni hisoblash to'g'ridan-to'g'ridan $7$ yoki $12$ moduli bo'yicha taqqoslashga asoslangan.

Tekshiruv raqamlari (checksum)

Bank kartalari (Luhn algoritmi), ISBN kitob raqamlari, IBAN bank hisob raqamlari — barchasi xatolarni aniqlash uchun modular arifmetikaga asoslangan $tekshiruv\ raqamidan$ foydalanadi.

Kriptografiya

RSA va boshqa zamonaviy shifrlash algoritmlari katta $a^b \bmod m$ darajali sonlarning modul bo'yicha qoldig'ini (modular exponentiation) tez hisoblashga tayanadi — aynan shu mavzudagi g'oyaning kengaytirilgan, kuchliroq versiyasi.

2 ning darajalari — oxirgi raqam aylanasi

2486 2ⁿ oxirgi raqami (davr T=4)

2¹→2, 2²→4, 2³→8, 2⁴→6, 2⁵→2, ... — davr uzunligi 4 bo'lgan aylanma naqsh.

Xulosa

$a \equiv b \pmod{m}$ — $a$ va $b$ bir xil songa ($m$) bo'linganda bir xil qoldiq beradi. Taqqoslashlar qo'shish, ayirish va ko'paytirishga nisbatan saqlanadi (lekin bo'lishga nisbatan EMAS). Sonning oxirgi raqami — uning $10 \bmod$ qiymati. Darajalarning oxirgi raqami har doim davriy (davr uzunligi odatda 1, 2 yoki 4), bu esa $n^k$ ning oxirgi raqamini $k$ ni davr uzunligiga bo'lgandagi qoldiq orqali tezkor topish imkonini beradi.

Modular arifmetika tili keyinchalik "Kombinatorika va ehtimollar nazariyasi" hamda yuqori darajadagi trigonometrik va ko'rsatkichli tenglamalar mavzularida davriylik tahlili sifatida qayta uchraydi. Bevosita amaliy davomi — "Oddiy kasrlar va ular ustida amallar" mavzusida davriy o'nli kasrlarni tushunishda ham shu g'oya ishlatiladi.

Bog'liq mavzular

Oldin bilishingiz kerak: Natural sonlar va ular ustida amallar

Bog'liq mavzular: Bo'linish belgilari, tub va murakkab sonlar, Bo'linuvchanlik. Sonning natural bo'luvchilar soni va yig'indisi

Manbalar

Shu mavzudagi savollar

235 sonini 16 ga bo'lgandagi bo'linma va qoldiqni toping. 444 sonini 44 ga bo'lgandagi bo'linma va qoldiqni toping. 590 sonini 15 ga bo'lgandagi bo'linma va qoldiqni toping. 125 sonini qandaydir songa bo'lganda bo'linma 15 ga, qoldiq esa 5 ga teng bo'ldi. Bo'luvchini toping. 169 sonini qandaydir songa bo'lganda bo'linma 10 ga, qoldiq esa 9 ga teng bo'ldi. Bo'luvchini toping. 327 sonini qandaydir songa bo'lganda bo'linma 18 ga, qoldiq esa 3 ga teng bo'ldi. Bo'luvchini toping.
Ro'yxatdan o'tib, mashq qilishni boshlang