Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел
Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел - раздел Образование, Непротиворечивая система аксиом называется независимой, если никакая из аксиом этой системы не является следствием других аксиом этой системы Рассмотрим Сначала Способ, Основанный На Разложении Данных Чисел На Простые М...
Рассмотрим сначала способ, основанный на разложении данных чисел на простые множители.
Пусть даны два числа 3600 и 288. Представим их в каноническом виде: 3600 = 24×32×52; 288 = 25×32. Найдем наибольший общий делитель данных чисел. В его разложение должны войти все общие простые множители, которые содержатся в разложениях чисел 3600 и 288, причем каждый из них нужно взять с наименьшим показателем, с каким он входит в оба разложения. Следовательно, D (3600, 288) = 24×32 = 144.
Вообще, чтобы найти наибольший общий делитель данных чисел:
1) представляют каждое данное число в каноническом виде;
2) образуют произведение общих для всех данных чисел простых множителей, каждый с наименьшим показателем, каким он входит во все разложения данных чисел;
3) находят значение этого произведения - оно и будет наибольшим общим делителем данных чисел.
Найдем наименьшее общее кратное чисел 3600 и 288. В его разложение должны войти все простые множители, которые содержатся хотя бы в одном из разложений чисел 3600 и 288, причем каждый из них нужно взять с наибольшим показателем, с каким он входит в оба разложения. Следовательно, K:(3600, 288) = 25×32×5 = 7200.
Вообще, чтобы найти наименьшее общее кратное данных чисел:
1) представляют каждое данное число в каноническом виде;
2) образуют произведение всех простых множителей, находящихся в разложениях данных чисел, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел;
3) находят значения этого произведения, оно и будет наименьшим общим кратным данных чисел.
Задача 1. Найти наибольший общий делитель и наименьшее общее кратное чисел 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.
Задача 2. Найти наибольший общий делитель и наименьшее общее кратное чисел 48 и 245.
Решение. Представим каждое число в каноническом виде: 48 = 24×3, 245 = 5×72.
Так как разложения данных чисел не содержат общих простых множителей, то D(48, 245) = 1, а K:(48, 245) = 48×245 = 10760.
Отыскание наибольшего общего делителя двух натуральных чисел по их каноническому виду требует предварительного разложения чисел на простые множители. Это несложно сделать, если числа не велики, но для многозначных чисел найти их каноническое разложение бывает трудно. Существует способ отыскания наибольшего общего делителя, требующий лишь деления с остатком. Этот способ был предложен Евклидом, и его называют алгоритмом Евклида. Он основан на следующих трех утверждениях, доказательство которых мы опускаем:
1. Если а делится на b, то D (а, b) = b.
2. Если а = bq+r и r < b,то множество общих делителей чисел а и b совпадает с множеством общих делителей чисел b и r.
3. Если а = bq+r и r < b, то D(а, b) = D(b, r).
Сформулируем теперь алгоритм Евклида для нахождения наибольшего общего делителя натуральных чисел а и b.
Пусть а > b.
Если а делится на b, то D (а, b) = b.
Если при делении а на b, получается остаток r, то a = bq+r и D(а, b) = D (b, r) и задача свелась к отысканию наибольшего общего делителя чисел b и r.
Если b делится на r, то D (b, r) = r и тогда D (а, b) = r.
Если при делении b на r получается остаток r, , то b = rq1+r1 и поэтому D (r, r1) = D(b,r) = D(а, b).
Продолжая описанный процесс, получаем все меньшие и меньшие остатки. В конце концов получим остаток, на который будет делиться предыдущий остаток. Этот наименьший, отличный от нуля, остаток и будет наибольшим общим делителем чисел а и А.
Найдем при помощи алгоритма Евклида наибольший общий делитель чисел 2585 и 7975. Процесс последовательного деления будем записывать так:
_ 7975 2585
7755 3 975 = 2585 3 + 220.
_ 2585 220
220 11 2585 = 220 × 11 + 165
_ 385
220
_220 165
165 1 220 = 165 × 1 + 55
_ 165 55
165 3 165 = 55 × 3 + 0
В последнем случае остаток равен нулю. Значит, D (7975, 2585) = 55.
При аксиоматическом построении теории по существу все утверж дения выводятся путем доказательства из аксиом Поэтому к системе аксиом предъявляются... Система аксиом называется непротиворечивой если из нее нельзя логически... Если система аксиом не обладает этим свойством она не может быть пригодной для обоснования научной теории...
Количественные натуральные числа. Счет
Аксиоматическая теория описывает натуральное число как элемент бесконечного ряда, в котором числа располагаются в определенном порядке, существует первое число и т.д. Другими словами, в аксиоматик
Вопросы для самоконтроля
1. Назовите виды множеств, дайте им характеристику. Какие можно производить операции над множествами?
2. Что такое «число», «цифра», «счет»?
3. В чем связь и различие счета и изме
Теоретико-множественный смысл суммы
Сложение целых неотрицательных чисел связано с объединением конечных непересекающихся множеств. Например, если множество А содержит 5 элементов, а множество В - 4 элемента и пересечен
Теоретико-множественный смысл разности
В аксиоматической теории вычитание натуральных чисел определено как операция, обратная сложению: а – b = с Û ($ сÎN) b + с = а.
Вычитание целых неотрицательных чисел определяет
Теоретико-множественный смысл произведения
Определение умножения натуральных чисел в аксиоматической теории основывается на понятии отношения «непосредственно следовать за» и сложении. В школьном курсе математики используется другое определ
Теоретико-множественный смысл частного натуральных чисел
В аксиоматической теории деление определяется как операция, обратная умножению, поэтому между делением и умножением устанавливается тесная взаимосвязь. Если а× b = с, то, зная произведение с
Запись числа в десятичной системе счисления
Как известно, в десятичной системе счисления для записи чисел пользуется 10 знаков (цифр): 0, 1,2, 3, 4, 5, 6, 7, 8, 9. Из них образую конечные последовательности, которые являются краткими записям
Алгоритм сложения
Сложение однозначных чисел можно выполнить, основываясь на определении этого действия, но чтобы всякий раз не обращаться к определению, все суммы, которые получаются при сложении однозначных чисел,
Алгоритм вычитания
Вычитание однозначного числа b из однозначного или двузначного числа а, не превышающего 18, сводится к поиску такого числа с, что b + с = а, и происходит с учетом таблицы сложения однозначных чисел
Алгоритм умножения
Умножение однозначных чисел можно выполнить, основываясь на определении этого действия. Но чтобы всякий раз не обращаться к определению, все произведения однозначных чисел записывают в особую табли
Алгоритм деления
Когда речь идет о технике деления чисел, то этот процесс рассматривают как действие деления с остатком: разделить целое неотрицательное число а на натуральное число b - это значит найти
Наименьшее общее кратное и наибольший общий делитель.
4. Простые числа.
5. Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел.
Основная литература [7, 9-13, 23, 33, 34];
Дополнительн
Отношение делимости и его свойства
Определение.Пусть даны натуральные числа а и b. Говорят, что число а делится на число b, если существует такое натуральное число q, что а = bq.
В этом случае чис
Признаки делимости
Рассмотренные в свойства отношения делимости позволяют доказать известные признаки делимости чисел, записанных в десятичной системе счисления, на 2, 3, 4, 5, 9.
Признаки делимости позволя
Наименьшее общее кратное и наибольший общий делитель
Рассмотрим известные из школьного курса математики понятия наименьшего общего кратного и наибольшего общего делителя натуральных чисел, сформулируем их основные свойства, опустив все доказательства
Простые числа
Простые числа играют большую роль в математике - по существу они являются «кирпичами», из которых строятся составные числа.
Это утверждается в теореме, называемой основной теоремой арифмет
ТЕМА 17. О РАСШИРЕНИИ МНОЖЕСТВА НАТУРАЛЬНЫХ ЧИСЕЛ
Содержание
1. Понятие дроби.
2. Положительные рациональные числа.
3. Запись положительных рациональных чисел в виде десятичных дробей.
4. Действительные ч
Понятие дроби
Пусть требуется измерить длину отрезка х с помощью единичного отрезка е (рис. 1). При измерении оказалос
Положительные рациональные числа
Отношение равенства является отношением эквивалентностинамножестве дробей, поэтому оно порождает на нем классы эквивалентности. В каждом таком классе содержатся равные междусобой дроби.
На
Действительные числа
Одним из источников появления десятичных дробей является деление натуральных чисел, другим - измерение величин. Выясним, например, как могут получиться десятичные дроби при измерении длины отрезка.
Теоретико-множественный смысл разности.
8. Отношения «больше на» и «меньше на».
9. Правила вычитания числа из суммы и суммы из числа.
10. Из истории возникновения и развития способов записи натуральных чисел и нуля.
Понятие положительной скалярной величины и ее измерения
Рассмотрим два высказывания, в которых используется слово «длина»:
1) Многие окружающие нас предметы имеют длину.
2) Стол имеет длину.
В первом предложении утверждается,
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов