запишите используя символы свойства отношения делимости

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

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

В этом случае число b называют делителем числа а, а число а – кратным числа b.

Например, 24 делится на 8, так как существует такое q = 3, что 24 = 8*3. Можно сказать иначе: 8 – это делитель числа 24, а 24 есть кратное числа 8.

В случае, когда а делится на b, пишут: . Эту запись часто читают и так: «а кратно b».

Заметим, что понятие «делитель данного число» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 – делитель, но 5 не является делителем числа 18. Если 18 делят на 6, то в случае понятия «делитель» и «делитель данного числа» совпадают.

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

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

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

Доказательство. Так как , то существует такое , что a = bq, значит, a – b = bq – b = b*(q – 1). Поскольку , то . Тогда и, следовательно, .

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

Свойства делимости

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

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

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

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

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

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

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

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

Доказательство. Так как, то существует такое натуральное число q, что а = bq, а так как , то существует такое натуральное число p, что . Но тогда имеем: . Число pq – натуральное. Значит, по определению отношения делимости,.

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

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

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

Теорема (признак делимости произведения). Если число а де­лится на b, то произведение вида ах, где xÎ N, делится на b.

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

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

Источник

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

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

В этом случае число b называют делителем числа a, а число a – кратным числа b.

Например, 27 делится на 9, так как существует такое q = 3, что 27 = 9·3. Можно сказать иначе: 9 – это делитель числа 27, а 27 есть кратное числа 9.

В том случае, когда a делится на b, пишут . Эту запись часто читают и так: «a кратно b».

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

Отношение делимости на множестве N обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно.

Задача 16. Пользуясь определением отношения делимости, доказать, что если и , то .

Решение. Так как , то существует такое натуральное число q, что a = b·q, а так как , то существует такое натуральное число p, что b = c·p. Но тогда имеем: a = b·q = (c·p)·q = c·(p·q). Число p·q – натуральное. Значит, по определению отношения делимости, .

Задача 17. Известно, что при делении на 3 числа a и b дают в остатке соответственно 1 и 2. Доказать, что сумма чисел a и b делится на 3.

Решение. Данные числа a и b имеют вид: a = 3q + 1, b = 3p + 2. Найдем их сумму: a + b = (3q + 1) + (3p + 2) = 3q + 3p + 3 = 3·(q + p + 1). Так как q + p + 1 есть натуральное число, то сумма a+b оказалась представленной в виде произведения числа 3 и некоторого натурального числа. Отсюда, согласно определению отношения делимости, сумма данных чисел a и b делится на 3.

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

Решение. Так как и , то по свойству транзитивности , т.е. число 24 является делителем числа 672.

Упражнения для самостоятельной работы

1. Известно, что при делении на 5 числа a и b дают в остатке соответственно 2 и 3. Доказать, что сумма чисел a и b делится на 5.

2. Известно, что число 37 – делитель числа 148, а число 148 – делитель числа 592. Докажите, что число 37, делитель числа 592, не выполняя деления.

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

4. Докажите, что: а) сумма двух четных чисел есть число четное; б) сумма двух нечетных чисел есть число четное; в) сумма четного числа и нечетного есть число нечетное.

Источник

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

Понятие отношения делимости

Определение. Число а делится на число в тогда и только тогда, когда существует такое число q, что а = в × q. а в ( q N₀) [а = вq].

Обозначают: а в. Читают: «число а кратно числу в», «число в – делитель числа а», «а кратно в».

Равенство а=вq называют формулой кратности числа а числу в.

Число а, кратное 2, называют четным. Общий вид четного числа: а = 2n, n N₀.

Число, кратное 3 имеет формулу: а = 3n, n N₀.

Определение. Отношение делимости на множестве N₀ N содержит те и только те пары чисел (а, в), у которых первая координата кратна второй. Обозначают: « ».

« » = <(а, в)| (а, в) N₀ N а в>.

Если отношение делимости обозначить , то N₀ N = <(а, в)| (а, в) N₀ N а=вq>.

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

Доказательство. Так как а в, то ( q N₀) [а = вq] а – в=вq-в=в(q – 1), так как q N q 1.

Тогда в (q – 1) 0 в а. Из определения отношения делимости и равенства а = 1 × а, следует, что 1 является делителем для любого натурального числа.

Следствие. Множество делителей данного числа конечно.

Например, делители числа 18 является конечное множество: <1, 2, 3, 6, 9, 18>.

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

1. Отношение делимости рефлексивно, то есть любое натуральное число делится само на себя: ( а N) [(а,а) ], то есть а : а = 1.

Доказательство. ( а N)[а = а × 1] по определению отношения делимости а : а.

2. Отношение делимости антисимметрично, то есть для различных чисел а и в из того, что а в, следует, что в не кратно а. ( а, в N₀ N)[а в а в ].

Доказательство. Допустим, что в а, тогда в а. Но по условию а в, так как а в.

Неравенства в а а в истины только в том случае, если а = в. пришли к противоречию с условием. Следовательно, допущение, что в а Л. Таким образом, отношение делимости антисимметрично.

3. Отношение делимости транзитивно. ( а,в,с N₀ N)[а в в с а с].

Доказательство. Если а в ( q N)[а = вq] (1) Из того, что в с ( t N)[в = сt] (2)

Подставим в = сt в равенство (1), получим: а = (сt)q = c(tq), t,q N tq N tq = р а = ср, р N. А это значит, что а с.

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

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

Теорема (признак делимости суммы). Если числа а и в делится на число n, то их сумма делится на это число, ( а,в,n N₀ N)[а n в n (а + в) n].

Доказательство. Из того что а n в n (по определению отношения делимости)

а=nq₁ (1), q₁ N. в=nq₂ (2), q₂ N. Преобразуем сумму (а + в) к виду:

а + в = nq₁ + nq₂ = n (q₁ + q₂) = nq,q = q₁ + q₂. а + в = nq.

Следовательно, по определению отношения делимости, что (а + в) n.

Теорема (признак делимости разности). Если числа а и в делятся на число n и а в, то их разность а – в делится на число n, то есть

( а,в,n N₀ N)[а n в n а в (а – в) n].

Теорема (признак делимости произведения). Если один из множителей произведения делится на число n, то и все произведение делится на число n.

( а,в,n N₀ N)[а n (ав) n].

Доказательство. Из того, что а n а = nq (1). Умножим обе части равенства (1) на в N, получим: ав = nqв (по ассоциативности умножения) ав = n(qв) = nt, где t = qв ав = nt. А это значит, что ав n (по определению отношения делимости). Таким образом, для делимости произведения на число достаточно чтобы на данное число делился хотя бы один из множителей этого произведения.

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

( а,в,m,n N)[а m в n ав mn].

Доказательство. Из того, что а m а = mq₁, q₁ N; в n в = nq₂, q₂ N

ав = mq₁ × nq₂, = mn(q₁ × q₂) = mnq, q₁ × q₂ = q N. ав = mnq ав mn.

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

Доказательство. Пусть число х записано в десятичной системе счисления, то есть:

х = а_n10 n + a_n–110 n –1 + …+a₁10 + a₀, где а_n, a_n–1, …, а₁ – цифры, принимающие значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и а_n 0, а₀ – принимает значения 0, 2, 4, 6, 8.

Докажем, что число х 2. Так как 10 2, то любая степень числа 10 2. Десятичную запись числа х представим в виде: х = (а_n10 n + a_n–110 n –1 + …+a₁10) + a₀

I слагаемое II слагаемое

В этой сумме первое слагаемое по признаку делимости суммы делится на 2. Второе слагаемое а₀ 2 (по условию). Следовательно, по признаку делимости суммы на число х делится на 2.

Обратно, если число х делится на 2, то его десятичная запись оканчивается цифрой 0, 2, 4, 6, 8.

В этой разности число х 2 (по условию), вычитаемое (а_n10 n + a_n–110 n –1 + …+a₁10) 2 (по признаку делимости суммы). Следовательно, по теореме о делимости разности а₀ 2. Чтобы однозначное число а₀ делилось на 2, оно должно принимать значения 0, 2, 4, 6, 8.

Признак делимости на 2. На 2 делятся те и только те числа, в разряде единиц которых содержится число, делящееся на 2 или на 2 делятся те и только те числа, десятичная запись которых оканчивается одной из цифр 0, 2, 4, 6, 8.

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

Лемма. ( n N) [n > 1 10 n 4].

Доказательство. Так как 100 = 4 × 25, то по признаку делимости произведения

100 4. Тогда ( n N n > 1)[10 n = 10 2 × 10 n–2 ] 10 n = 100 × 10 n–2 и по признаку делимости произведения 10 n 4.

Теорема (признак делимости на 4). Натуральное число х делится на 4 тогда и только тогда, когда две последние цифры его десятичной записи образуют двузначное число, делящееся на 4.

Пусть х = а_n10 n + a_n–110 n –1 + …+a₁10 + a₀ и пусть десятичная запись двух последних цифр a₁10 + a₀ выражает число , которое делится на 4.

Доказательство. Представим число х в виде суммы двух слагаемых:

х = (а_n10 n + a_n–110 n –1 + …+a₂10 2 ) + (а₁10 + а₀),

I слагаемое II слагаемое

где первое слагаемое, по доказанной выше Лемме, делится на 4, второе слагаемое делится на 4 по условию. Следовательно, согласно признака делимости суммы на число, число х делится на 4.

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

По условию х 4. Докажем, что (а₁10 + а₀) 4.

Доказательство. Десятичная запись числа х имеет вид:

х = а_n10 n + a_n–110 n –1 + …+а₂ 10 2 + a₁10 + a₀, представим число х в виде суммы двух слагаемых:

х – (а_n10 n + a_n–110 n –1 + …+a₂10 2 ) = а₁10 + а₀, где х 4 (а_n10 n + a_n–110 n –1 + …+a₂10 2 ) 4 (по лемме).

Следовательно, по признаку делимости разности а₁10 + а₀ 4. выражение а₁10 + а₀ = – есть запись двузначного числа, образованного последними цифрами записи числа х.

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

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

Признак делимости на 25. На 25 делятся те и только те числа, у которых две последние цифры в записи числа 00, 25, 50, 75.

Лемма. ( n N) [(10 n – 1) 9].

Докажем методом математической индукции.

1. Проверим справедливость утверждения для n = 1,

имеем: 10 1 – 1 = 9 9 9. А(1) И.

2. Допустим, что утверждение справедливо для n = k,

имеем: 10 k – 1 9 А(k) И – индукционное допущение.

1. Докажем справедливость утверждения для n = k + 1, имеем:

2. 10 k + 1 – 1 = 10 k × 10 – 1 = 10 k (9 + 1) – 1 = 10 k × 9 + 10 k × 1 – 1 = 10 k × 9 + 10 k – 1, где первое слагаемое 10 k × 9 9 (по признаку делимости произведения), второе слагаемое 10 k – 1 9 (по допущению индукции). Следовательно, по признаку делимости суммы вся сумма делится на 9.

Таким образом, А (1) И А(k) И А(k + 1) И.

Следовательно, лемма доказана, то есть (10 n – 1) 9.

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

Пусть х = а_n10 n + a_n–110 n –1 + …+a₁10 + a₀ (1), где где а_n, a_n–1, …, а₁, а₀ – цифры, принимающие значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и а_n 0 и (а_n + a_n–1 + … + а₁ + а₀) 9.

Докажем, что число х 9. Доказательство. Преобразуем сумму (1), прибавив и вычтя из нее выражение а_n + a_n–1 + … + а₁ + а₀, получим:

В полученной сумме каждое слагаемое делится на 9 (по признаку делимости произведения):

а_n (10 n – 1) 9, так как (10 n – 1) 9; a_n–1 (10 n –1 – 1) 9, так как (10 – 1) 9; а_n + a_n–1 + … + а₁ + а₀ 9 (по условию). Следовательно, х 9.

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

Так как х 9 (по условию) и вычитаемое (а_n (10 n – 1) + a_n–1 (10 n –1 – 1) + … + a₁ (10 –1)) 9 (по признаку делимости суммы), то по теореме о делимости разности (а_n + a_n–1 + … + а₁ + а₀) 9, то есть сумма цифр десятичной записи числа х делится на 9.

Лемма. ( n N) [(10 n – 1) 3].

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

1. Проверим справедливость утверждения для n = 1,

имеем: 10 1 – 1 = 9 9 3. А(1) И.

2. Допустим, что утверждение справедливо для n = k,

имеем: 10 k – 1 3 А(k) И – индукционное допущение.

3. Докажем справедливость утверждения для n = k + 1, имеем: 10 k + 1 – 1 = 10 k × 10 – 1 = 10 k (9 + 1) – 1 = 10 k × 9 + 10 k × 1 – 1 = 10 k × 9 + 10 k – 1, где первое слагаемое 10 k × 9 3 (по признаку делимости произведения), второе слагаемое 10 k – 1 3 (по допущению индукции). Следовательно, по признаку делимости суммы вся сумма делится на 3.

Таким образом, А (1) И А(k) И А(k + 1) И. Следовательно, (10 n – 1) 3

Признак делимости на 3. На 3 делятся те и только те числа, сумма цифр которых делится на 3.

Источник