Arifmetikaning asosiy teoremasi

Asosiy faktorizatsiya qilishning o'ziga xosligi
Keling, faktorlar tartibidan tashqari bu parchalanish noyob ekanligini tekshirib ko'raylik. $ N $ ikki yo'l bilan yozilishi mumkin deylik:
n = p₁.p₂.p₃ ... p_r = q_1.nima₂.q₃… ..Q_s (r ≤ s bilan)
Albatta bu₁, nima₂, nima₃... ham oddiy sonlar. P sifatida₁ ajratish (q_1.nima₂.q₃… ..Q_s) Keyin p₁ har qanday "q" ga teng, bu muhim emas bunga, shuning uchun p₁ = q₁. Biz n ni p ga ajratamiz₁ va biz quyidagilarni olamiz:
p₂.p₃ ... p_r =_.nima₂.q₃… ..Q_s
Biz hamma narsani p ga bo'lmagunimizcha protsedurani takrorlaymiz_r, keyin olamiz:
1 = q_{r + 1} ... nima_s
Ammo nimaga erishish mumkin emas_{r + 1} ... nima_s R Ilovalar
Avval aytib o'tganimizdek, asosiy sonlar, agar xohlasangiz, raqamlarning atomlarini, ularning asosiy tarkibiy qismlarini ifodalaydi. Shunday qilib, arifmetikaning asosiy teoremasi juda ko'p qo'llanmalarga ega, eng ravshan: agar biz ularni kichikroq sonlar hosilasi sifatida ifodalasak, biz katta sonlar bilan osonroq ishlashimiz mumkin.
Xuddi shu tarzda, biz eng katta umumiy ko'paytmani (LCM) va eng katta umumiy bo'luvchini (GCF) topishimiz mumkin, bu bizga kasrlarning yig'indisini osonroq qilish, ko'p sonli ildizlarni topish yoki radikallar bilan ishlash, ratsionalizatsiya qilish va echishga yordam beradi. juda xilma-xil xarakterdagi dastur muammolari.
Bundan tashqari, oddiy sonlar juda sirli. Ularda naqsh hali tan olinmagan va keyingi nima bo'lishini bilish mumkin emas. Hozirgacha eng kattasi kompyuterlar tomonidan topilgan va mavjud 24.862.048raqamlar, garchi yangi tub sonlar har safar kam uchraydi.
Yevklid algoritmi qadamlari:

1. 
   Ikkita sondan kattasini kichigiga bo’lib qoldiq olamiz.
   
2. 
   Ularni o’rnini almashtiramiz
   
3. 
   1- va 2-qadamlarni sonlardan biri nol bo’lib qolguncha davom ettiramiz
   
4. 
   Qolgan son shu ikki son uchun EKUB bo’ladi.
   

Algoritm implementatsiyasi videosiga o'tishdan oldin. Uning dasturini o'zingiz mustaqil yozib ko'rishni maslahat beramiz.
Yevklid algoritmi qay tarzda ishlaydi. (Geometrik tushuntirish)
Bilamizki, Yevklid geometriya fani olimi bo'lgan shuning uchun u yaratgan algoritmni geometriya orqali tushuntirib berishga harakat qilamiz.
Misol: 38 va 16 sonlarining EKUBini Yevklid algoritmi yordamida toping.
Keling tomonlari 38 va 16 bo'lgan to'g'ri to'rtburchak chizib olamiz.

Endi bu to'rtburchakdan tomoni 16 ga teng bo'lgan kvadratlarni ajratib olamiz.

Bu narsa bizga 38 ni 16 ga bo'lgandagi butun va qoldiq qismni vizual ko'rsatib beradi. Ya'ni:

O'ng tarafdagi bo'yalmagan qism bizdagi qoldiqni (6) ifodalaydi. Endi yuqoridagi ishni o'sha 16 ga 6 tomonli to'g'ri to'rtburchak uchun davom ettiramiz.

Huddi yuqoridagidek:

Shu tarzda qoldiq nolga tenglashguncha davom etamiz.




Shu joyda algoritm o'z ishini yakunlaydi va eng kichik kvadrat tomoni (2) bizga 38 va 16 uchun EKUBni beradi.
Bu holatda tomoni to'g'ri to'rtburchak tomonlari EKUBiga teng bo'lgan kvadrat shu to'g'ri to'rtburchakning barcha sohasini to'ldirib chiqa oladigan eng katta tomonli kvadrat.