Делимость на множестве целых неотрицательных чисел Z

лекция 1 .notebook September 01, 2020 стр. 320­336. фев 2­16:26 Делимость на множестве целых неотрицательных чисел Z0 Разность натуральных чисел a­b существует тогда и только тогда, когда a>b. А когда существует частное двух натуральных чисел? С этой целью часто используются признаки делимости на натуральные числа. Некоторые из признаков представлены уже в начальной школе /по некоторым программам. янв 24­17:02 1 лекция 1 .notebook September 01, 2020 Теория делимости натуральных чисел содержит не только признаки делимости, но другие важные свойства чисел, связанные с делением. В начальном курсе математики детей знакомят с правилами деления суммы, разности, произведения. Следовательно, уже в начальной школе у детей формируются начальные знания теории делимости натуральных чисел. янв 24­16:52 Примеры. 1. 96:4=(80+16):4=80:4 + 16:4=20+4=24 2. 1600:8=(16 100):8=16:8 100=2 100=200 янв 24­17:02 2 лекция 1 .notebook September 01, 2020 Отношение делимости и его свойства. Теоремы о делимости чисел N. Говорят, что число а делится на в, если существует такое число q N, что Определение. Пусть a, в а=вq. а ­ кратно числу в, в ­ делитель числа а. янв 24­17:02 Стандартные обозначения: а в а делится на в, а в а не делится на в. янв 24­17:02 3 лекция 1 .notebook September 01, 2020 Следует отличать понятие "делитель данного числа" от понятия "делитель числа в выражении". 24:5 ­ здесь 5 ­ делитель в выражении, 36:9 ­ здесь оба понятия совпадают. Утверждение. Число 1 является делителем любого натурального числа. Доказательство. Имеем а= 1 а. Далее используем определение отношения делимости. Получаем а 1. янв 24­17:02 Выясним, сколько делителей может быть у натурального числа. С этой целью сначала докажем следующую теорему. Теорема 1. Если а в , то в ≤ а, т.е. делитель данного числа не превосходит этого числа. Доказательство. Так как а в , то по определению отношения делимости существует такое натуральное число q , что а=вq. янв 24­17:02 4 лекция 1 .notebook September 01, 2020 Отсюда имеем а­в = вq­в = в(q­1) . Так как q N, то q ≥ 1. Тогда в(q­1) ≥ 0 и, следовательно, в ≤ а. Следствие. Множество делителей данного числа конечно. Пример. Найдем все делители числа 28. Они образуют конечное множество 1, 2, 4, 7, 14, 28 . янв 24­18:39 В зависимости от числа делителей в множестве натуральных чисел различают простые и составные числа. Определение. Простым числом называют такое натуральное число, большее 1, которое имеет только два делителя ­ 1 и само это число. Пример. 11 ­ простое число, так как у него только два делителя : 1 и 11. янв 24­18:59 5 лекция 1 .notebook September 01, 2020 Определение. Составным числом называют такое натуральное число, которое имеет более двух делителей. Пример. Число 6 ­ составное, так как оно имеет более двух делителей: 1, 2, 3, 6. янв 24­18:59 Число 1 не является ни простым, ни составным, так как оно имеет ровно один делитель. Чисел, кратных данному числу, бесконечно много. Так, числа, кратные 3, образуют бесконечную последовательность натуральных чисел 3, 6, 9, 12, 15, 18, ... и все они могут быт получены по формуле а=3q, где q N. янв 24­19:08 6 лекция 1 .notebook September 01, 2020 Теорема : Деление на нуль невозможно. Доказательство: Пусть а N, а в = 0. 1. Если а ≠ 0 и частное а и в существует, тогда найдется число с из Z0, что а= 0• с, а = 0. Мы пришли к противоречию с условием, следовательно, частное чисел а ≠ 0 и в = 0 не существует. 2. Если а = 0, а частное а = 0 и в = 0 существует, тогда найдется с из Z0 и выполняется равенство 0 =0• с, истинное при любых значениях с , следовательно, частное чисел а = 0 и в = 0 может быть любым числом из Z0, т.е. результат деления определяется не единственным образом, а это невозможно. Поэтому в математике считают, что деление на 0 и в этом случае также невозможно. янв 24­16:53 Отношение делимости на множестве N обладает свойствами рефлексивности, антисимметричности и транзитивности. Теорема 2. Отношение делимости на множестве N рефлексивно. Доказательство. Для любого натурального числа а справедливо равенство а=а 1. Так как 1 ­ натуральное число, то а а по определению. янв 24­19:08 7 лекция 1 .notebook September 01, 2020 Теорема 3. Отношение делимости на множестве N антисимметрично, т.е. если а в и а ≠ в, то в а. Доказательство. Предположим противное , т. е. в а. Тогда по теореме 1 а ≤ в. По условию а в . Тогда по той же теореме в≤а. Два неравенства справедливы тогда и только тогда, когда а=в. Получили противоречие (а≠в по условию теоремы). Теорема доказана. янв 26­20:05 Теорема 4. Отношение делимости на множестве N транзитивно, т. е. если а в и в с, то а с. Доказательство. Так как а в , то существует такое натуральное число q, что а = вq. а так как в с , то существует такое натуральное число p, что в = сp. Но тогда имеем: а = вq = (сp)q = с(pq). Число pq ­ натуральное. По определению отношения делимости а с. Теорема доказана. янв 24­17:19 8 лекция 1 .notebook September 01, 2020 Теорема 5 (признак делимости суммы). Если каждое из натуральных чисел а1, а2, а3, ..., аn делится на натуральное число в, то и их сумма а1 + а2 + а3 +... + аn делится на в. Доказательство. Так как а1 в, то существует такое натуральное число q1, что а1 = вq1..Так как а2 в, то существует такое натуральное число q2, что а2 = вq2. Продолжая такие рассуждения, получим, что если аn в, то существует такое натуральное число qn, что аn = вqn.. янв 26­20:05 Эти равенства позволяют преобразовать сумму а1 + а2 + а3 +... + аn в сумму вq1 + вq2 + вq3+ ...+вqn . В последней сумме вынесем общий множитель в за скобки, а число q1 + q2 + q3 + ...+ qn обозначим через q. Тогда а1 + а2 + а3 +... + аn = в(q1 + q2 + q3 + ...+ qn ) = вq . Сумма а1 + а2 + а3 +... + аn представлена в виде произведения числа в и некоторого натурального числа q. А это значит, что сумма а1 + а2 + а3 +... + аn делится на в, что и требовалось доказать. янв 26­21:08 9 лекция 1 .notebook September 01, 2020 Например, не выполняя вычислений, можно показать, что сумма 234 +146 + 1864 делится на 2. янв 26­21:08 Теорема 6 (признак делимости разности). Если числа а1 и а2 делятся на натуральное число в и а1 > а2, то и их разность а1 ­ а2 делится на в. Доказательство данной теоремы аналогично доказательству теоремы о делимости суммы. янв 26­21:08 10 лекция 1 .notebook September 01, 2020 Теорема 7 (признак делимости произведения). Если число а делится на натуральное число в и х вида ах делится на в. N , то произведение Доказательство. Так как а в, то существует такое натуральное число q, что а = вq. Умножим обе части этого равенства на натуральное число х. Тогда ах = (вq)х, откуда (вq)х = в(qх) и, значит, ах = в(qх), где qх ­ натуральное число. Следовательно, по определению отношения делимости ах в. Теорема доказана. янв 26­22:01 Следствие. Если один из множителей произведения делится на натуральное число в, то и всё произведение делится на в. Пример. Произведение 33 3456 789 делится на 11, так как 33 делится на 11. янв 26­22:02 11 лекция 1 .notebook September 01, 2020 Теорема 8 . Если в сумме одно слагаемое не делится на натуральное число в, а все другие слагаемые делятся на в, то вся сумма не делится на в. Доказательство. Пусть s= а1 + а2 + а3 +... + аn + c и известно, что а1 в , а2 в , а3 в , ...,аn в , но с в. Докажем, что тогда s в. Предположим противное, т.е. пусть s в. Преобразуем сумму s к виду с = s ­ (а1 + а2 + а3 +... + аn). Так как s в по предположению, (а1 + а2 + а3 +... + аn) в согласно признака янв 26­22:02 делимости суммы, то по теореме о делимости разности с в. Получили противоречие с условием теоремы. Следовательно, s в. Пример. Сумма 23 + 56 + 2342 + 44 не делится на 2. янв 26­22:02 12 лекция 1 .notebook September 01, 2020 Теорема 9. Если в произведении ав множитель а делится на натуральное число m, а множитель в делится на натуральное число n, то ав делится на mn. Доказательство: самостоятельно. янв 26­22:54 Теорема 10. Если произведение ас делится на произведение вс, а с ­ натуральное число, то а делится на в. Доказательство. Так как ас делится на вс, то существует такое натуральное число q, что ас = (вс)q, откуда ас = (вq)с и , следовательно, а = вq, т.е. а в. 66 6 66 2 6 2 66:2=33 6:2 =3 33 3. янв 26­22:54 13 лекция 1 .notebook September 01, 2020 янв 26­22:54 фев 3­12:49 14