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

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

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

3. Делимость суммы, разности и произведения целых неотрицательных чисел. Как известно, вычитание и деление на множестве натуральных чисел выполнимо не всегда. Вопрос о существовании разности натуральных чисел а и bрешается просто - достаточно установить (по записи чисел), что b В этом случае число bназывают делителем числа а, а число а - кратным числа b .

Например, 24 делится на 8, так как существует такое q =3, что 24 = 8·3. Можно сказать иначе: 8 - это делитель числа 24, а 24 есть кратное числа 8. В том случае, когда а делится на b, пишут: а : . b. Эту запись »« читают и так: «а кратно b». Заметим, что понятие «делитель данного числа» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 -делитель, но 5 не является делителем числа 18. Если 18 делят 6, то в этом случае понятия «делитель» и «делитель данного числа» совпадают.

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

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

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

а : . b, то b а : . b, то существует такое q Є N ,что a=bqu, значит, a -b=bq–b= b·(q- 1). Поскольку q Є N ,тоq≥ 1. Тогда b · (q- 1) ≥ 0 и, следовательно, b ≤ а.

Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. образуют конечное множество .

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

Определение. Простым числом называется такое натуральное число, которое имеет только два делителя - единицу и само это число.

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

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

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

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

Чисел, кратных данному числу, можно назвать как угодно много, - их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, …, и все они могут быть получены по формуле а = 4q, где qпринимает значения 1, 2, 3.

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

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

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

Теорема 3. Отношение делимости антисимметрично, т.е. если а : . bи а ≠ b ,

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

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

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

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

Доказательство. Так как а : . b, то существует такое натуральное число q, что a = bq, а так как b ⁞ с, то существует такое натуральное число р, что b = ср. Но тогда имеем: a = bq = (cp)q = c(pq)- Число pq- натуральное. Значит, по определению отношения делимости,

а ⁞ с.

Теорема 5 (признак делимости суммы). Если каждое из натуральных чисел а1, а2, . апделится на натуральное число b , то и их сумма a1 + а2 + . + аnделится на это число.

Доказательство. Так как а1 ⁞ b , то существует такое натуральное числоq1, что а1 =bq1. Так как а2 ⁞ b, то существует такое натуральное число q2, что а2 = bq2. Продолжая рассуждения, получим, что если аn : . b , то существует такое натуральное число qn, что ап = bqn. Эти равенства позволяют преобразовать сумму а1 + а2 + . +апв сумму вида bq1 + bq2 + . + bqn. Вынесем за скобки общий множитель b , а получившееся в скобках натуральное число q1 + q2 + . + qnобозначим буквой q. Тогда a1 + a2 + . + an = b(q1 + q2+. + qn) = bq, т.е. сумма а1 + а2 +… + ап оказалась представленной в виде произведения числа bи некоторого натурального числа q. А это значит, что сумма а1 + а2 +… + ап делится на b, что и требовалось доказать.

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

Теорема 6 (признак делимости разности). Если числа а1 и а2 делятся на bи а1≥ а2 , то их разность а1 - а2 делится на b.

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

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

Доказательство. Так как а : . b, то существует такое натуральное число q, что a= bq. Умножим обе части этого равенства на натуральное число х. Тогда ах =(bq)x, откуда на основании свойства ассоциативности умножения (bq)x = b(qx) и, значит , ax = b(qx), где qx - натуральное число. Согласно определению отношения делимости, ax : . b, что и требовалось доказать.

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

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

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

Доказательство. Пусть s = а1+ аг+. +ап +" с и известно, что а1 : . B, а2 : . B ,

___ ___

а3 : . b, … аn : . b, но с : . b. Докажем, что тогда s : . bПредположим противное, т.е. Пусть s : . b. Преобразуем сумму s к виду с=s—(а1 + а 2 +… + аn). Так как s : . b по предположению, (а1 + а 2 +… + аn) : . b согласно признаку делимости суммы, то по теореме делимости разности с : . 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.

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

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

Известно, что число 24 - делитель числа 96, а число 96 -делитель числа 672. Докажите, что число 24 делитель числа 672, не выполняя деления.

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

5.На множестве X= задано отношение «иметь одно и то же число делителей». Является ли оно отношением эквивалентности?

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

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

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

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

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

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

8. Верно ли, что:

а) а : . ти b : . n =>ab : .mn

б) а : .пи b : .n=>ab : .n;в) ab : .n=> а : .пили b : .n.

Лекция 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.

Доказательство. Пусть число х записано в десятичной системе счисления, т.е. х=аn·10 + аn-1·10 n -1 + . + а 1·10 + а0, где аn, аn-1,…,a1принимают значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, аn ≠0 и а 0 принимает значения 0,2,4,6,8. Докажем, что тогда х : .2.

Так как 10 : .2, то 10 2 : .2, 10 3 : .2,…,10 n : .2 и, значит, (аn·10 + аn-1·10 n -1 + . + а1·10) : .2. По условию а0 тоже делится на 2, поэтому число хможно рассматривать как сумму двух слагаемых, каждое из которых делится на 2. Следовательно, согласно признаку делимости суммы, число х делится на 2. Докажем обратное: если число хделится на 2, то его десятичная запись оканчивается одной из цифр 0,2,4,6,8.

Запишем равенство х=аn·10 + аn-1·10 n -1 + . + а 1·10 + а0 в таком виде: а0=х- (аn·10 + аn-1·10 n -1 + . + а 1·10 ). Но тогда, по теореме о делимости разности, а0 : . 2, поскольку х : . 2и (аn·10 + аn-1·10 n -1 + . + а 1·10) : . 2. Чтобы однозначное число а0 делилось на 2, оно должно принимать значения 0,2,4,6,8.

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

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

Теорема 13. (признак делимости на 4). Для того чтобы число х делилось на 4, необходимо и достаточно, чтобы на 4 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х. Д оказательство. Пусть число х записано в десятичной системе счисления, т.е. х=аn·10 + аn-1·10 n -1 + . + а 1·10 + а0 и последние цифры в этой записи образуют число, которое делится на 4. Докажем, что тогда х : . 4.

Так как 100 : . 4, то (аn·10 + аn-1·10 n -1 + . + а 2·10 2 ) : . 4. По условию, а 1 ·10 + а0(это и есть запись двузначного числа) также делится на 4. Поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 4. Следовательно, согласно признаку делимости суммы, и само число х делится на 4.

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

Запишем равенство х=аn·10 + аn-1·10 n -1 + . + а 1·10 + а0 в таком виде: а1·10 + а0 = х- (аn·10 + аn-1·10 n -1 + . + а 2·10 2) . Так как х : . 4и аn·10 + аn-1·10 n -1 + . + а 2·10 2 ) : . 4, то по теореме о делимости разности (а1·10 + а0) : . 4.Но выражение а1·10 + а0 есть запись двузначного числа, образованного последними цифрами записи числа х.

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

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

Доказательство. Докажем сначала, что числа вида 10 n - 1 делятся на 9. Действительно, 10 n - 1 = (9·10 n -1 + 10 n -1 ) - 1 = (9·10 n -1 +9·10 n -2 + 10 n -2 )-1 = (9·10 n -1 +9·10 n -2 + …+10)-1=9·10 n -1 +9·10 n -2 + …+9. Каждое слагаемое полученной суммы делится на 9, значит, и число 10 n - 1 делится на 9.

Пусть число х=аn·10 + аn-1·10 n -1 + . + а1·10 + а0и( a n +an-1 +…+a1 +a0 ) : . 9. Докажем, что тогда х : .9.

Преобразуем сумму аn·10 + аn-1·10 n -1 + . + а1·10 + а0,прибавив и вычтя из нее выражение a n +an-1 +…+a1 +a0 и записав результат в таком виде: х = (аn·10 - a n )+( аn-1·10 n -1 - a n-1 )+…+( а1·10 - a 1 )+ (а0 – а 0 )+ ( a n+an-1 +…+a1 +a0 )= аn·(10 n -1)+ an-1 ·(10 n -1 -1)+…+ a1·(10 -1)+ ( a n +an-1 +…+a1 +a0 ).

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

аn·(10 n -1) : . 9, так как (10 n -1) : . 9,

a n-1 ·(10 n -1 -1) : . 9,так как(10 n -1 -1) : . 9 и т.д.

a 1·(10 -1) : . 9, так как (10- 1) : . 9,

( a n +a n-1 +…+a 1 +a 0 ) : . 9 по условию.

Следовательно, х : . 9.

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

Равенство х=аn·10 + аn-1·10 n -1 + . + а 1·10 + а0 запишем в таком виде: a n +an-1 +…+a1 +a0 =х - (аn(10 n - 1) + аn-1 · (10 n -1 -1) +…+ a1·(10 -1). Так как в правой части этого равенства и уменьшаемое, и вычитаемое кратны 9, то по теореме о делимости разности ( a n +an-1 +…+a1 +a0 ) : . 9, т.е. сумма цифр десятичной записи числа x делится на 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 . Верно ли утверждение:

а) Для того чтобы число делилось на 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;

Не выполняя вычитания, установите, делится ли разность на 9.

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

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

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

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

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

Наименьшее общее кратное чисел аи bвсегда существу-ет и является единственным.

Наименьшее общее кратное чисел аи 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.

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

Наибольший общий делитель чисел а и b не превосходит меньшего из данных чисел, т.е. если аи K(a,b)=ab.

Например, чтобы найти наименьшее общее кратное чисел 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, которые являются взаимно простыми. Следовательно,

Даны числа 36 и 45.

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

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

Верны ли записи:

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

Найдите К(а,b), если известно, что:

Сформулируйте признаки делимости на 12,15,18,36,45,75.

Из множества чисел 1032, 2964,5604,8910, 7008 выпишите те, которые делятся на 12.

Делятся ли на 18 числа 548 и 942?

К числу 15 припишите слева и справа по; одной цифре так, чтобы полученное число делилось на 15.

Найдите цифры а и 6 числа 72, если известно, что это число, делится на 45.

а) 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 на простые множители.

Раскладывая числа на простые множители, используют признаки делимости на 2, 3, 5 и др. Напомним один из способов записи разложения чисел на простые множители. Разложим, например, на множители число 90. Число 90 делится на 2. Значит , 2 есть один из простых множителей в разложении числа 90. Разделим 90 на 2. Число 2 запишем справа от знака равенства, а частное 45 - под числом 90. Число 45 делим на простое число 3, получаем 15. Делим 15 на 3, получаем 5. Число 5 - простое, при делении его на 5 получаем 1. Разложение на множители закончено.

При разложении числа на простые множители произведение одинаковыx множителей представляют в виде степени: 90 = 2∙3 2 ∙5; 60 = 2 2 ∙3∙5; 72 = 2 3 ∙3 2 . Такое разложение числа на простые множители называют каноническим.

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

Выпишем все натуральные числа от 1 до 50 и зачеркнем число 1 - оно не является простым. Число 2- простое, обведем его кружком. После этого зачеркиваем каждое второе число, стоящее после 2, т.е. числа 4,6,8.

Первое не зачеркнутое число 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

Те числа, которые останутся после четырех вычеркиваний (исключая числа 2,3,5 и 7), не делятся ни на 2, ни на 3, ни на 5, ни на 7. В арифметике доказано, что если натуральное число а, большее единицы, не делится ни на одно из простых чисел, квадрат которых не превосходит о, то а число простое. Поскольку 7 2 = 49, а 49 р также делится на это простое число q, то и разность (а + 1) - а, т.е. число 1, делится на q, что невозможно.

Итак, число а не является ни простым, ни составным, но этого тоже не может быть - всякое число, отличное от 1, либо простое, либо составное. Следовательно, наше предложение о том, что множество простых чисел конечное и есть самое большое простое число, неверно, и значит, множество простых чисел бесконечное.

Упражнения

Докажите, что число 819 не является простым числом.

Разложите на простые множители числа 124,588,2700,3780.

Какое число имеет разложение:

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.

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

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

находят значение этого произведения - оно и будет наибольшим общим делителем данных чисел. Найдем наименьшее общее кратное чисел 3600 и 288. В его разложение должны войти все простые множители, которые содержатся хотя бы в одном из разложений чисел 3600 и 288, причем каждый из них нужно взять с наибольшим показателем, с каким он входит в оба разложения.

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

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

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

Решение. Представим каждое число в каноническом виде: 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.

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

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

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

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

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

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

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

Продолжая описанный процесс, получаем все меньшие и меньшие остатки. В конце концов получим остаток, на который будет делиться предыдущий остаток. Этот наименьший, отличный от нуля, остаток и будет наибольшим общим делителем чисел 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.
📎📎📎📎📎📎📎📎📎📎