Тема 2. Основы теории делимости Лекция 1. Делимость целых неотрицательных чисел План

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

2. Делимость суммы, разности и произведения целых неотрицательных чисел.

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

Содержание

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

Определение 1. Говорят, что целое неотрицательное число а делится на натуральное число b, если существует такое целое неотрицательное число q, что а = b · q.

Если а делится на b, то пишут: . Иногда говорят, что «а кратно b». Обратным к отношению является отношение «b делит а».

Отношение делимости является бинарным отношением на множестве N₀. Рассмотрим свойства, которыми оно обладает.

1. Отношение делимости рефлексивно, то есть

.

Справедливость этого свойства следует из того, что а = а · 1 и . Так что можно считатьq = 1.

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

.

Доказательство этого свойства проведем методом от противного. Предположим, что . Тогда, по теореме 22 о существовании и единственности частного, b ≥ а. Но по условию – , и значит, а ≥ b. Выполнение обоих неравенств возможно только при а = b, что противоречит условию. Следовательно, справедливость свойства установлена.

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

.

Действительно, поскольку , то, по определению 1, существует такое , чтоа = bq₁. Аналогично, существует такое, чтоb = cq₂. Тогда , где. Это и означает, что .

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

2. Рассмотрим ряд основных теорем, связанных с делимостью суммы, разности и произведения.

Теорема 1. Если каждое слагаемое суммы делится на натуральное число b, то и вся сумма делится на это число, то есть

.

Доказательство. Пусть . Тогда существуют такие, что выполняются равенства:. Из этих равенств следует, что, где. По определению 1 отношения делимости это означает, что .

Теорема 2. Если каждое из чисел а и b делится на с и а ≥ b, то разность а – b делится на с, то есть

.

Доказательство. Пусть и . Тогда существуют такие, чтои. Посколькуа ≥ b, то q₁ ≥ q₂. Таким образом, имеем , где. Следовательно, .

Теорема 3. Если хотя бы один из множителей произведения делится на натуральное число b, то и все произведение делится на это число, то есть

.

Доказательство. Пусть i = 1, 2, ..., n, тогда существует такое, что .Отсюда, используя коммутативный и ассоциативный законы умножения, можем записать: =. Поскольку произведениецелых неотрицательных чисел является целым неотрицательным числом, то последнее равенство означает, что .

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

.

Доказательство. Пусть и , тогда существуют такие, чтои. Отсюда, на основании коммутативного и ассоциативного законов умножения, имеемab = (mq₁)(nq₂) = (mn) (q₁q₂) = (mn)q, где . Следовательно, .

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

Доказательство. Пусть , где , но . Докажем, что .

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

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

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

Для вывода признаков делимости используем тот факт (см. теорему 1), что любое натуральное число х можно представить в виде

, (1)

где 0 ≤ a_i ≤ 9 (i = 0, 1, ..., п), a_n ≠ 0.

Признак делимости на 2(5). Число х делится на 2(5) тогда и только тогда, когда на 2(5) делится число, образованное последней цифрой его десятичной записи:

.

Доказательство необходимости. Пусть . Поскольку,, то, по теоремам 3 и 1 о делимости произведения и суммы, можем утверждать, что в равенстве 1. Кроме того, по условию теоремы,. Отсюда, по теореме 2 о делимости разности,.

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

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

Признак делимости на 4(25). Число х делится на 4(25) тогда и только тогда, когда на 4(25) делится число, образованное двумя последними цифрами его десятичной записи:

.

Доказательство необходимости. Пусть . Так как, то в равенстве (1) выражение. Отсюда, по теореме о делимости разности,.

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

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

Признак делимости на 8(125). Число х делится на 8(125) тогда и только тогда, когда на 8(125) делится число, образованное тремя последними цифрами его десятичной записи.

.

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

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

.

Доказательство необходимости. Заметим сначала, что все числа вида 10ⁿ – 1, где , делятся на 3. Справедливость этого утверждения вытекает из равенства .

Преобразуем число , прибавив и вычтя из него выражение. Тогда .

После несложных преобразований можем записать равенство . (2)

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

Доказательство достаточности.

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

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