Курсовая работа: Признаки делимости

Приведенное доказательство бесконечности множества простых чисел было найдено Евклидом (IV век до н. э.) [1, c. 21].

Всякое число, делящее одновременно числа а и b, называется общим делителем этих чисел. Наибольший из общих делителей чисел а и b называется их наибольшим общим делителем и обозначается обычно через (а, b). Если наибольший общий делитель чисел а и b равен единице, то эти числа называются взаимно простыми. Иначе говоря, числа а и b называются взаимно простыми, если они одновременно не делятся ни на какое число кроме единицы.

Теорема 9. Если a и p - натуральные числа, причем число р простое, то либо a ? р, либо числа a и р взаимно просты.

Доказательство: Если числа а и р взаимно просты, то теорема доказана. Если же эти числа не взаимно просты, то оба они делятся на одно и то же число, отличное от единицы. Ввиду простоты р таким числом может быть только само р. Значит, в этом случае a ? p, а это и требовалось.

Всякое число, делящееся одновременно на числа а и b, называется общим кратным этих чисел. Наименьшее положительное общее кратное а и b называется наименьшим общим кратным этих чисел [1, c. 21].

1.2 Делимость сумм и произведений

Во многих случаях при делении с остатком интересно найти именно остаток от деления числа а на число b, а величина неполного частного от деления не играет роли.

Приведем следующий пример: Пусть, например, мы хотим узнать, какой день недели будет 21 ноября 2047 г. Мы знаем, что 21 ноября 2017 года - это вторник. Тридцать лет, разделяющие эти даты, состоят из

30·365 + 7 (последнее слагаемое - число високосных лет за это время), т. е. из 10957 дней. Эти дни составляют 1565 целых недель и еще 2 день. По прошествии 1565 целых недель снова наступит вторник, так что еще через 2 дня, 21 ноября 2047 г., будет четверг. Очевидно, для решения поставленной нами сейчас задачи совершенно неважно знать, сколько именно целых недель прошло за 30 лет, а интересно только число дней, прошедших сверх этих недель.

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

Продемонстрируем один из таких приемов на только что решавшейся нами задаче о дате 21 ноября 2047 г. Мы можем рассуждать следующим образом. Каждый простой (не високосный) год состоит из 365 дней, что составляет 52 полные недели и еще один день. Високосный же год составляет столько же недель и два дня. Значит, весь срок от 21 ноября 2017 г. до 21 ноября 2047 г. состоит из некоторого (совершенно неважно, какого) числа полных недель плюс число дней, равное числу содержащихся в этом сроке лет, причем каждый високосный год считается за два. Это число дней равно 30 + 7 = 37. Исключив из него 5 полных недель, получаем 2 дня, которые и следует отсчитывать от нашего вторника. Такая "замена года днем" есть проявление весьма общего приема.

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

,

где 0 ? б_i < t при i = 0, 1, ..., n. (5) Числа a₀, a₁, ..., a_n называются t-ичными цифрами числа A. При t = 10 мы получаем десятичную систему счисления. Из (5) следует

,

т. е. последняя t_ичная цифра а₀ числа А является остатком от деления А на t с остатком. Неполное частное от такого деления стоит в скобках. Разделив это неполное частное на t с остатком, мы получим

.

Остатком оказывается предпоследняя t_ичная цифра числа А.

Продолжая этот процесс повторного деления с остатком на t, мы будем последовательно получать все t-ичные цифры числа А, считая от низших разрядов к высшим. В силу полной упорядоченности множества натуральных чисел по величине, этот процесс последовательного деления с остатком должен рано или поздно оборваться. В результате мы получим все t-ичные цифры числа А, т. е. его запись в t-ичной системе счисления [1, c. 26].

Определение. Назовем числа а и b равноостаточными при делении на b, если остатки от деления а и b на m равны.

Установим несколько свойств равноостаточных чисел.

Теорема 10. Для того чтобы числа а и b были равноостаточными при делении на m, необходимо и достаточно, чтобы (а - b) ? m.

Доказательство: Необходимость. Пусть a = m·q₁ + r₁ (0 ? r₁ <m) (Д. 2) и a = m·q₂ + r₂ (0 ? r₂ <m) (Д. 3) Ввиду равноостаточности a и b должно быть r₁ = r₂. Значит, a - b = m·(q₁ - q₂), т. е. (а - b) ? m.

Достаточность. Пусть (а - b) ? m. Разделив a и b на m с остатком, мы получим (Д. 2) и (Д. 3). При этом а - b = m·(q₁ - q₂) + r₁ - r₂, т. е.

(a - b) - m (q₁ - q₂) = r₁ - r₂. По теореме 6 (r₁ - r₂) ? m. Но |r₁ - r₂| < m. Значит, по теореме 4 r₁ - r₂ = 0 или r₁ = r₂, а это и требовалось.

Следствие. Если числа а и b равноостаточны при делении на m, и m ? d, то а и b равноостаточны при делении на d.

Теорема 11. Если при делении на m числа a₁,a₂,...,a_n соответственно равноостаточны числам b₁,₂,...,b_n, то равноостаточными будут суммы a₁ + a₂ + ... + a_n и b₁ + b2 + ... + bn, а также произведения a1a2....an и b1b2....bn.

Доказательство: Из условия мы имеем:

(Д. 4)

Сложив почленно эти равенства, мы после простых преобразований получаем (a₁ + а₂ + ... + а_n) - (b₁ + b₂ + ... + b_n) = m (q₁ + q₂ + ... + q_n), что по теореме 10 и означает равноостаточность сумм.

Для доказательства равноостаточности произведений отметим следующее тождество: (k + b·m)·(р + q·m) - k·p + (p·q + l·p + l·q·m)·m. Из него следует, что произведение двух чисел вида а + b·m снова является числом того же вида. Поэтому, рассуждая по индукции, мы убеждаемся в том, что произведение любого количества чисел вида а + b·m есть число этого же вида. Перемножив теперь почленно все равенства (Д. 4) и применив к правой части только что проведенные рассуждения, мы получаем

a₁·a₂·...·a_n = b_1·b₂·...·b_n + m·t,

где t - некоторое целое число. Равноостаточность произведений, таким образом, доказана.

Следствие. Если при делении на m числа а и b равноостаточны, то такими же являются и степени aⁿ и bⁿ при любом натуральном n [1, c. 27].

Теорема 11 и ее следствие дают уже довольно богатые возможности для нахождения остатков от деления. Приведем пример:

Пример 1. Найти остаток от деления на 3 числа A = 13¹⁶ - 2²⁵·5¹⁵.

Очевидно, при делении на 3 число 13 равноостаточно с 1, 2 равноостаточно с - 1, а 5 тоже с - 1. Значит, на основании доказанного число А при делении на 3 равноостаточно с числом 1¹⁶ - (-1)²⁵·(-1)¹⁵ = 1 - 1 = 0, т. е. искомый остаток равен нулю, а А делится на 3.

1.3 Общие признаки равноостаточности и делимости

Существуют способы построения признаков делимости и равноостаточности на любое наперед заданное число. Они называются общими признаками равноостаточности или соответственно общими признаками делимости.

Указывая общий признак делимости (как и общий признак равноостаточности), мы должны проверить выполнение следующих условий. Во-первых, по всякому числу m он должен действительно давать признак делимости (равноостаточности) на это число. Во-вторых, общий признак должен быть определенным, т. е., примененный к заданному числу m, он должен приводить вполне определенным способом к вполне определенному конкретному признаку делимости (равноостаточности) на это число. Наконец, в-третьих, признак должен быть массовым, т. е. действительно общим, и давать признаки делимости или равноостаточности на любое наперед заданное натуральное число [1, c. 48].

В качестве примера найдем признак равноостаточности при делении на 5 в десятичной системе счисления.

Пример 2. Пусть А - натуральное число. Представим А в виде 10а + b (b _ последняя цифра числа А) и положим

Определенная функция удовлетворяет следующим условиям:

а) Значение f(x) при x ? m есть натуральное число;

б) Значение f(x) при x < m не определено (т. е. не имеет смысла);

в) Если x ? m, то f(x) < x;

г) Если x? m то числа x и f(x) равноостаточны при делении на m.

Таким образом, для нахождения остатка от деления некоторого числа на 5 достаточно взять последнюю цифру этого числа. Если эта цифра меньше пяти, то она и будет искомым остатком; в противном случае от нее следует отнять 5.

Некоторое усовершенствование общего признака равноостаточности, основанного на последовательном вычитании, приводит к известному процессу деления целых чисел "углом". Этот процесс деления тоже может рассматриваться как общий признак равноостаточности [1, c. 40].

Исторически первым общим признаком делимости (признаком равноостаточности) является следующий, предложенный знаменитым французским математиком Паскалем еще в середине XVII столетия. Сущность этого признака такова.

Пусть m - натуральное число. Составим последовательность чисел

r₁, r₂, r₃, ..., (5) полагая

представим теперь произвольное натуральное число А в виде

и определим функцию F_m(a):

Общий признак делимости должен давать нам признаки делимости на любое натуральное число, и для различных чисел приводить к признакам делимости весьма различного качества [1, c. 50].

Так, например, общий признак Паскаля наряду с вполне приемлемыми признаками равноостаточности при делении на 3 и 11 дает весьма громоздкий и неудобный к применению признак равноостаточности при делении на 7.

2. Изучение признаков делимости

2.1 Классификация признаков делимости

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

1) По последним цифрам числа

а. По одной последней цифре:

На 2. Если последняя цифра числа кратна 2 (четная), то число делится на 2.

На 5. Если последняя цифра делится на 5, то и число делится на 5

На 10. Если последняя цифра делится на 10 (иными словами она должна быть нулем), то и число делится на 10.

б. По двум последним цифрам

На 4. Если последними двумя цифрами образуется число, делящееся на 4, то и исходное число делится на 4

На 25. Если последними двумя цифрами образуется число, делящееся на 25, то и исходное число поделится на 25.

в. По трем последним цифрам

На 8. Если последние 3 цифры образуют число, которое делится на 8, то и исходное число разделится на 8

2) По сумме цифр или классов

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

На 9. Если сумма цифр разделилась на 9, то и исходное число разделится на 9

На 11. Натуральное число разбивают справа налево на группы по 2 цифры в каждой и складывают эти группы. Если получаемая сумма кратна 11, то испытуемое число кратно 11.

3) По разности классов

На 7. Число разделится на 7, если разность числа без его последней цифры и удвоенной последней цифрой делится на 7.

На 13. Число разделится на 13, если сумма числа без его последней цифры и учетверенной последней цифрой делится на 13.

Доказательство:

Вычитаемое делится на 13, поэтому делимость разности зависит от уменьшаемого. Поскольку 10 не имеет в разложении на простые множители числа 13, то уменьшаемое поделится на 13 только тогда, когда поделится сумма Что и требовалось обосновать.

4) Признаки делимости составных чисел

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

2.2 Примеры школьных задач на изучение признаков делимости

Таким образом, изложение основных математических фактов теории делимости основано на ряде теорем: о делении с остатком, разложении на простые множители, нахождении НОД и НОК, признаках делимости и т.д. Эти факты позволяют решать основные задачи школьного курса математики, и способствуют развитию умений решать задачи повышенной трудности. Поэтому необходимо проанализировать, какие из перечисленных базовых понятий отражены в школьных учебниках.

В школьном курсе математики теория делимости в полукольце натуральных чисел изучается в 5-6 классах (в зависимости от учебника) в следующем объеме: делители и кратные натуральных чисел; наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) натуральных чисел; простые и составные числа; разложение составного числа на множители; признаки делимости на 5, на 2, на 10, на 3 и на 9.

Задача № 1. Бюро путешествий «Бибигон» сделало господину Крокодилу специальное предложение: сертификат на три путевки в тур по Африке для его семьи - два взрослых билета и один детский за 2567 червонца. Известно, что детский билет на 500 червонцев дешевле. Однако господин Крокодил сразу раскусил обманщиков. Как ему это удалось?

Решение. 2567 + 500 = 3067, однако это число не делится на 3 [2, c. 8].