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

Рассмотрим сначала способ, основанный на разложении данных чисел на простые множители.


Пусть даны два числа 3600 и 288. Представим их в каноническом виде: 3600 = 24·32·52; 288 = 25·32. Найдем наибольший общий делитель данных чисел. В его разложение должны войти все общие простые мно­жители, которые содержатся в разложениях чисел 3600 и 288, причем каждый из них нужно взять с наименьшим показателем, с каким он входит в оба разложения. Следовательно, D(3600, 288) = 24·32 = 144.


Вообще чтобы найти наибольший общий делитель данных чисел:


1) представляют каждое данное число в каноническом виде;


2) образуют произведение общих для всех данных чисел простых множителей, каждый с наименьшим показателем, каким он входит во все разложения данных чисел;


3) находят значение этого произведения - оно и будет наибольшим общим делителем данных чисел.


Найдем наименьшее общее кратное чисел 3600 и 288. В его разло­жение должны войти все простые множители, которые содержатся хотя бы в одном из разложений чисел 3600 и 288, причем каждый из них нужно взять с наибольшим показателем, с каким он входит в оба разложения. Следовательно, D (3600, 288) = 25 ·32·5 = 7200.


Вообще чтобы найти наименьшее общее кратное данных чисел:


1) представляют каждое данное число в каноническом виде;


2) образуют произведение всех простых множителей, находящих­ся в разложениях данных-чисел, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел;


3) находят значения этого произведения, оно и будет наименьшим общим кратным данных чисел.


Найдем наибольший общий делитель и наименьшее об­щее кратное чисел 60, 252 и 264.


Решение. Представим каждое число в каноническом виде: 60 =  22·3·5,  252 = 22·32·7,   264 = 23·3·11.


Чтобы найти наибольший общий делитель данных чисел, образуем произведение общих для всех данных разложений простых множите­лей, каждый с наименьшим показателем, с каким он входит во все решения данных чисел: D(60, 252, 264) = 22·3 = 12.


Наименьшее общее кратное чисел можно найти, образовав произве­дение всех простых множителей, находящихся в данных разложениях, каждый с наибольшим показателем, с каким он входит во все разложе­ния данных чисел, т.е. K(60, 252, 264) = 23··32·5·7·11 = 27720.


Найдем наибольший общий делитель и наименьшее об­щее кратное чисел 48 и 245.


Решение. Представим каждое число в каноническом виде: 48 = 24 · 3, 245 = 5· 72.


Так как разложения данных чисел не содержат общих простых множителей, то D(48, 245) = 1, а К(48, 245) = 48· 245 = 10760.


Отыскание наибольшего общего делителя двух натуральных чисел по их каноническому виду требует предварительного разложения чисел на простые множители. Это несложно сделать, если числа не велики, но для многозначных чисел найти их каноническое разложение быва­ет трудно. Существует способ отыскания наибольшего общего дели­теля, требующий лишь деления с остатком. Этот способ был предло­жен Евклидом, и его называют алгоритмом Евклида. Он основан на следующих трех утверждениях:


1. Если а делится на b, то D(a, b) = b.


Доказательство: Так как а делится на b и b делится на b, то b общий делитель чисел a и b. Но любой делитель числа b не превосходит этого числа. Поэтому все общие делители a и b не превосходят b. Значит


b = D(a, b).


2. Если а = bq + r и r < b, то множество общих делителей чисел а и b совпадает с множеством общих делителей чисел.


Доказательство: Пусть d – общий делитель b и r. Так как b и r делятся на d, то и a = bq + r делится на d, значит, любой общий делитель чисел b и r является общим делителем чиcел b и a. Обратно, если b – общий делитель a и b, то d  является и делителем r, так как r = a – bq. Значит, любой общий делитель a и  b является общим делителем b и r. Таким образом множества совпадают.


3. Если а = bq + r и r < b, то D(a, b) = D(b, r).


Доказательство: По утверждению 2 множества общих делителей совпадают. А тогда оба множетва имеют один и тот же наибольший элемент, т.е. D(a, b) = D(b, r).


Сформулируем теперь алгоритм Евклида для нахождения наиболь­шего общего делителя натуральных чисел а и b.


Пусть а > b.


Если а делится на b, то D{a, b) = b.


Если при делении а на b, получается остаток r, то а = bq + r и D(a, b) = D(b, r) и задача свелась к отысканию наибольшего общего Делителя чисел b и r.


Если b делится на r, то D(b, r) = r и тогда D(а, b) = r.


Если при делении b на r получается остаток r1, то b = rq1 + r1 и поэтому D(r, r1) = D(b, r) = D(a, b).


Продолжая описанный процесс, получаем все меньшие и меньшие остатки. В конце концов получим остаток, на который будет делиться предыдущий остаток. Этот наименьший, отличный от нуля, остаток и будет наибольшим общим делителем чисел а и b.


Найдем при помощи алгоритма Евклида наибольший общий дели­тель чисел 2585 и 7975.


Просмотров 12 270 Комментариев 1
Познавательно:
Скажи свое мнение:
  1. 1 Написал: рвиамст (15 мая 2016 11:12) | Комментариев 0 | Группа: Гости
    Мне нравится, спасибо. не помогло am
Добавить комментарий
Имя:* E-Mail:*

Вопрос:
1+1=
Ответ:*