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

Некоторые свойства наибольшего общего делителя и наименьшего общего кратного

Читайте также:
  1. II.7. Свойства усилительных элементов при различных способах
  2. III. Требования к структуре основной образовательной программы основного общего образования
  3. III.1. Физические свойства и величины
  4. III.3. Влияние обратной связи на свойства усилителя.
  5. IV. Требования к условиям реализации основной образовательной программы основного общего образования
  6. Vi. Некоторые методические примеры экономического обоснования проектируемых мероприятий
  7. XI. ПРИСПОСОБЛЕНИЕ И ДРУГИЕ ЭЛЕМЕНТЫ, СВОЙСТВА. СПОСОБНОСТИ И ДАРОВАНИЯ АРТИСТА

Теорема 1 (О связи НОД и НОК). НОД (а, в) · НОК (а, в) = а · в.

Доказательство. Пусть и , тогда , используя ассоциативность и коммутативность умножения, перегруппируем множители следующим образом:

а × в = ,

где diti, i = 1, 2, …, к.

Т.е. поступили мы так: выбрали и и сравнили ai и b i. Если a ib i, то во 2-ой скобке, а – в 1-ой скобке. Но ведь тогда

,

,

т.е. а · в =НОД(а, в)·НОК(а, в).

П р и м е р.

Запишем равенство 12 ·240 = 60 · 48, получим 2880 = 2880.

Теорема 2 (облегчающая вычисление НОД и НОК).

1) НОД (а 1, а 2, … а n) =НОД (НОД(а 1, а 2), а 3, …, аn),

2) НОК (а 1, а 2, … а n) =НОК (НОК(а 1, а 2), а 3, …, аn).

Теорема позволяет при отыскании НОД и НОК нескольких чисел производить это последовательно, заменяя пару чисел их НОД и НОК.

Доказательство. 1) Пусть даны числа а 1, а 2, …, аn своими каноническими разложениями.

,

,

,

… …….. …….

.

НОД (а 1, а 2) = , где ti – наименьшее из чисел ai, bi, i = 1, 2, …, к.

Обозначим через di – наименьшее из чисел ai, bi, ci, …, gi, тогда di является наименьшим из чисел ti, ci, …, gi.

НОД , отсюда

НОД(а 1, а 2, , аn) = НОД (НОД (а 1, а 2), а 3, а 4, …, аn).

2) Точно так же доказывается и вторая часть.

НОК , где r i – наибольшее из чисел ai, bi, i = 1, 2, …, к.

НОК , где mi – наибольшее из чисел ai, bi, ci, …, gi и является наибольшим из чисел ri, ci, …, gi, отсюда

НОК (а 1, а 2, …, аn) = НОК (НОК (а 1, а 2), а 3, а 4, …, аn).

П р и м е р. Применяя теорему 2, найдем НОД (1320, 3600, 1485).

1320 = 23 · 31 · 5 · 11,

3600 = 24 · 32 · 52 ·110,

1485 = 20 · 33 · 5 · 11.

НОД (1320, 3600) = 23 · 3 · 5 = 120,

НОД (120, 1485) = 20 · 3 · 5 = 15.

Значит, НОД (1320, 3600, 1485) = 15.

НОК (1320, 3600) = 24 · 32 · 52 · 11 = 39600

НОК (39600, 1485) = 24 · 33 · 52 · 11 = 118800.

Значит, НОК (1320, 3600, 1485) = 118800.

Теорема 3. Пусть m – некоторое натуральное число, тогда

НОД (ma1, ma2, …, man) = m НОД (а 1, а 2, …, аn),

НОК (ma1, ma2, …, man) = m НОК (а 1, а 2, …, аn), то есть общий множитель можно выносить за знак НОД и за знак НОК.

Доказательство. Запишем каноническое разложение чисел , НОД (а 1, а 2, …, аn) = ,

НОК (а 1, а 2, …, аn) = . Ясно, что есть наименьший, а – наибольший среди степеней простого числа pi, встречающихся в канонических разложениях чисел а 1, а 2, …, аn, но тогда будет наименьшим, а – наибольшим среди степеней простого числа p i в разложениях чисел 1, mа 2, …, n. pi – это любое число из простых множителей чисел а 1, а 2, …, аn. Значит, получили m НОД (а 1, а 2, …, аn) = = НОД ( 1, mа 2, …, n).

Аналогично, m НОК (а 1, а 2, …, аn) = = НОК ( 1, mа 2, …, n).

 


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


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

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