Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Нахождение наибольшего общего делителя и наименьшего общего кратного способом разложения на простые множители

Читайте также:
  1. II. Местонахождение и адрес государственной регистрации общества с ограниченной ответственностью при создании
  2. II.3.1. Пункция и катетеризация верхней полой вены через подключичную вену подключичным способом
  3. III. Требования к структуре основной образовательной программы основного общего образования
  4. IV. Требования к условиям реализации основной образовательной программы основного общего образования
  5. XXXVIII. ПОЛЕТЫ АВИАЦИИ ОБЩЕГО НАЗНАЧЕНИЯ
  6. Автопарк ежегодно потребляет 110-120 млн. т кислорода, что составляет 8-10% от его общего воспроизводства на территории страны.
  7. Агрегатная форма общего рынка

Если натуральные числа а и в представлены в каноническом виде, то над ними легко выполнять умножение, деление, возведение в степень.

Пусть ,

.

.

, для aк ≥ b к,при к = 1, 2, …, n.

Из последнего равенства следует, что число d может быть общим делителем чисел а и в лишь в том случае, когда показатель степени каждого простого числа в разложении d не превосходит соответствующих показателей в числах а и в.

Иными словами при условии, что для любого к
(1 ≤ кn) будут выполняться неравенства gк ≤ aк и gк b к. НОД (а, в) – это наибольшее из чисел на которое делятся числа а и в. Значит, для каждого из простых чисел показатель степени в разложении НОД (а, в) должен быть наибольшим из возможных (т.е. удовлетворяющих неравенствам gк ≤ aк и gк b к). Этим показателем является меньшее из чисел aк и b к. Таким образом, чтобы найти НОД чисел, представленных в каноническом виде, достаточно образовать произведение общих всем данным числам простых множителей, каждый с наименьшим показателем, с каким он входит во все разложения данных чисел, и найти его значение.

Аналогично выводится и правило нахождения НОК: чтобы найти НОК чисел, представленных в каноническом виде, достаточно образовать произведение всех простых множителей, находящихся в разложениях данных чисел, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел, и найти его значение.

П р и м е р. Найти НОК и НОД чисел 504 и 132

504 = 23 ·32 · 7; 132 = 22 · 3 ·11.

НОД (504, 132) = 22 · 3 · 70 · 110 =12,

НОК (504, 132) = 23 · 32 · 7 · 11 = 5544.


Дата добавления: 2015-07-18; просмотров: 489 | Нарушение авторских прав


Читайте в этой же книге: Позиционные системы счисления | Перевод натуральных чисел из одной позиционной системы счисления в другую | Восьмеричная система счисления | Компьютеры и системы счисления | Отношение делимости и его свойства | Признаки делимости на 2 и 5. | Признаки делимости в других позиционных системах счисления | Четыре класса целых неотрицательных чисел.Простые и составные числа | Решето Эратосфена | Некоторые теоремы, предшествующие основной теореме арифметики |
<== предыдущая страница | следующая страница ==>
Основная теорема арифметики| Некоторые свойства наибольшего общего делителя и наименьшего общего кратного

mybiblioteka.su - 2015-2024 год. (0.005 сек.)