История появления натуральных чисел и нуля. Теоретико-множественное определение натурального числа и нуля. Теоретико-множественное определение сложения и разности целых неотрицательных чисел. Свойства сложения


Нахождение НОД трех и большего количества чисел



Download 1,03 Mb.
bet59/60
Sana21.02.2022
Hajmi1,03 Mb.
#40272
TuriЛекция
1   ...   52   53   54   55   56   57   58   59   60
Bog'liq
Лекция1

Нахождение НОД трех и большего количества чисел


Нахождение наибольшего общего делителя трех и большего количества чисел может быть сведено к последовательному нахождению НОД двух чисел. Мы об этом упоминали, при изучении свойств НОД. Там мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2,НОД(d2, a3)=d3НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.
Давайте разберемся, как выглядит процесс нахождения НОД нескольких чисел, рассмотрев решение примера.
Пример.
Найдите наибольший общий делитель четырех чисел 78294570 и 36.
Решение.
В этом примере a1=78a2=294a3=570a4=36.
Сначала по алгоритму Евклида определим наибольший общий делитель d2двух первых чисел 78 и 294. При делении получаем равенства 294=78·3+60;78=60·1+1860=18·3+6 и 18=6·3. Таким образом, d2=НОД(78, 294)=6.
Теперь вычислим d3=НОД(d2, a3)=НОД(6, 570). Опять применим алгоритм Евклида: 570=6·95, следовательно, d3=НОД(6, 570)=6.
Осталось вычислить d4=НОД(d3, a4)=НОД(6, 36). Так как 36 делится на 6, тоd4=НОД(6, 36)=6.
Таким образом, наибольший общий делитель четырех данных чисел равенd4=6, то есть, НОД(78, 294, 570, 36)=6.
Ответ:
НОД(78, 294, 570, 36)=6.
Разложение чисел на простые множители также позволяет вычислять НОД трех и большего количества чисел. В этом случае наибольший общий делитель находится как произведение всех общих простых множителей данных чисел.
Пример.
Вычислите НОД чисел из предыдущего примера, используя их разложения на простые множители.
Решение.
Разложим числа 78294570 и 36 на простые множители, получаем 78=2·3·13,294=2·3·7·7570=2·3·5·1936=2·2·3·3. Общими простыми множителями всех данных четырех чисел являются числа 2 и 3. Следовательно,НОД(78, 294, 570, 36)=2·3=6.
Ответ:
НОД(78, 294, 570, 36)=6.

Download 1,03 Mb.

Do'stlaringiz bilan baham:
1   ...   52   53   54   55   56   57   58   59   60




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish