MathTest.uz
Algebra

Sonlarni tub ko'paytuvchilarga ajratish, EKUB va EKUK

boshlangich 55 daqiqa tub ko'paytuvchilarga ajratishEKUBEKUKYevklid algoritmio'zaro tub sonlar

Nima uchun muhim?

Har qanday oddiy kasrni qisqartirish, ikkita kasrni umumiy maxrajga keltirish, yoki "har 12 kunda avtobus, har 18 kunda poyezd keladi — ikkalasi qachon bir kunda kelishadi" turidagi masalalarni yechish — bularning barchasi bitta g'oyaga tayanadi: sonni "tub ko'paytuvchilar" ko'rinishida yoyish. $EKUB$ (eng katta umumiy bo'luvchi) va $EKUK$ (eng kichik umumiy karrali) — matematikaning eng amaliy ikkita tushunchasi bo'lib, ular "Oddiy kasrlar va ular ustida amallar" mavzusida bevosil ishlatiladi (kasrni qisqartirish uchun $EKUB$, umumiy maxraj uchun $EKUK$ kerak).

O'quv maqsadlari

  • Sonni tub ko'paytuvchilarga (daraxt yoki ustunlab usulida) ajrata olish
  • $EKUB$ va $EKUK$ ni tub ko'paytuvchilar yoyilmasi orqali topa olish (minimal/maksimal daraja qoidasi)
  • Yevklid algoritmini (ketma-ket qoldiqli bo'lish) $EKUB$ topishning tezkor usuli sifatida qo'llay olish
  • $EKUB(a,b) \times EKUK(a,b) = a \times b$ bog'lanishidan foydalanib, biridan ikkinchisini hisoblay olish
  • O'zaro tub (coprime) sonlar tushunchasini bilish va $EKUB=1$ shartini tanish
1900-yillar boshida Yevklid "Elementlar" asarida sonlarning eng katta umumiy bo'luvchisini topishning ajoyib samarali usulini keltirgan — bu usul bugungi kunda ham kompyuter algoritmlarida ishlatiladi. Ikki yoki undan ortiq sonning $EKUB$ (eng katta umumiy bo'luvchi, ba'zi manbalarda GCD/HCF deb ham ataladi) — ularning barchasiga qoldiqsiz bo'linadigan eng katta son. $EKUK$ (eng kichik umumiy karrali, LCM) esa — barcha berilgan sonlarning har biriga qoldiqsiz bo'linadigan eng kichik son. Bu ikki miqdorni topishning ikkita asosiy usuli bor: (1) har bir sonni tub ko'paytuvchilarga ajratib, $EKUB$ uchun umumiy tub ko'paytuvchilarning eng kichik darajalarini, $EKUK$ uchun esa uchraydigan barcha tub ko'paytuvchilarning eng katta darajalarini olish; (2) Yevklid algoritmi — katta sonlar uchun ancha tezroq, faqat $EKUB$ uchun to'g'ridan-to'g'ri ishlaydi ($EKUK$ esa $EKUB \times EKUK = a \times b$ formulasi orqali topiladi).

Ta'riflar

Tub ko'paytuvchilarga ajratish

$n$ natural sonni ($n>1$) tub sonlarning ko'paytmasi $n=p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k}$ ko'rinishida (arifmetikaning asosiy teoremasiga ko'ra YAGONA tarzda) ifodalash.

Sonni eng kichik 'g'ishtlar' — tub sonlarga — bo'lib chiqish.

Misol: $60 = 2^2\times 3\times 5$

Bu emas: $60=4\times 15$ — bu yoyilma emas, chunki 4 tub son emas.

💡 Yoyilmani topishning ikki keng tarqalgan usuli: 'faktor daraxti' (factor tree) va ustunlab ketma-ket bo'lish.

EKUB (eng katta umumiy bo'luvchi)

$a$ va $b$ sonlarining $\mathrm{EKUB}(a,b)$ — ikkalasiga ham qoldiqsiz bo'linadigan barcha umumiy bo'luvchilar orasidagi ENG KATTASI.

Ikki (yoki undan ortiq) sonni bab bo'linadigan eng katta son.

Misol: $\mathrm{EKUB}(12,18)=6$ (12 ning bo'luvchilari: 1,2,3,4,6,12; 18 niki: 1,2,3,6,9,18; umumiylari: 1,2,3,6; eng kattasi 6).

Bu emas: $\mathrm{EKUB}(12,18) \neq 3$ — 3 umumiy bo'luvchi, lekin eng katta emas.

💡 Xalqaro adabiyotda GCD (Greatest Common Divisor) yoki HCF (Highest Common Factor) deb ham ataladi.

EKUK (eng kichik umumiy karrali)

$a$ va $b$ sonlarining $EKUK(a,b)$ — ikkalasiga ham qoldiqsiz boʻlinuvchi barcha umumiy karralilar orasidagi eng kichigi.

Ikki (yoki undan ortiq) sonning har biriga boʻlinadigan eng kichik musbat son.

Misol: $EKUB(4,6)=12$ (4 ning karralilari: 4,8,12,16...; 6 niki: 6,12,18...; eng kichik umumiysi 12).

Bu emas: $EKUK(4,6)\neq 24$ — 24 umumiy karrali, lekin eng kichigi emas.

💡 Xalqaro adabiyotda LCM (Least Common Multiple) deb ataladi; kasrlarda umumiy maxraj topishda ishlatiladi.

Fundamental tushunchalar

Faktor daraxti (factor tree) usuli

Sonni ikkita bo'luvchiga ajratib, har birini yana ajratib, tub songa yetguncha davom etiladi — natijada daraxtsimon tuzilma hosil bo'ladi, uning 'barglari' tub ko'paytuvchilardir.

$6\times 10\to (2\times 3)\times (2\times 5) = 2^{2}\times 3\times 5$

Qaysi tartibda ajratmang ($60=6\times 10$ yoki $60=4\times 15$ dan boshlasangiz ham), oxirgi tub ko'paytuvchilar to'plami BIR XIL bo'ladi — bu arifmetikaning asosiy teoremasining natijasi.

EKUB va EKUKni yoyilma orqali topish

Ikkala son tub ko'paytuvchilarga ajratilgandan so'ng: $EKUB$ uchun — faqat IKKALASIDA HAM uchraydigan tub sonlarni, eng kichik darajasida olib ko'paytiriladi. $EKUK$ uchun — uchraydigan BARCHA tub sonlarni (ikkalasida ham, yoki faqat birida), eng katta darajasida olib ko'paytiriladi.

$a=2^{2} \times 3 \times 5, \quad b=2 \times 3^{2} \times 7 \text{ bo'lsagina: } \operatorname{EKUB}=2^{1} \times 3^{1}=6, \quad \operatorname{EKUK}=2^{2} \times 3^{2} \times 5 \times 7$

Bu usul 3 va undan ortiq son uchun ham to'g'ridan-to'g'ri kengaytiriladi.

Yevklid algoritmi

$EKUB(a,b)$ ni topishning tezkor rekursiv usuli: $a$ va $b$ ($a>b$) berilganda, $a$ ni $b$ ga bo'lib qoldiq $r$ ni topamiz, so'ng $EKUB(a,b)=EKUB(b,r)$ ekanidan foydalanib jarayonni takrorlaymiz, toki qoldiq $0$ bo'guncha — oxirgi nolmas qoldiq (yoki oxirgi bo'luvchi) $EKUB$ bo'ladi.

$\operatorname{EKUB}(a, b) = \operatorname{EKUB}\left(b, a \bmod b\right), \operatorname{EKUB}(a, 0) = a$

Bu algoritm katta sonlar (masalan minglab raqamli) uchun ham juda tez ishlaydi — tub ko'paytuvchilarga ajratishdan ancha samaraliroq, chunki katta sonlarni faktorlashtirish o'zi qiyin masala.

O'zaro tub sonlar (coprime numbers)

Agar ikkita sonning $EKUB(a,b)=1$ bo'lsa, ular o'zaro tub (coprime yoki relatively prime) deyiladi — ularning umumiy tub ko'paytuvchisi yo'q, garchi ikkalasi ham tub son bo'lmasligi mumkin.

$\operatorname{EKUB}(a,b)=1 \iff a,b \text{ o'\zaro tub}$

8 va 9 o'zaro tub (garchi ikkalasi ham murakkab son bo'lsa ham), chunki 8=2³, 9=3², umumiy tub ko'paytuvchi yo'q.

Formula kutubxonasi

EKUB va EKUK orasidagi bog'lanish

$$\text{EKUB}(a,b) \times \text{EKUK}(a,b) = a \times b$$
  • $a,b$ — ixtiyoriy ikkita musbat butun son

Agar EKUB ma'lum bo'lsa, EKUKni bo'lish orqali (yoki aksincha) tezda topish mumkin.

Shart: Faqat IKKITA son uchun to'g'ri (uch va undan ortiq son uchun bu tenglik to'g'ridan-to'g'ri o'rinli emas).

Xususiy holatlar: Agar a,b o'zaro tub bo'lsa (EKUB=1), EKUK=a×b bo'ladi.

Yevklid algoritmi (rekursiv formula)

$$\text{EKUB}(a,b) = \text{EKUB}(b,\ a \bmod b), \quad \text{EKUB}(a,0)=a$$
  • $a mod b$ — a ni b ga bo'lgandagi qoldiq

Katta ikkita sonning EKUBini kichikroq sonlar juftligiga qisqartirib boradi.

Shart: b>0; jarayon qoldiq 0 bo'lguncha takrorlanadi.

Xususiy holatlar: EKUB(a,0)=a — bazaviy holat.

Teoremalar va isbotlar

📐 $EKUB\times EKUK=a\times b$ teoremasi

Ixtiyoriy ikkita musbat butun $a$,$b$ sonlar uchun $EKUB(a,b)\times EKUK(a,b)=a\times b$.

$EKUB$ 'kichraytiradi', $EKUK$ 'kattalashtiradi' — ularning ko'paytmasi doim asl sonlar ko'paytmasiga teng bo'lib qoladi.

Isbotni ko'rsatish

Berilgan: $a=p_1^{x_1} \times p_2^{x_2} \times \dots \times p_k^{x_k}$, $b=p_1^{y_1} \times p_2^{y_2} \times \dots \times p_k^{y_k}$ (bir xil tub sonlar ro'yxati bilan, ba'zi darajalar 0 bo'lishi mumkin).

Isbotlash kerak: $EKUB(a,b) \times EKUK(a,b)=a \times b$

  1. $EKUB(a,b)$ ta'rifiga ko'ra har bir $p_i$ uchun $\min(x_i,y_i)$ darajasida olinadi: $EKUB=\prod p_i^{\min(x_i,y_i)}$.
  2. $EKUK(a,b)$ ta'rifiga ko'ra har bir $p_i$ uchun $\max(x_i,y_i)$ darajasida olinadi: $EKUK=\prod p_i^{\max(x_i,y_i)}$.
  3. $EKUB \times EKUK=\prod p_i^{(\min(x_i,y_i)+\max(x_i,y_i))}$
  4. Har qanday ikkita $x,y$ son uchun $\min(x,y)+\max(x,y)=x+y$ (bu — ikkita son yig'indisining oddiy xossasi: qaysi biri kichik, qaysi biri katta bo'lishidan qat'i nazar, ularning yig'indisi o'zgarmaydi).
  5. Demak $EKUB \times EKUK=\prod p_i^{(x_i+y_i)}=\prod p_i^{x_i} \times \prod p_i^{y_i}=a \times b$

Demak $EKUB(a,b) \times EKUK(a,b)=a \times b$. ∎

📐 Yevklid algoritmining to'g'riligi

Ixtiyoriy $a>b>0$ butun sonlar uchun $EKUB(a,b)=EKUB(b, a \bmod b)$.

Katta juftlikning 'umumiy bo'luvchilar to'plami' kichikroq juftlikning umumiy bo'luvchilar to'plami bilan bir xil bo'lib qoladi.

Isbotni ko'rsatish

Berilgan: $a>b>0$ — butun sonlar, $r = a \bmod b$ ($a=bq+r$, $0\le r<b$).

Isbotlash kerak: $EKUB(a,b)=EKUB(b,r)$

  1. $d$ soni $a$ va $b$ ning umumiy bo'luvchisi bo'lsin. U holda $d \mid a$ va $d \mid b$.
  2. $r=a-bq$ bo'lgani uchun, $d \mid a$ va $d \mid bq$ (chunki $d\mid b$) dan $d \mid (a-bq)=r$ kelib chiqadi. Demak $d$ — $b$ va $r$ ning ham umumiy bo'luvchisi.
  3. Aksincha, $e$ soni $b$ va $r$ ning umumiy bo'luvchisi bo'lsin: $e\mid b$, $e\mid r$. U holda $a=bq+r$ dan $e\mid bq$ va $e\mid r$, demak $e\mid(bq+r)=a$. Demak $e$ — $a$ va $b$ ning ham umumiy bo'luvchisi.
  4. Shunday qilib, $\{a,b\}$ juftligining umumiy bo'luvchilari to'plami va $\{b,r\}$ juftligining umumiy bo'luvchilari to'plami AYNAN BIR XIL.
  5. Ikki to'plam bir xil bo'lgani uchun ularning eng kattasi (EKUB) ham bir xil: $EKUB(a,b)=EKUB(b,r)$.

Demak, $EKUB(a,b)=EKUB(b, a \bmod b)$ — Yevklid algoritmining har bir qadami EKUBni saqlaydi, jarayon esa chekli, chunki qoldiqlar ketma-ket kamayib boradi. ∎

Yechilgan misollar

oson 36 sonini tub ko'paytuvchilarga ajrating.

💡 Maslahat: Eng kichik tub son 2 dan boshlab ketma-ket bo'ling.

  1. $36 \div 2 = 18$
  2. $18 \div 2 = 9$
  3. $9 \div 3 = 3$
  4. $3 \div 3 = 1$

✅ Javob: $36 = 2^2 \times 3^2$

Nega bu usul ishlaydi: Ketma-ket eng kichik tub songa bo'lish yoyilmani sistematik topadi.

Muqobil usul: Faktor daraxti: $36=6 \times 6 = (2 \times 3) \times (2 \times 3) = 2^2 \times 3^2$.

⚠️ Yoyilmani to'liq tugatmasdan (masalan $36=4 \times 9$ darajasida) to'xtatib qo'yish — 4 va 9 hali tub emas.

oson $EKUB(8,12)$ va $EKUK(8,12)$ ni bo'luvchilar/karralilarni sanab toping.

💡 Maslahat: 8 va 12 ning bo'luvchilari va dastlabki karralilarini yozing.

  1. 8 bo'luvchilari: 1,2,4,8. 12 bo'luvchilari: 1,2,3,4,6,12. Umumiylari: 1,2,4 — eng kattasi 4.
  2. 8 karralilari: 8,16,24,32... 12 karralilari:12,24,36... Umumiy eng kichigi: 24.

✅ Javob: $EKUB(8,12)=4$, $EKUK(8,12)=24$

Nega bu usul ishlaydi: To'g'ridan-to'g'ri sanash kichik sonlar uchun tushunarli va ishonchli.

Muqobil usul: Tekshirish: $EKUB \times EKUK=4 \times 24=96=8 \times 12$ ✓

⚠️ EKUB va EKUKni chalkashtirib, EKUBni 'eng kichik', EKUKni 'eng katta' deb noto'g'ri eslab qolish.

ortacha $EKUB(84,126)$ ni tub ko'paytuvchilarga ajratish orqali toping.

💡 Maslahat: Ikkalasini ham to'liq yoying, so'ng umumiy tub ko'paytuvchilarning eng kichik darajasini oling.

  1. $84=2^2 \times 3 \times 7$
  2. $126=2 \times 3^2 \times 7$
  3. Umumiy tub ko'paytuvchilar: $2$,$3$,$7$
  4. Eng kichik darajalar: $2^1$, $3^1$, $7^1$

✅ Javob: $EKUB(84,126)=2 \times 3 \times 7=42$

Nega bu usul ishlaydi: Yoyilma orqali usul har qanday kattalikdagi son uchun tizimli ishlaydi.

Muqobil usul: Yevklid algoritmi: $126=84 \times 1+42$, $84=42 \times 2+0$, demak $EKUB=42$ (tezroq).

⚠️ $2$ sonining darajasini $\min(2,1)=1$ emas, ikkalasidan birini (masalan $2^2$ ni) olib qo'yish.

ortacha $EKUK(18,24,30)$ ni toping (uchta son).

💡 Maslahat: Har birini yoying, so'ng uchraydigan barcha tub ko'paytuvchilarning eng katta darajasini oling.

  1. $18=2×3^2$
  2. $24=2^3×3$
  3. $30=2×3×5$
  4. Uchraydigan tub sonlar: 2,3,5. Eng katta darajalar: $2^3$,$3^2$,$5^1$

✅ Javob: $EKUK=8×9×5=360$

Nega bu usul ishlaydi: Yoyilma usuli ikkitadan ortiq son uchun ham to'g'ridan-to'g'ri kengaytiriladi (Yevklid algoritmidan farqli, u faqat ikkita son uchun to'g'ridan-to'g'ri qo'llanadi).

Muqobil usul: Juft-jufti bilan: avval $EKUK(18,24)=72$, keyin $EKUK(72,30)=360$.

⚠️ 5 tub ko'paytuvchisini (u faqat 30 da bor) $EKUK$ hisobiga qo'shishni unutib qoldirish.

ortacha Yevklid algoritmi bilan $EKUB(252,105)$ ni toping.

💡 Maslahat: Ketma-ket qoldiqli bo'lishni qo'llang: $EKUB(a,b)=EKUB(b,a \bmod b)$.

  1. $252=105 \times 2 + 42$
  2. $105=42 \times 2 + 21$
  3. $42=21 \times 2 + 0$
  4. Qoldiq 0 bo'lgani uchun, oxirgi nolmas qoldiq (bo'luvchi) 21 — $EKUB$.

✅ Javob: $EKUB(252,105)=21$

Nega bu usul ishlaydi: Har bir qadamda $EKUB$ saqlanadi (isbotga qarang), jarayon chekli, chunki qoldiqlar qat'iy kamayib boradi.

Muqobil usul: Tub ko'paytuvchilar: $252=2^2 \times 3^2 \times 7$, $105=3 \times 5 \times 7$, $EKUB=3 \times 7=21$ (mos keladi).

⚠️ Bo'lish tartibini teskari qilib ($105$ ni $252$ ga bo'lib) chalkashtirib yuborish.

murakkab Ikki avtobus bekatdan bir vaqtda jo'nadi: birinchisi har $18$ daqiqada, ikkinchisi har $24$ daqiqada qaytib keladi. Ular yana qachon bir vaqtda bekatga qaytib kelishadi (necha daqiqadan keyin)?

💡 Maslahat: Bu — $EKUK$ masalasi: $EKUK(18,24)$ qancha vaqtdan keyin ikkalasi ham 'karrali' nuqtaga tushadi.

  1. $18=2\times 3^{2}$, $24=2^{3}\times 3$
  2. $EKUK=2^{3}\times 3^{2}=8\times 9=72$

✅ Javob: $72$ daqiqadan keyin (ya'ni $1$ soat $12$ daqiqadan so'ng) ikkalasi yana bir vaqtda keladi.

Nega bu usul ishlaydi: Davriy takrorlanadigan ikki hodisaning 'bir vaqtga tushishi' har doim $EKUK$ bilan aniqlanadi.

Muqobil usul: Yevklid orqali $EKUB(18,24)=6$ topib, $EKUK=18\times 24/6=72$ formulasidan foydalanish.

⚠️ $EKUK$ o'rniga $EKUB$ ($6$ daqiqa) ni javob deb yozib qo'yish — bu masala turini chalkashtirish.

murakkab 120 va 84 sonlarining $EKUB$ va $EKUK$ini toping, so'ng $EKUB\times EKUK=a\times b$ tengligini tekshirib tasdiqlang.

💡 Maslahat: Avval ikkalasini yoying, $EKUB$ va $EKUK$ni toping, keyin tekshiring.

  1. $120=2^3\times 3\times 5$
  2. $84=2^2\times 3\times 7$
  3. $EKUB=2^2\times 3=12$
  4. $EKUK=2^3\times 3\times 5\times 7=840$
  5. Tekshirish: $EKUB\times EKUK=12\times 840=10080$. $a\times b=120\times 84=10080$ ✓

✅ Javob: $EKUB=12$, $EKUK=840$, va $12\times 840=120\times 84=10080$ — tenglik tasdiqlandi.

Nega bu usul ishlaydi: $\min+\max=$yig'indi xossasi bu bog'lanishni har doim kafolatlaydi.

Muqobil usul: $EKUB$ni Yevklid algoritmi bilan tezroq topib ($12$), so'ng $EKUK=\frac{a\times b}{EKUB}=\frac{10080}{12}=840$ deb hisoblash.

⚠️ Yoyilmada biror tub ko'paytuvchini (masalan $7$ ni, u faqat $84$ da bor) $EKUK$ hisobida unutib qoldirish.

murakkab n va $n+1$ (ikkata ketma-ket natural son) har doim o'zaro tub ekanini isbotlang.

💡 Maslahat: $EKUB(n,n+1)$ ni Yevklid algoritmi mantig'i bilan baholang.

  1. Faraz qilaylik, $d = EKUB(n, n+1)$
  2. $d \mid n$ va $d \mid (n+1)$
  3. Demak $d \mid [(n+1)-n] = d \mid 1$
  4. Faqat 1 soni 1 ga bo'linadi, demak $d=1$

✅ Javob: $EKUB(n,n+1)=1$ — ular har doim o'zaro tub. ∎

Nega bu usul ishlaydi: Ikki sonning umumiy bo'luvchisi ularning AYIRMASINI ham bo'lishi kerak — bu Yevklid algoritmining asosiy mantiqiy printsipi.

Muqobil usul: Tub ko'paytuvchilar orqali: $n$ va $n+1$ hech qachon umumiy tub ko'paytuvchiga ega bo'la olmaydi, chunki ular orasidagi ayirma 1.

⚠️ Faqat bitta misolda (masalan 4,5) tekshirib, umumiy holat uchun ham 'isbotlandi' deb noto'g'ri xulosa chiqarish.

olimpiada EKUB(a,b)=15 va EKUK(a,b)=180 boʻlsa, a va b ning barcha mumkin boʻlgan juftliklarini toping (a<b).

💡 Maslahat: EKUB×EKUK=a×b dan a×b=2700 ni toping, soʻng a=15m, b=15n (m,n o'zaro tub) koʻrinishida qidiring.

  1. EKUB×EKUK=15×180=2700=a×b
  2. a=15m, b=15n deb yozamiz, bu yerda EKUB(m,n)=1 (o'zaro tub) shart.
  3. 15m×15n=2700 → mn=12
  4. mn=12 va EKUB(m,n)=1 shartini qanoatlantiruvchi (m,n) juftliklarini qidiramiz: (1,12),(3,4) — bular o'zaro tub. (2,6) va (4,3) kabi variantlar EKUB(m,n)≠1 boʻlgani uchun (masalan EKUB(2,6)=2) chiqarib tashlanadi, (3,4) esa (4,3) bilan bir xil juftlik, faqat tartib farqi.
  5. m=1,n=12: a=15,b=180. m=3,n=4: a=45,b=60.

✅ Javob: $(a,b) \in \{(15,180), (45,60)\}$

Nega bu usul ishlaydi: EKUB va EKUKni 'normallashtirish' (a=EKUB×m koʻrinishida yozish) orqali masala kichikroq o'zaro tub sonlar juftligini topishga qisqaradi — bu klassik son nazariyasi texnikasi.

Muqobil usul: Barcha 2700 ning boʻluvchilar juftliklarini sanab, har birida EKUB=15 shartini tekshirish (sekinroq).

⚠️ mn=12 ning BARCHA boʻluvchilar juftligini (masalan (2,6)) ham javob deb qoʻshib yuborish — EKUB(m,n)=1 shartini tekshirmasdan.

olimpiada 1 dan 20 gacha bo'lgan barcha natural sonlarning $EKUK$ini toping.

💡 Maslahat: Har bir tub songa mos eng katta darajani (20 dan oshmaydigan) aniqlang.

  1. 20 gacha bo'lgan tub sonlar: 2,3,5,7,11,13,17,19
  2. Har biri uchun 20 dan oshmaydigan eng katta darajasini topamiz: $2^4=16\le20<32=2^5$ → $2^4$; $3^2=9\le20<27=3^3$ → $3^2$; $5^1=5\le20<25=5^2$ → $5^1$; 7,11,13,17,19 — har biri faqat birinchi darajada (chunki kvadratlari 20 dan katta)
  3. $EKUK=2^4 imes3^2 imes5 imes7 imes11 imes13 imes17 imes19$

✅ Javob: $EKUK(1..20) = 16 imes9 imes5 imes7 imes11 imes13 imes17 imes19 = 232792560$

Nega bu usul ishlaydi: 1 dan 20 gacha bo'lgan har qanday songa bo'linadigan eng kichik son — har bir tub darajaning 20 ichida 'yeta oladigan' eng kattasini o'z ichiga olishi kerak.

Muqobil usul: Ketma-ket $EKUK(EKUK(...EKUK(1,2),3)...,20)$ — juft-jufti bilan hisoblash.

⚠️ Har bir tub sonni faqat BIRINCHI darajada olish (masalan $2^1$ yoki $3^1$), $2^4$ va $3^2$ kabi yuqoriroq, lekin 20 ichida 'sig'adigan' darajalarni e'tiborsiz qoldirish.

Umumiy xatolar

❌ EKUB topishda umumiy tub ko'paytuvchilarning ENG KATTA darajasini olish (EKUK bilan aralashtirib yuborish).

EKUB uchun ENG KICHIK umumiy daraja, EKUK uchun ENG KATTA daraja olinishi kerak — bu ikkalasi teskari qoida.

✅ EKUB=$\min$ daraja, EKUK=$\max$ daraja qoidasini alohida-alohida eslab qoling (masalan, 'EKUB — kichraytiradi, shuning uchun kichik daraja' deb yodlash).

a=2^3×3, b=2×3^2: EKUB=2^1×3^1=6 ($\min$), EKUK=2^3×3^2=72 ($\max$).

❌ $EKUK$ topishda faqat IKKALASIDA HAM uchraydigan tub ko'paytuvchilarni olib, faqat bitta sonda uchraydiganlarini tashlab ketish.

$EKUK$ BARCHA (hech bo'lmasa bittasida uchragan) tub ko'paytuvchilarni o'z ichiga olishi kerak, faqat umumiylarini emas.

✅ Har ikkala sonning barcha tub ko'paytuvchilarini (eng katta darajasida) $EKUK$ka kiriting.

$a=12=2^2 \times 3$, $b=5$ (tub): $EKUK=2^2 \times 3 \times 5=60$, faqat '3' emas.

❌ Yevklid algoritmida bo'lish tartibini (qaysi son $a$ bo'linuvchi, qaysisi $b$ bo'luvchi) e'tiborsiz almashtirib yuborish.

$a \bmod b$ faqat $a > b$ bo'lganda to'g'ri tartibda hisoblanadi; teskari qilinsa qoldiq noto'g'ri chiqadi.

✅ Har doim KATTA sonni KICHIK songa bo'ling, keyin bo'luvchi va qoldiqni yangi juftlik sifatida oling.

$\mathrm{EKUB}(105,252)$: to'g'ri boshlanish $252 = 105 \times 2 + 42$, $105$ ni $252$ ga emas.

Noto'g'ri tasavvurlar

'$EKUB$ va $EKUK$ har doim asl sonlardan biriga teng bo'ladi' degan noto'g'ri tasavvur.

Bu faqat bir son ikkinchisining karralisi bo'lganda to'g'ri (masalan $EKUB(4,8)=4$, $EKUK(4,8)=8$). Umumiy holda $EKUB$ va $EKUK$ ikkala sondan ham farqli bo'lishi mumkin (masalan $EKUB(12,18)=6$, $EKUK(12,18)=36$ — ikkalasi ham 12 va 18 dan farqli).

'$EKUB(a,b)$ doim $EKUK(a,b)$ dan kichik bo'lishi shart emas' — aslida bu to'g'ri, lekin ko'pincha '$EKUB$ har doim $EKUK$dan ancha kichik bo'lishi kerak' deb noto'g'ri kutiladi.

Agar $a=b$ bo'lsa, $EKUB(a,a)=EKUK(a,a)=a$ — ikkalasi TENG bo'ladi. Bu chegaraviy holatni unutmang.

'Uchta son uchun $EKUB\times EKUK=a\times b\times c$ formulasi ishlaydi' degan noto'g'ri umumlashtirish.

$EKUB\times EKUK=a\times b$ formulasi FAQAT IKKITA son uchun to'g'ri. Uch va undan ortiq son uchun bunday oddiy formula YO'Q — $EKUB$/$EKUK$ to'g'ridan-to'g'ri tub ko'paytuvchilar yoyilmasi (min/max daraja) orqali topilishi kerak.

Amaliy qo'llanilishi

Kasrlar bilan ishlash

Kasrni qisqartirishda (surat va maxrajni $EKUB$ga bo'lish) va kasrlarni qo'shish/ayirishda umumiy maxraj ($EKUK$) topishda bevosita ishlatiladi.

Jadval tuzish va rejalashtirish

Turli davriylikdagi hodisalarning (ishlab chiqarish sikllari, transport jadvallari, takrorlanadigan uchrashuvlar) qachon bir vaqtga to'g'ri kelishini aniqlashda $EKUK$ ishlatiladi.

Kompyuter fanlari va kriptografiya

Yevklid algoritmi zamonaviy kriptografik protokollarda (masalan RSA kalitlarini generatsiya qilishda, kengaytirilgan Yevklid algoritmi orqali) va dasturlash tillarining standart kutubxonalarida (gcd funksiyasi) ishlatiladi.

Faktor daraxti: 60 = 2² × 3 × 5

60 6 10 2 3 2 5 60 = 2 × 3 × 2 × 5 = 2² × 3 × 5

60 sonining faktor daraxti — oltin rangdagi barglar tub ko'paytuvchilar.

Xulosa

Tub ko'paytuvchilarga ajratish — sonni $p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}$ ko'rinishida yagona tarzda yoyish. $EKUB$ — umumiy tub ko'paytuvchilarning eng kichik darajalari ko'paytmasi; $EKUK$ — barcha tub ko'paytuvchilarning eng katta darajalari ko'paytmasi. Yevklid algoritmi ($EKUB(a,b) = EKUB(b, a \bmod b)$) katta sonlar uchun eng tezkor usul. Muhim bog'lanish: $EKUB(a,b) \times EKUK(a,b) = a \times b$.

Bu bilim to'g'ridan-to'g'ri "Oddiy kasrlar va ular ustida amallar" mavzusida ishlatiladi: kasrni $EKUB$ bilan qisqartirish, ikki kasrni $EKUK$ yordamida umumiy maxrajga keltirish. Shuningdek, "Bo'linuvchanlik. Sonning natural bo'luvchilar soni va yig'indisi" mavzusi ham xuddi shu tub ko'paytuvchilar yoyilmasidan foydalanadi.

Bog'liq mavzular

Oldin bilishingiz kerak: Bo'linish belgilari, tub va murakkab sonlar

Bog'liq mavzular: Qoldiqli bo'lish. Oxirgi raqam.

Keyingi mavzular: Bo'linuvchanlik. Sonning natural bo'luvchilar soni va yig'indisi, Oddiy kasrlar va ular ustida amallar

Manbalar

Shu mavzudagi savollar

Hisoblang: $0!+1!+2!+3!$ Hisoblang: $2!\cdot 5!$ Hisoblang: $\frac{6!}{240}$ Hisoblang: $\frac{6!}{4!}$ Hisoblang: $\frac{7!}{5!}$ Hisoblang: $\frac{4!+5!}{4!}$
Ro'yxatdan o'tib, mashq qilishni boshlang