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

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

В этом случае число 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 = bq u, значит, a-b = bq – b= b·(q - 1). Поскольку q Є N, тоq≥ 1. Тогда b· (q - 1) ≥ 0 и, следовательно, b ≤ а.

Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. образуют конечное множество {1, 2, 3, 4, 6, 9, 12, 18, 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 (признак делимости суммы). Если каждое из натуральных чисел а₁, а₂, ..., а_п делится на натуральное число b, то и их сумма a₁ + а₂ +... + а_n делится на это число.

Доказательство. Так как а₁ ⁞ b, то существует такое на­туральное число q₁, что а₁ =bq₁. Так как а₂ ⁞ b, то существует такое натуральное число q₂, что а₂ = bq₂. Продолжая рассуж­дения, получим, что если а_n ^: . b, то существует такое натуральное число q_n, что а_п = bq_n. Эти равенства позволяют преобразовать сумму а₁ + а₂ +... +а_п в сумму вида bq₁ + bq₂ +... + bq_n. Вынесем за скобки общий множитель b, а получившееся в скобках натуральное число q₁ + q₂ +... + q_n обозначим буквой q. Тогда a₁ + a₂ +... + a_n = b(q₁ + q₂+... + q_n) = bq, т.е. сумма а₁ + а₂ +… + а_п оказалась представленной в виде произведения числа b и некоторого натурального числа q. А это значит, что сумма а₁ + а₂ +… + а_п делится на b, что и требовалось доказать.

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

Теорема 6 (признак делимости разности). Если числа а₁ и а₂ делятся на b и а₁≥ а₂ , то их разность а₁ - а₂ делится на 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 = а₁+ а_г +... + а_п +" с и известно, что а₁ ^: . B, а₂ ^: . B,

___ ___

а₃ ^: . b, … а_n ^: . b, но с ^: . b. Докажем, что тогда s ^: . b

 

Предположим противное, т.е. Пусть s ^: . b. Преобразуем сумму s к виду с = s— (а₁ + а₂ +… + а_n). Так как s ^: . b по предположению, (а₁ + а₂ +… + а_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.

Доказательство. Так как ас делится на bc, то существует такое натуральное число q, что ас = (bc)q, откуда ас = (bq)c и, следовательно, а = bq, т.е. а^: .b.

 

Упражнения

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

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

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

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

а) 24; 6)13; в) 1.

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

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

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

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

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

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

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

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

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

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

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

___ __ ___

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

 

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

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

План:

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

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

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

 

Признаки делимости

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

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

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

Доказательство. Пусть число х записано в десятичной системе счисления, т.е. х = а_n·10 + а_n-1·10^n-1 +... + а ₁·10 + а₀, где а_n, а_{n-1, …,} a₁ принимают значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, а_n ≠ 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 +... + а₁·10) ^: .2. По условию а₀ тоже делится на 2, поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 2. Следовательно, согласно признаку делимости суммы, число хделится на 2. Докажем обратное: если число х делится на 2, то его десятичная запись оканчивается одной из цифр 0, 2, 4, 6, 8.

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

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

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

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

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

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

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

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

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

Доказательство. Докажем сначала, что числа вида 10ⁿ - 1 делятся на 9. Действительно, 10ⁿ - 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ⁿ- 1 делится на 9.

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

Преобразуем сумму а_n·10 + а_n-1·10^n-1 +... + а₁·10 + а₀, при­бавив и вычтя из нее выражение a _n +a _n-1 +…+a ₁ +a ₀ и записав результат в таком виде: х = (а_n·10 - a _n )+( а_n-1·10^n-1 - a _n-1 )+…+( а₁·10 - a ₁ )+ (а₀ – а ₀ )+ (a _n+a _n-1 +…+a ₁ +a ₀ )= а_n·(10ⁿ -1)+ a _n-1 ·(10^n-1 -1)+…+ a ₁·(10 -1)+ (a _n +a _n-1 +…+a ₁ +a ₀ ).

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

а_n·(10ⁿ -1)^: . 9, так как (10ⁿ -1) ^: . 9,

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

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

(a _n +a _n-1 +…+a ₁ +a ₀ )^: . 9 по условию.

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

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

Равенство х = а_n·10 + а_n-1·10^n-1 +... + а ₁·10 + а₀ запи­шем в таком виде: a _n +a _n-1 +…+a ₁ +a ₀ = х - (а_n(10ⁿ - 1) + а_n-1·(10^n-1 -1) +…+ a ₁·(10 -1). Так как в правой части этого равенства и уменьшаемое, и вычитаемое кратны 9, то по теореме о делимости разности (a _n +a _n-1 +…+a ₁ +a ₀ )^: . 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 и на 4.

2. Верно ли утверждение:

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

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

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

а) делятся на 3;

б) делятся на 9;

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

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

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

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

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

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

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

б) 284+ 1440 + 792224; г) 284+ 1441 + 113+ 164.

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

а) 360- 144; 6) 946-540; в) 30240-97.

 

⇐ Предыдущая29303132333435363738Следующая ⇒

Поделиться:

Популярное:

1. A. Оценка будущей стоимости денежного потока с позиции текущего момента времени
2. A. Смещение суставной головки через вершину суставного бугорка на передний его скат
3. A.27. Процедура ручной регулировки зеркала заднего вида
4. B. С нарушением непрерывности только переднего полукольца
5. Cоотношение номинального и реального валютного курса в краткосрочной и долгосрочной перспективе. Факторы, определяющие динамику номинального валютного курса в долгосрочном периоде
6. Cсрочный трудовой договор и сфера его действия.
7. F. Оценка будущей стоимости денежного потока с позиции текущего момента времени
8. G) определение путей эффективного вложения капитала, оценка степени рационального его использования
9. H) Такая фаза круговорота, где устанавливаются количественные соотношения, прежде всего при производстве разных благ в соответствии с видами человеческих потребностей.
10. I. МИРОВОЗЗРЕНИЕ И ЕГО ИСТОРИЧЕСКИЕ ТИПЫ
11. I. ПОЛОЖЕНИЯ И НОРМЫ ДЕЙСТВУЮЩЕГО ЗАКОНОДАТЕЛЬСТВА, В ОБЛАСТИ ОРГАНИЗАЦИИ ПРОТИВОПОЖАРНОЙ ПРОПАГАНДЫ И ОБУЧЕНИЯ НАСЕЛЕНИЯ МЕРАМ ПОЖАРНОЙ БЕЗОПАСНОСТИ
12. I. Рабочее тело и параметры его состояния. Основные законы идеального газа.