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

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

Определение. Число а делится на число в тогда и только тогда, когда существует такое число 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ⁿ + 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ⁿ + a_n–110^n–1 + …+a₁10) + a₀

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

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

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

Запишем число х = а_n10ⁿ + a_n–110^n–1 + …+a₁10 + a₀ в виде: а₀ = х – (а_n10ⁿ + a_n–110^n–1 + …+a₁10).

В этой разности число х 2 (по условию), вычитаемое (а_n10ⁿ + 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ⁿ 4].

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

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

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

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

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

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

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

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

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

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

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

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

х = (а_n10ⁿ + a_n–110^n–1 + …+a₂10²) + (а₁10 + а₀) и запишем равенство в виде:

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

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

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

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

Доказывается аналогично.

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

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

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

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

имеем: 10¹ – 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ⁿ – 1) 9.

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

Пусть х = а_n10ⁿ + 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 + … + а₁ + а₀, получим:

х = а_n10ⁿ + a_n–110^n–1 + …+a₁10 + a₀ + а_n – a_n + a_{n – 1} – a_{n – 1} + …+ a₁ – a₁ + a₀ – a₀ =

= (а_n10ⁿ – a_n) + (a_n–110^n–1 – a_{n – 1}) + … + (a₁10 – a₁) + (a₀ – a₀) =

=а_n (10ⁿ – 1) + a_n–1 (10^n–1 – 1) + … + a₁ (10 –1) + (а_n + a_n–1 + … + а₁ + а₀).

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

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

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

Равенство х = а_n10ⁿ + a_n–110^n–1 + …+a₁10 + a₀ запишем в виде: а

а_n + a_n–1 + … + а₁ + а₀ = х – (а_n (10ⁿ – 1) + a_n–1 (10^n–1 – 1) + … + a₁ (10 –1)).

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

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

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

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

имеем: 10¹ – 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ⁿ – 1) 3

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