Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Основная теорема арифметики




Важнейшим вопросом, связанным с простыми числами, является вопрос о возможности разложения любого числа на простые множители.

Условились считать два разложения на множители одинаковыми, если они отличаются друг от друга лишь порядком множителей. Например, одинаковы разложения 2 · 2 · 3 · 5 и 3 · 2 · 5 · 2. Тогда справедлива следующая теорема, которую называют основной теоремой арифметики натуральных чисел.

Теорема. Всякое натуральное число, большее единицы, можно единственным образом представить в виде произведения простых множителей.

Основной эта теорема называется потому, что практически все свойства делимости чисел являются ее следствиями.

Теорема содержит два утверждения:

1) разложение на простые множители существует,

2) разложение на простые множители единственно.

Предварительно сделаем замечание. Возникает вопрос: в каком смысле сформулированная теорема верна для простого числа р?

Условимся считать, что простое число представимо в виде произведения так: р = р, т.е. число простых множителей в правой части равно одному.

1) Докажем сначала возможность представления натурального числа большего единицы в виде произведения простых чисел.

Пусть п > 1– какое-нибудь натуральное число. Оно имеет по крайней мере один простой делитель р1, п = р1· п1, при этом п1 = 1 или п1 > 1. Если п1 = 1, то п = р1 и теорема доказана. Если число п1 > 1, то оно имеет хотя бы один простой делитель р2, т.е. n1 = p2 × n2,
n = p1 · p2 · n2. При этом п2 = 1 или п2 >1. Если п2 = 1, то n1 = р2 и
n=p1 × p2 и теорема доказана. Если п2 > 1, то п2 имеет по крайней мере один простой делитель р3, п2 = p3 × n3, п = p1 × p2 × p3 × n3, если п3 = 1, то
n = p1· p2· p3 и теорема доказана. Если п3 > 1, то рассуждаем аналогичным образом дальше.

Заметим, что числа n1, n2, n3, … уменьшаются: n1 > n2 > n3 > … . Но множество натуральных чисел, меньших определённого числа n, конечно. Поэтому проводимый нами процесс после конечного числа шагов должен прекратиться, что может наступить лишь при условии, что какое-либо число nк = 1. Но тогда n = p1 · p2· · pк, где p1, p2, …, pк – простые числа.

Этим и доказывается возможность представления любого натурального числа большего 1 в виде произведения простых чисел.

Процесс разложения натурального числа на простые множители, применённый при доказательстве, хорошо известен со школы и схематически изображается так

 
 
 
 
 
   

Для осуществления этого разложения испытывают, последовательно, делится ли n на простые числа 2, 3, 5, 7.

2) Доказательство единственности (от противного).

Допустим, что натуральное число n > 1 можно представить в виде произведения простых чисел не единственным образом:

n = p1· p2· · pк и n = q1 · q2 ·· qm, где простые числа pi могут отличаться от qi, и, может быть, к m.

По симметричности и транзитивности отношения равенства имеем p1· p2 · · pк = q1· q2 ·· qm (*). Правая часть имеет множителем q1, значит произведение в левой части делится на q1, но тогда по теореме 5 (§ 9) один из множителей делится на q1. Меняя в случае надобности места множителей, можем считать, что p1 q1, но p1и q1 – простые числа, значит по теореме 6 (§ 9) p1 = q1. Разделим обе части равенства (*) на р1, получим:

p2 · p3 · … · pк = q2 · q3 · … · qm.

Аналогично устанавливаем, что один из множителей q2, q3, …, qm равен р2. Пусть q2 = р2, тогда p3 · p4 · … · pк = q3 · q4 · … · qm. Повторяя рассуждения, придем:

1) при к = т к тому, что при сокращении всех множителей в левой части равенства (*) сократятся все множители в правой части равенства (*) и в этом случае два представления числа n, указанные при допущении, могут отличаться только порядком следования множителей;

2) при к < т к невозможному равенству 1 = qk+1 · qk+2 · … · qm, т.к. произведение простых чисел не может быть равно единице;

3)при к > тпридем к невозможному равенству

pm+1 · pm+2 · … · pk = 1.

Следовательно, утверждение о единственности представления натурального числа п > 1 в виде произведения простых чисел доказано.

Если среди множителей p1, p2, …, pк встречаются одинаковые, то, пользуясь записью произведения равных множителей как степени, можем написать: , где каждый из показателей – натуральное число, а все множители p1, p2, …, pк различные простые числа.

Такое представление натурального числа п > 1 называют каноническим разложением числа n на простые множители. Например,
360 = 23 · 32 · 5.

 

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

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

Пусть ,

.

.

, для 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.

15. Некоторые свойства наибольшего общего делителя (НОД)
и наименьшего общего кратного (НОК)

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

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

а × в = ,

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

Т.е. поступили мы так: выбрали и и сравнили ai и bi. Если ai bi, то во 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) Точно так же доказывается и вторая часть.

НОК , где ri – наибольшее из чисел 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, но тогда будет наименьшим, а – наибольшим среди степеней простого числа pi в разложениях чисел 1, mа2, …,n. pi – это любое число из простых множителей чисел а1, а2, …, аn. Значит, получили m НОД (а1, а2, …, аn) = = НОД (1, mа2, …,n).

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

 

Следствие 1.

Пусть m – есть некоторый общий делитель чисел в1, в2, …, вn, тогда

НОД ;

НОК ,

т.е. если данные числа разделить на m, то их НОД и НОК также разделятся на m.

Доказательство. По теореме 3 имеем:

m НОД (а1, а2, …, аn) = НОД (1, mа2, …,n), разделим обе части равенства на m, получим

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

Обозначим mai = вi Þ ai = . Тогда:

. Что и требовалось доказать. Точно также выводится равенство относительно НОК.

Следствие 2.

d = НОД (а1, а2, …, аn .

Доказательство. Необходимость.

Дано НОД (а1, а2, …, аn) = d, доказать, что .

По следствию 1, имеем

НОД .

Достаточность.

Дано НОД , доказать, что НОД (а1, а2, …, аn) = d.

Обе части данного равенства умножим на d,

тогда d НОД .

По теореме 2 НОД (а1, а2, …, аn) = d. Что и требовалось доказать.

П р и м е р ы на применение следствия.

Пусть в1 = 33, в2 = 55, в3 = 99 Þ m = 11

1. .

=НОК (3, 5, 9) Þ НОК (33, 55, 99) = 11 · 45 = 495.

2. Пусть в1 = 33, в2 = 55, в3 = 99;

НОД (33, 55, 99) = 11. Тогда НОД ( )= 1.






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2023 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных