Постройте умозаключение доказывающее что число 19 является простым

Отношение делимости и его свойства

Определение. Пусть даны натуральные числа а и b. Гово­рят, что число а делится на число b, если существует та­кое натуральное число q, что a = bq.

Из определения отношения делимости и равенства а = 1·а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.

Выясним, сколько вообще делителей может быть у натурального числа а. Сначала рассмотрим следующую теорему.

Теорема1. Делитель b данного числа а не превышает этого числа, т.е. если

Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. образуют конечное множество <1,2,3,4,6,9,12,18,36>.

В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.

Например, число 13- простое, поскольку, у него только два делителя: 1 и 13.

Определение. Составным числом называется такое нату­ральное число, которое имеет более двух делителей.

Так число 4 составное, у него три делителя: 1,2 и 4.

Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.

Нам известно, что отношение делимости обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимо­сти, мы можем доказать эти и другие его свойства.

Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.

Доказательство. Для любого натурального а справед­ливо равенство а = а·1. Так как 1 Є N, то, по определению отношения делимости, а : _. а.

то b ⁞͞ a.

Доказательство. Предположим противное, т.е. что b⁞a. Но тогда а ≤ b, согласно теореме, рассмотренной выше.

По условию и а ⁞. b и а ≠ b. Тогда, по той же теореме, b ≤ а.

Неравенства а ≤ b и b ≤ а будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следова­тельно, наше предположение неверное и теорема доказана.

Теорема 4. Отношение делимости транзитивно, т.е. если а⁞ b и b⁞ с, то а⁞ с.

а⁞ с.

Например, не производя вычислений, можно сказать, что 175 + 360 + 915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.

Доказательство этой теоремы аналогично доказательству признака делимости суммы.

Теорема 7 (признак делимости произведения). Если число а делится на b, то произведениe вида ах, где х Є N, делитcя на b.

Из доказанной теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b. Например, произведение 24·976·305 делится на 12, так как на 12 делится множитель 24.

Рассмотрим еще три теоремы, связанные с делимостью суммы и произведения, которые часто используются при решении задач на делимость.

Теорема 8. Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся cумма на число b не делится.

Теорема 9. Если в произведении ab множитель a делится на натуральное число т, а множитель b делится на натуральное число n,то ab делится на mn.

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

1.Объясните, почему число 15 является делителем числа 60 и не является делителем числа 70.

2.Постройте граф отношения «быть делителем данного числа», заданного на множестве Х = <2, 6,. 12, 18, 24>. Как от­ражены на этом графе свойства данного отношения?

4. Запишите множество делителей числа.

5.На множестве X = <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11; 12>задано отношение «иметь одно и то же число делителей». Является ли оно отношением эквивалентности?

6.Постройте умозаключение, доказывающее, что:

а) число 19 является простым;

б) число 22 является составным.

7.Докажите или опровергните следующие утверждения:

а) Если сумма двух слагаемых делится на некоторое число, то и каждое слагаемое делится на это число.

б) Если одно из слагаемых суммы не делится на некоторое число, то и сумма не делится на это число.

в) Если ни одно слагаемое не делится на некоторое число, то и сумма не делится на это число.

г) Если одно из слагаемых суммы делится на некоторое число, а другое не делится на это число, то и сумма не делится на это число.

Источник

Умозаключения. Виды умозаключений

Свойства основных понятий раскрываются в аксиомах – предложениях, принимаемых без доказательства.

Например, в школьной геометрии есть аксиомы: «через любые две точки можно провести прямую и только одну» или «прямая разбивает плоскость на две полуплоскости».

Система аксиом любой математической теории, раскрывая свойства основных понятий, дает их определения. Такие определения называют аксиоматическими.

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

Доказать теорему АВ – это значит установить логическим путем, что всегда, когда выполняется свойство А, будет выполняться свойство В.

Доказательством в математике называют конечную последовательность предложений данной теории, каждое из которых либо является аксиомой, либо выводится из одного или нескольких предложений этой последовательности по правилам логического вывода.

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

В качестве примера рассмотрим рассуждение школьника, которому надо установить отношение «меньше» между числами 7 и 8. Учащийся говорит: «7 12.

Поэтому выводы, полученные с помощью неполной индукции, необходимо либо доказывать, либо опровергать.

Пример 3. При обучении делению на однозначное число используется такой прием. Сначала выясняется: чтобы найти значение выражения 12 : 4, следует узнать, на какое число надо умножить делитель 4, чтобы получить делимое 12. Известно, что 43 = 12. Значит, 12 : 4 = 3.

Данный пример – это пример рассуждения по аналогии.

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

Вывод по аналогии носит характер предположения, гипотезы и поэтому нуждается либо в доказательстве, либо в опровержении.

Источник

Решение логических задач

Исходя из разговорной практики, мы знаем, что, имея высказывания А и В, можно построить высказывания: не А (неверно, что А); А и В; А или В; если А, то В (из А следует В); А только и только тогда, когда В (А эквивалентно В, А тождественно В). Эти высказывания, в отличие от элементарных, естественно назвать сложными, поскольку они уже наделены структурой. Однако они так же, как и простые, могут принимать только два возможных значения: И либо Л.

Пример 3. Для составного высказывания «Пришла весна, и грачи прилетели» выделите простые, обозначив каждое из них буквой; запишите с помощью логических операций составное высказывание:

Пример 4. Определить значение истинности высказываний:

1) «7 является простым числом, или 19 является простым числом». Данное высказывание является сложным, поэтому обозначим А – «7 является простым числом», a В – «19 является простым числом». Имеем, что А=1, В=1. Составим формулу АÚВ и, используя таблицу истинности, найдем логическое значение формулы. Получим АÚВ= 1.

2) «2 + 3 = 6 и Архангельск расположен на Северной Двине». Данное высказывание является сложным, поэтому обозначим А – «2+ 3 = 6», а В-«Архангельск расположен на Северной Двине». Имеем, что А = 0, В = 1. Составим формулу АÙВ и, используя таблицу истинности, найдем логическое значение формулы. Получим АÙВ =0.

3) «Если 12 делится на 6, то 12 делится на 4». Данное высказывание является сложным, поэтому обозначим А- «12 делится на 6», а В – «12 делится на 4». Имеем, что А= 1,В=1. Составим формулу А®В и, используя таблицу истинности, найдем логическое значение формулы. Получим А®В= 1.

4) «11 делится на 3 тогда и только тогда, когда 20 делится на 5». Данное высказывание является сложным, поэтому обозначим А – «11 делится на 3», а В- «20 делится на 5». Имеем, что А=0, В = 1. Составим формулу А«В и, используя таблицу истинности, найдем логическое значение формулы. Получим А«В= 0.

Пример 5.Если будет холодно (А), то я надену теплое пальто (В), если рукав будет починен (С). Завтра будет холодно, а рукав не будет починен. Следует ли отсюда, что я не надену теплое пальто?

Множество. Способы задания множеств.

Если a является элементом множества A или, что то же самое, a принадлежит множеству A, то применяют запись aÎA; в противном случае пишут aÏA.

Два множества A и B равны (A=B), если они состоят из одних и тех же элементов. Если множества A и B не равны, то применяется запись A ¹ B.

Множество, содержащее конечное число элементов, называется конечным, в противном случае множество называется бесконечным. Конечное множество, содержащее n элементов, называется n-множеством.

Множество, не содержащее элементов, называется пустым и обозначается Æ.

Предположим, что все множества, которые будут рассмотрены в этой главе, являются подмножествами некоторого множества U, называемого универсальным множеством.

Если каждый элемент а множества В, аÎВ, является элементом множества А, аÎА, то В называется подмножеством множества А (рис. 1.1, а). Этот факт записывается с помощью знака включения Í следующим образом: ВÍА.

2. если АÍ В и ВÍС, то АÍС (рис. 1.1, б);

3. из двух включений ВÍА и АÍ В следует, что А=В.

Принято считать, что пустое множество является подмножеством любого множества.

Если ВÍ А и при этом В¹А, то этому соответствует запись ВÌ А и В называется собственным подмножеством А. В решении примера 1.1 все множества, кроме последнего, являются собственными подмножествами множества А.

Для описания множества A, состоящего из элементов a₁,a₂. a_n. обычно применяется запись A=1,a₂. a_n. >, причём порядок элементов в фигурных скобках не имеет значения; обычно он определяется соображениями наглядности.

Пример 1. В записи множества первых n натуральных чисел Nn= <1,2. n>удобно располагать числа в возрастающем порядке, хотя при этом надо иметь в виду, что N₃ =<1,2,3>=<2,1,3>=<3,2,1>.

Другой способ задания множества состоит в описании свойств, однозначно определяющих принадлежность элементов данному множеству. Такому способу задания множества соответствует запись: A =.

В случае описания множества с помощью некоторого свойства необходимо следить за тем, чтобы каждый элемент был чётко определён. Так, например, недостаточно чётким является определение множества А как множества слов русского языка, если нет ссылки на один из толковых словарей.

Возможно также рекурсивное задание множества, при котором осуществляется последовательное описание элементов через предыдущие. Например, множество натуральных чисел рекурсивно можно задать так: N=.

Операции над множествами. Законы действий над множествами.

Объединением двух множеств А и В называется множество вида:

Пересечением двух множеств А и В называется множество вида:

Если множества А и В не имеют общих элементов, то AÇB=Æ.

Свойства операций объединения и пересечения

1. AÈB = ВÈА, AÇB = ВÇА (коммутативность);

2. (AÈB)ÈС = AÈ(BÈС), (AÇB)ÇС = AÇ(BÇС) (ассоциативность).

3. Объединение и пересечение связаны законами дистрибутивности:

AÇ(BÈC)= (AÇB) È (AÇС); AÈ(BÇC)= (AÈB) Ç (AÈС).

По свойству 3 операции включения следует равенство правой и левой частей доказываемого равенства.

Разность множеств А и В определяется следующим образом:

Разность не обладает свойством коммутативности; эта операция также не является и ассоциативной.

Пользуясь понятием универсального множества, можно определить дополнение к множеству А, как разность вида: = U \ A (рис. 1.3, б).

Операции объединения, пересечения и дополнения множеств связаны между собой законами де Моргана:

, .

Источник

Курс лекций по математике. Учебнометодический комплекс по дисциплине Конспект лекций (на правах рукописи) Абакан

§ 18. ДЕЛИМОСТЬ НАТУРАЛЬНЫХ ЧИСЕЛ
Лекция 44. Делимость целых неотрицательных чисел

1. Отношение делимости на множестве неотрицательных чисел.

2. Свойства отношения делимости.

Из определения отношения делимости и равенства а = 1·а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.

Выясним, сколько вообще делителей может быть у натурального числа а. Сначала рассмотрим следующую теорему.

Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. образуют конечное множество <1,2,3,4,6,9,12,18,36>.

В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.

Например, число 13- простое, поскольку, у него только два делителя: 1 и 13.

Определение. Составным числом называется такое нату­ральное число, которое имеет более двух делителей.

Так число 4 составное, у него три делителя: 1,2 и 4.

Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.

Нам известно, что отношение делимости обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимо­сти, мы можем доказать эти и другие его свойства.

Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.

Доказательство. Для любого натурального а справед­ливо равенство а = а·1. Так как 1 Є N, то, по определению отношения делимости, а : _. а.

Неравенства а ≤ bи b ≤ а будут справедливы лишь тогда, когда а = b , что противоречит условию теоремы. Следова­тельно, наше предположение неверное и теорема доказана.

Например , не производя вычислений, можно сказать, что 175 + 360 + 915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.

Доказательство этой теоремы аналогично доказательству признака делимости суммы.

Теорема 7 (признак делимости произведения). Если число а делится на b , то произведениe вида ах, где х Є N, делитcя на b.

Из доказанной теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b. Например, произведение 24·976·305 делится на 12, так как на 12 делится множитель 24.

Рассмотрим еще три теоремы, связанные с делимостью суммы и произведения, которые часто используются при решении задач на делимость.

Теорема 8. Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b , то вся c умма на число bне делится.

Пришли к противоречию с тем, что дано. Следовательно , s : . b.
Например, сумма 34 + 125 + 376 + 1024 на 2 не делится, так 34 : .2,376 : .2,124 : .2, но 125 не делится на 2.

Теорема 9. Если в произведении abмножитель aделится на натуральное число т, а множитель bделится на натуральное число n,то abделится на mn.

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

Теорема 10. Если произведение ас делится на произведе­ние bс,причем с— натуральное число, то и а делится на b.

5.На множестве X=<1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11; 12> задано отношение «иметь одно и то же число делителей». Является ли оно отношением эквивалентности?

6.Постройте умозаключение, доказывающее, что:

а) число 19 является простым;

б) Если одно из слагаемых суммы не делится на некоторое число, то и сумма не делится на это число.

в) Если ни одно слагаемое не делится на некоторое число, то и сумма не делится на это число.

г) Если одно из слагаемых суммы делится на некоторое число, а другое не делится на это число, то и сумма не делится на это число.

Лекция 45. Наименьшее общее кратное и наибольший общий делитель чисел

1. Признаки делимости на 2, 3, 4, 5, 9, 25.

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

3. Основные свойства наименьшего общего кратного и наибольшего общего делителя чисел.
89. Признаки делимости

Рассмотренные в п. 88 свойства отношения делимости позволяют доказать известные признаки делимости чисел, записанных в десятичной системе счисления, на 2,3,4,5,9.

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

Теорема 11 (признак делимости на 2). Для того чтобы до хделилось на 2, необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр 0,2,4,6,8.

Теорема 12. (признак делимости на 5). Для того чтобы число х делилось на 5, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 0 или 5.

Доказательство этого признака аналогично доказательству признака делимости на 2.

Докажем обратное, т.е. если число х делится на 4, тo двузначное число, образованное последними цифрами его десятичной записи, тоже делится на 4.

Например, число 157872 делится на 4, так как последние две цифры в его записи образуют число 72, которое делится на 4. Число 987641 не делится на 4, так как последние две цифры в его записи образуют число 41, которое не делится на 4.

Теорема 14 (признак делимости на 9). Для того чтобы число х делилось на 9, необходимо и достаточно, чтобы сум­ма цифр его десятичной записи делилось на 9.

В последней сумме каждое слагаемое делится на 9:

Например, число 34578 делится на 9, так как сумма его цифр, равная 27, делится на 9. Число 130542 не делится 9, так как сумма его цифр, равная 15, не делится на 9.

Теорема 15 (признак делимости на 3). Для того чтобы число х делилось на 3, необходимо и достаточно, чтобы сум­ма цифр его десятичной записи делилось на 3.

Доказательство этого утверждения аналогично доказа­тельству признака делимости на 9.

1. Выпишите из ряда чисел 132, 1050, 1114, 364, 12000 те, которые:

в) делятся на 2 и не делятся на 4;

г) делятся и на 2 и на 4.

а) Для того чтобы число делилось на 2, необходимо и достаточно, чтобы оно делилось на 4?

б) Для того чтобы число делилось на 2, достаточно, чтобы
оно делилось на 4?

3. Из ряда чисел 72,312,522,483,1197 выпишите те, которые:

в) делятся на 3 и не делятся на 9;

г) делятся и на 3 и на 9.

Сделайте вывод о взаимосвязи делимости на 3 и на 9. До­кажите его.

4. Докажите признаки делимости на 5 и на 3.

5. Сформулируйте признак делимости на 25 и докажите его.

6. Не выполняя сложения, установите, делится ли значение выражения на 4:

а) 284 + 1440 + 113; в) 284 + 1441+ 113;

90. Наименьшее общее кратное и наибольший общий делитель

Рассмотрим известные из школьного курса математики понятия наименьшего общего кратного и наибольшего обще­го делителя натуральных чисел, сформулируем их основные свойства, опустив все доказательства.

Определение. Общим кратным натуральных чисел а иb на­зывается число, которое кратно каждому из данных чисел.

Наименьшее число из всех общих кратных чисел а и bна­зывается наименьшимобщимкратнымэтих чисел.

Наименьшее общее кратное чисел аи bусловимся обозна­чать К(а,b).

Наибольшее число из всех общих делителей чисел а и bна­зывается наибольшим общим делителем данных чисел.

Наибольший, общий делитель чисел а и bусловимся обо­значать D(а,b).

Например, для чисел 12 и 18 общими делителями являются числа: 1, 2, 3, 6. Число 6- наибольший общий делитель чисел 12 и 18. Можно записать: D(12,18) = б.

Число 1 является общим делителем любых двух натураль­ных чисел аиb.Если у этих чисел нет иных общих делителей, то D(a,b)= 1. Такие числа аи b называются взаимно простыми.

Например, числа 14 и 15 взаимно простые. ‘Так как
D(14, 15)=1.

Для наибольшего общего делителя справедливы следую-
щие утверждения:

Например, чтобы найти наименьшее общее кратное чисел 14 и 15, достаточно их перемножить, так как D(14,15) = 1.

б) Для того чтобы натуральное число а делилось на произ-
ведение взаимно простых чисел 14 и 15 необходимо и доста-
точно, чтобы оно делилось и на 14 и на 15.

Лекция 46. Простые и составные числа

1. Признак делимости на составное число

2. Простые и составные числа. Решето Эратосфена. Бесконечность множества простых чисел.

Критерий определения простого числа. Распределение простых чисел в натуральном ряду.
3. Признак делимости на составное число

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

Например, так как 6 = 2∙3 и D (2, 3) = 1, то получаем при­знак делимости на 6. Д ля того, что бы натуральное число де­лилось на 6, необходимо и достаточно, чтобы оно делилось и на 2 и на 3.

Заметим, что данный признак можно применять много­кратно.

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

Этим свойством можно пользоваться при проверке пра­вильности найденного наибольшего общего делителя данных чисел. Например, проверим, является ли число 12 наиболь­шим общим делителем чисел 24 и 36. Для этого, согласно по­следнему утверждению, разделим 24 и 36 на 12. Получим соответственно числа 2 и 3, которые являются взаимно просты­ми. Следовательно,

б) Можно ли назвать все их общие кратные?

в) Найдите три трехзначных числа, которые являются общими кратными данных чисел.

б) D(17,35)= 1 и K(17,35) = 595;

а) 105∙20; 6)47∙12∙5; в) 85∙33∙7.

10. Не выполняя сложения или вычитания, установите, значения каких выражений, делятся на 36.

а) 72 + 180 + 252; в) 180 + 252 + 100;

б) 612-432; г) 180 + 250 + 200.
91. Простые числа

Теорема: Любое составное число можно единственным об­разом представить в виде произведения простых множителей.

Например, запись 110 = 2∙5∙11 есть представление чис­ла 110 в виде произведения простых множителей или разло­жение его на простые множители.

Два разложения числа на простые множители считают одинаковым и, если они отличаются друг от друга лишь по­рядком множителей. Поэтому представление числа 110 в виде произведения 2∙5∙11 или произведения 5∙2∙11 есть, по сущест­ву, одно и то же разложение числа 110 на простые множители.

В связи с возможностью представлять любое составное число в виде произведения простых множителей возникает необхо­димость определять, является данное число простым или со­ставным. Эту задачу умели решать еще древнегреческие мате­матики, которым были известны многие свойства простых чи­сел. Так, Эратосфеном (III в. до н.э.) был придуман способ по­лучения простых чисел, не превышающих натурального чис­ла а. Воспользуемся им для поиска всех простых чисел до 50.

Первое не зачеркнутое число 3 является простым, обведем его кружком. И вычеркнем каждое третье число, стоящее по­сле 3, т.е. числа 9, 15. (числа 6,12 и др. зачеркнуты раньше).

Первое не зачеркнутое число 5 является простым, его также обведем кружком. Зачеркнем каждое пятое число после 5 и т.д

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

1. Разложение составного числа на простые множители (основная теорема арифметики).

2. Алгоритмы нахождения наибольшего общего делителя и наименьшего общего кратного данных чисел с помощью канонического разложения и алгоритма Евклида.
92. Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел

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

Пусть даны два числа 3600 и 288. Представим их в канони­ческом виде: 3600 = 2 4 ·3 2 ·5 2 ;

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

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

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

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

252 = 2 2 ·3 2 ·7, 264 = 2 3 ·3·11.

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

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

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

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

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

Найдем при помощи алгоритма Евклида наибольший об­щий делитель чисел 2585 и 7975. Делим уголком. Получаем: 7975 = 2585 ∙ 3 + 220, 2585 = 220 ∙ 11 + 165, 220 = 165∙ 1 + 55, 165 = 55 ∙ 3 + 0. В последнем случае остаток равен нулю. Значит, D (7975, 2575) = 55.

1. Найдите наибольший общий делитель и наименьшее общее кратное данных чисел, представив их в каноническом виде:
а) 948 и 624; 6) 120, 540, 418.

2. Используя алгоритм Евклида, найдите наибольший об­щий делитель чисел.

а) 846 и 246; б) 585 и 1960; в) 15283 и 10013.

Источник