Делимость

Введение
Глава 1. Математические основы изучения темы
«Делимость чисел»
1.1.Делители и кратные
1.1.1.Понятие делимости
1.1.2 Простые числа
1.2. Свойства делимости
1.2.1. Основные свойства
1.2.2. Наибольший общий делитель
1.2.3 Наименьшее общее кратное
1.2.4 Единственность разложения на простые сомножители
1.3.Признаки делимости
1.1.3.Признаки делимости на числа от 2 до 12
1.3.2 Признак Паскаля
1.3.3 Диофантовы уравнения
1.4.Деление с остатком
1.1.4.Понятие деления с остатком
1.4.2. Сравнение по модулю
1.4.3 Классы вычетов.4.4 Принцип Дирихле в задачах на делимость
Глава 2. Методика изучения темы «Делимость» в основной и старшей школе
2.1. Анализ методики изучения темы «Делимость» в методической литературе
2.1.2.Анализ ФГТ по изучению темы делимость в профильных классах
2.1.3. Анализ учебников профильного уровня для 10-11-х классов по теме «Теория делимости»
2.2.Разработка элективного курса “Делимость целых чисел” для учащихся 11 классов
Заключение
Список литературы
Приложения

Делимость

Всякое целое, кратное всех данных чисел, называется их общим кратным. Наименьшее положительное общее кратное называется наименьшим общим кратным. Здесь мы будем рассматривать только общие кратные двух положительных чисел.
a. Пусть (a, b)=d, a=da1, b=db1 и, следовательно (2, е, п. 2), (а1, b1)=1. Пусть М - какое-либо общее кратное чисел а и b. Так как М кратно a, то M=ak, где k - целое. Но М кратно и b. Поэтому
должно быть целым и, следовательно (2, f, п. 2), k должно делиться на b1. Поэтому k=b1t, где t - целое, причем для М получается формула
. (1)
Обратно, очевидно, что М, представляемое формулой (1) при любом целом t, будет общим кратным a и b, и, таким образом, формула (1) дает общий вид всех общих кратных чисел а и b.
Наименьшее положительное из этих общих кратных, т. е. наименьшее общее кратное, получаем при t=1. Оно будет
. (2)
Теперь формулу (1) можно переписать так:
M=mt. (3)
Формулы (3) и (2) приводят к теоремам.
1. Совокупность общих кратных двух чисел совпадает с совокупностью кратных их наименьшего общего кратного.
2. Это наименьшее общее кратное двух чисел равно их произведению, деленному на их наибольший общий делитель.
1.2.4 Единственность разложения на простые сомножители
a. Всякое целое а или взаимно просто с данным простым p, или же делится на р.
Доказательство: (а, p), будучи делителем р, может быть равно или 1, или р. В первом случае а взаимно просто с p, во втором а делится на р.
b. Если произведение нескольких сомножителей делится на данное простое p, то, по крайней мере, один из сомножителей делится на р.
Доказательство: (а), каждый сомножитель или взаимно прост с p, или же делится на р. Если бы все сомножители были взаимно просты с p, то и их произведение (3, f, п. 2) было бы взаимно просто с р. Поэтому хоть один сомножитель делится на р.
c. Основная теорема арифметики. Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным способом (если отвлечься от порядка следования сомножителей).
Доказательство: Пусть а - целое, большее 1; обозначая буквою p1 его наименьший простой делитель, имеем а=р1а1. Если a1 > 1, то, обозначая буквою р2 его наименьший простой делитель, имеем a1=p2a2. Если а2 > 1, то подобно этому находим а2=р3а3 и т.д., пока не придем к какому-либо аn, равному 1. Тогда получим аn-1=pn. Перемножив все найденные равенства и произведя сокращение, получим следующее разложение а на простые сомножители:
a=p1p2p3…pn.
Допустим, что для того же самого а существует и второе разложение на простые сомножители a=q1q2q3…qs. Тогда найдем
p1p2p3…pn=q1q2q3…qs.
Правая часть этого равенства делится на q1. Следовательно (b), по крайней мере один из сомножителей левой части должен делиться на q1. Пусть, например, p1 делится на q1 (порядок следования сомножителей в нашем распоряжении); тогда найдем p1=q1 (p1 кроме 1 делится только на р1). Сократив обе части равенства на p1=q1, получим p2p3…pn=q2q3…qs. Повторив прежние рассуждения применительно к этому равенству, получим p3…pn=q3…qs и т.д., пока, наконец, в одной части равенства, например, в левой не сократятся все сомно­жители. Но одновременно должны сократиться и все сомножители правой части, так как равенство 1=qп+1…qs при qn+1, ..., qs, превосходящих 1, невозможно. Таким образом, второе разложение на простые сомножители тождественно первому.
 Основная теорема арифметики указывает на принципиальную возможность разложения любого числа на простые сомножители. Однако практическое осуществление такого разложения встречает большие трудности, которые современная математика иногда еще не может преодолеть. Разложение больших чисел на простые множители или установления их простоты в настоящее время осуществляется на основы применения электронных вычислительным машин. Так, лишь совсем недавно было обнаружено, что число 219937-1 (в нем более шести тысяч цифр) является простым.
d. В разложении числа а на простые сомножители некоторые из них могут повторяться. Обозначая буквами p1, p2, …, pk различные из них и буквами 1, 2, , k кратности их вхождения в а, получим так называемое каноническое разложение числа а на сомножители
.
Пример. Каноническое разложение числа 588000: 588000=2535372.
e. В заключение мы докажем несколько теорем, касающихся делителей числа, а также наибольшего общего делителя и наименьшего общего кратного нескольких чисел.
1. Пусть - каноническое разложение числа а. Тогда все делители числа суть все числа вида
; (1)
0  1  1, 0  2  2, …, 0  k  k.
Доказательство: Пусть d делит а. Тогда (b, п. 1) a=dq и, следовательно, все простые делители числа d входят в каноническое разложение числа а с показателями, не меньшими тех, с которыми они входят в каноническое разложение числа d. Поэтому d имеет вид (1). Обратно, всякое d вида (1) делит а.
Пример. Все делители числа 720=24325 получим, если в выражении заставим 1, 2, 3 независимо друг от друга пробегать значения 1=0, 1, 3, 4; 2=0, 1, 2; 3=0, 1. Поэтому указанные делители будут 1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 9, 18, 36, 72, 144, 5, 10, 20, 40, 80, 15, 30, 60, 120, 240, 45, 90, 180, 360, 720.
2. Наибольший общий делитель нескольких чисел является произведением степеней вида p, где p – общий простой делитель всех этих чисел, а  - наименьший из показателей, с которыми p входит в их канонические разложения.
3. Совокупность общих делителей нескольких чисел совпадает с совокупностью делителей их наибольшего общего делителя.
Доказательство: Пусть d - общий делитель чисел а, ..., l. Тогда имеют место равенства вида a=da1, ..., 1=dl1, которые показывают, что: а) всякий простой делитель p числа d должен быть делителем и каждого из чисел а, ..., l, а также что: b) этот делитель р должен входить в каноническое разложение числа d с показателем, не превосходящим наименьшего из тех, с которыми он входит в канонические разложения чисел а, ..., l; обратно, каждое d, подчиненное условиям а) и b), очевидно, является общим делителем чисел а, ..., l.
Наибольшим общим наибольшим делителем, т. е. наибольшим из общих делителей (а, п. 2) является тот из последних, в каноническом разложении которого показатели степеней простых чисел точно равны наименьшим из тех, с какими эти простые числа входят в канонические разложения чисел а, ...,.l.
А всякий общий делитель, как имеющий в своем каноническом разложении все показатели не превосходящими соответствующих показателей в каноническом разложении наибольшего общего делителя, будет делителем последнего.
Пример. Наибольший общий делитель чисел 6791400=2332527311, 178500=22353717, 27720=23325711 равен 22357=420.
4. Наименьшее общее кратное нескольких чисел является произведением степеней вида p, где p - простой делитель по меньшей мере одного из этих чисел, а  - наибольший из показателей, с которыми p входит в их канонические разложения.
5. Наименьшее общее кратное нескольких попарно простых чисел равно их произведению.
6. Совокупность общих кратных нескольких чисел совпадает с совокупностью кратных их наименьшего общего кратного.
Доказательство: Пусть М - общее кратное чисел a, ..., l. Тогда имеют место равенства вида М=ad', …, М=dl', которые показывают, что: а) всякий простой делитель p каждого из чисел а, ..., l должен быть делителем и числа М, а также что: b) этот делитель p должен входить в каноническое разложение числа М с показателем, не меньшим наибольшего из тех, с которыми он входит в канонические разложения чисел а, ..., l; обратно, каждое М, подчиненное условиям а) и b), очевидно, является общим кратным чисел а, ..., l.
Наименьшим общим кратным, т. е. наименьшим из общих кратных (а, п. 3), является то из последних, в каноническом разложении которого показатели степеней простых чисел точно равны наибольшим из тех, с какими эти простые числа входят в канонические разложения чисел а, ..., l.
В случае, когда а, ..., l - попарно простые и, следовательно, каждый множитель вида p канонического разложения наименьшего общего кратного входит в каноническое разложение одного и только одного из чисел а, ..., l, наименьшее общее кратное последних, очевидно, равно их произведению.
Всякое общее кратное, как имеющее в своем каноническом разложении все показатели не меньшими соответствующих показателей в каноническом разложении наименьшего общего кратного, будет кратным последнего.
Пример. Наименьшее общее кратное чисел 1800=233252, 3780=223357, 8910=234511 равно 233452711=1247400.
1.3.Признаки делимости
1.1.3.Признаки делимости на числа от 2 до 12
Рассмотрим признаки делимости.
Признак делимости на 2.
Число делится на 2 в том и только в том случае, если его последняя цифра четная.
Признак делимости на 3.
Вычислите сумму цифр интересующего вас числа. Если эта сумма выражается более чем однозначным числом, найдите сумму цифр полученной суммы, и т.д. до тех пор, пока вы не придете к однозначному числу, которое мы назовем цифровым корнем исходного числа. Если цифровой корень кратен 3, то исходное число делится на 3. Если же цифровой корень не кратен 3, то нужно установить наибольшее 0, 3 и 6, которое не превосходит цифрового корня. Взяв разность между цифровым корнем и найденным числом, мы узнаем остаток от деления на 3 исходного числа. Например, число 61671142 имеет цифровой корень, равный 1. Это означает, что остаток при делении числа на 3 равен 1.
Признак делимости на 4.
Число делится на 4 в том и только том случае, если две его последние цифры образуют двузначное число, делящееся на 4. (Это нетрудно понять, если учесть, что 100 и кратные ему числа делятся на 4.) Число 61671142 оканчивается цифрами 42. Поскольку число 42 при делении на 4 дает остаток 2, то и данное число при делении на 4 также даст остаток 2.
Признак делимости на 5.
Число делится на 5 в том и только том случае, если оно оканчивается на 0 или на 5. Если число не делится на 5, то его последняя цифра либо меньше 5 (но больше 0), либо больше 5. В первом случае остаток от деления числа на 5 равен последней его цифре, во втором - разности между последней цифрой и 5.
Признак делимости на 6.
Нужно проверить делимость интересующие нас числа на 2 и на 3 (то есть на делители числа 6). Число делится на 6 в том и только в том случае, если оно четное, а его цифровой корень делится на 3.
Признак делимости на 8.
Число делится на 8 в том и только том случае, если его последние 3 цифры образуют число, делящееся на 8. (Справедливость этого признака следует из того, что все числа, кратные тысяче, делятся на 8.) В противном случае остаток от деления на 8 числа, образованного последними тремя числами, совпадает с остатком от деления на 8 исходного числа. (Аналогичное правило справедливо для любой степени двойки 2n: число делится на  2n в том и только том случае, если число, образованное n его последними цифрами, делится на 2n.)
Признак делимости на 9.
Число делится на 9 в том и только том случае, если его цифровой корень равен 9. В противном случае цифровой корень совпадает с остатком от деления исходного числа на 9. Число 61671142 имеет цифровой корень равный 1, следовательно, остаток от деления номера на 9 равен 1.
Признак делимости на 10.
Число делится на 10 в том и только в том случае, если оно оканчивается на 0. В противном случае последняя цифра дает остаток от деления числа на 10.
Признак делимости на 12.
Проверьте делимость интересующего вас числа на 3 и 4 - делители 12. Число делится на 12 в том и только в том случае, если оно делится одновременно и на 3, и на 4.4
Признак делимости на 11.
Двигаясь справа налево, будем попеременно приписывать цифрам нашего числа знаки плюс и минус (последняя цифра берется со знаком плюс, предпоследняя - со знаком минус и т.д.), после чего вычислим сумму всех цифр (каждую следует брать с ее знаком). Исходное число делится 11 в том и только том случае, если полученная сумма делится на 11 (число 0 считается делящимся на 11). Для числа 61671142, которое неоднократно уже использовалось, получаем 2-4+1-1+7-6+1-6=-6. Поскольку полученная сумма не кратно 11, исходное число - не делится на 11. Чтобы найти остаток от деления числа на 11, рассмотрим все ту же сумму цифр, взятых с переменными знаками. Если эта сумма меньше 11 и положительна, то она совпадает с остатком. Если же сумма больше 11, то ее нетрудно свести к числу, меньшему 11, поделив на 11 и взяв остаток. Если последний положителен, то он совпадает с остатком от деления на 11 исходного числа. Если же он отрицателен, прибавьте к нему 11. (В примере  -6+11=5. Означает, что наш номер при делении на 11 дает в остатке 5.)
Признак делимости на 7.
Заметим, что из приведенного списка признаков делимости нет признака делимости на 7, волшебное число средневековой нумерологии. Семерка - единственное число, для которого до сих пор не удалось найти простого признака делимости. Столь необычное поведение семерки уже давно обратило на себя внимание тех, кто занимается теорией чисел. Было предложено множество весьма любопытных и на первый взгляд не связанных между собой признаков делимости на 7. К сожалению, большинство из них  требует ничуть не меньше затрат времени, чем обычное ("честное") деление на 7.
Приведем один из них. Старый и хорошо известный признак делимости основан на том обстоятельстве, что число 1001 (случайно совпадающее с числом сказок в сборнике "1001 ночь") равно произведению трех простых чисел 7, 11 и 13. Число, делимость которого требуется проверить, разбивается справа налево на трехзначные группы цифр. Например, число 61671142 разбивается на группы 61/671/142. Трехзначным числам, образуемым цифрами каждой группы, приписываются поочередно знаки плюс и минус, так что самое правое число имеет знак плюс, после чего их складывают: 142-671+61=-148. При делении на 7, 11 или 13 полученное число дает тот же остаток, что и исходное.
 Признаки делимости нередко позволяют находить изящные решения числовых задач, которые без них были бы чрезвычайно трудными.
Рассмотрим, например, следующую задачу. Возьмем девять карточек, перенумерованных цифрами от 1 до 9, и тщательно их перетасуем. Какова вероятность того, что девятизначное число, образованное цифрами на разложенных в ряд карточках, будет делиться на 9? Поскольку сумма цифр от 1 до 9 равна 45, а число 45 делится на 9, вы сразу же знаете, что искомая вероятность равна 1 (событие достоверно). Возьмем теперь 4 карточки с цифрами от 1 до 4. Какова вероятность того, что четырехзначное число, образованное цифрами на выложенных в случайном порядке карточках, будет делиться на 3? Зная признак делимости на 3, вы сразу же можете сказать, что эта вероятность равна 0 (событие невозможно).
1.3.2 Признак Паскаля
Блез Паскаль (родился в 1623 году) - один из самых знаменитых людей в истории человечества. Паскаль умер, когда ему было 39 лет, но, несмотря на столь короткую жизнь, вошел в историю как выдающийся математик, физик, философ и писатель. Его именем названы единица давления (паскаль) и весьма популярный сегодня язык программирования.
Но научные интересы Блеза Паскаля не ограничивались созданием калькулятора: он нашёл общий алгоритм для нахождения признаков делимости любого целого числа на любое другое целое число, способ вычисления биномиальных коэффициентов, сформулировал ряд основных положений элементарной теории вероятностей.
Признак Паскаля.
Если сумма остатков при делении числа по разрядам на число делится на , то и число делится на .
Признаки делимости на 3 и 9. 
Число делится на 3, если его сумма цифр делится на 3. Число делится на 9, если его сумма цифр делится на 9.
Доказательство:
1, 10, 100, 1000, ... при делении на 3, на 9 дают в остатке единицу.
Значит, число делится на 3, если его сумма цифр делится на 3. Число делится на 9, если его сумма цифр делится на 9.
Признак делимости на 11. На 11 делятся только те числа, у которых сумма цифр, стоящих на нечётных местах, либо равна сумме цифр, стоящих на чётных местах, либо отличается от неё на число, делящееся на 11.
Доказательство:
10=11-1, недостаток 1;
100=11·9+1, избыток 1;
1000=11·91-1;
10 000=11·909+1,
100 000=11·9091-1,
1000 000= 11·90909+1.
Надо найти сумму всех остатков по разрядам числа.
Значит, на 11 делятся только те числа, у которых сумма цифр, стоящих на нечётных местах, либо равна сумме цифр, стоящих на чётных местах, либо отличается от неё на число, делящееся на 11.
Пример 1.1.4.. Делится ли число 865 948 732 на 11?
8+5+4+7+2=26;
6+9+8+3=26; 26-26=0
Можно получить еще один признак делимости на 11.
Признак делимости на 11. Если сумма, составленная при разбивании числа справа налево на группы по две цифры, делится на 11, то и число делится на 11.
Доказательство:
100=11·9+1, избыток в 1;
10 000=11·909+1,
1000 000= 11·90909+1.
Число делится на 11, если сумма, составленная при разбивании числа справа налево на группы по две цифры, делится на 11.
Пример 1.1.5. 2 37 84 95 68.
2+37+84+95+68=286.
2+86=8811
1.3.3 Диофантовы уравнения
Диофантовы уравнения (простейшего вида) - это уравнения вида ax+by=c, решаемые в целых числах (a, b, c - известные целые коэффициенты, x и y - неизвестные). Для них существует общий метод решения, который здесь и будет рассказан. Кроме того, мы затронем и методы решения уравнений в целых числах вообще.
Утверждение. Пусть a,b - целые и (a,b)=d. Тогда существуют целые m и n такие, что am+bn=d.
Этот факт называется линейным разложением НОД.
Доказательство: Коэффициенты m и n находятся конструктивно из алгоритма Евклида (он есть в прошлой лекции "Теория чисел"). Всесто того, чтобы формально расписывать процесс их нахождения мы рассмотрим его на примере. Найдем НОД и линейное разложение для 2003 и 232.
2003=8·232+147, поэтому (2003,232)=(232,147); 232=1·147+85, поэтому (232,147)=(147,85);
147=1·85+62, поэтому (147,85)=(85,62); 85=1·62+23, поэтому (85,62)=(62,23);
62=2·23+16, поэтому (62,23)=(23,16); 23=1·16+7, поэтому (23,16)=(16,7);
16=2·7+2, поэтому (16,7)=(7,2); 7=3·2+1, поэтому (7,2)=(2,1)=1.
Мы нашли НОД, равный 1. А теперь раскрутим эту цепочку в обратном порядке:
7=3·2+1, откуда 1=7-3·2 (выразили НОД через 2 предыдущих остатка в цепочке);
16=2·7+2, откуда 2=16-2·7 и 1=7-3· (16-2·7)=7·7-3·16 (выразили остаток через 2 предыдцщих и подставили);
23=1•16+7, откуда 7=23-1•16 и 1=7•(23-1•16)-3•16=7•23-10•16 (повторили предыдущую операцию);
62=2•23+16, откуда 16=62-2•23 и 1=7•23-10•(62-2•23)=27•23-10•62 (и так далее...);
85=1•62+23, откуда 23=85-1•62 и 1=27•(85-1•62)-10•62=27•85-37•62;
147=1•85+62, откуда 62=147-1•85 и 1=27•85-37•(147-1•85)=64•85-37•147;
232=1•147+85, откуда 85=232-1•147 и 1=64•(232-1•147)-37•147=64•232-101•147;
2003=8•232+147, откуда 147=2003-8•232 и 1=64•232-101•(2003-8•232)=872•232-101•2003....пока не поднимемся до самого верха, до двух изначальных чисел.
Другим примером Диофантовых уравнений является:
x2 + у2 = z2. (5)
Это Диофантово уравнение 2-й степени. Сейчас мы займёмся поиском его решений. Удобно записывать их в виде троек чисел (x,y,z). Они называются пифагоровыми тройками. Вообще говоря , уравнению (5) удовлетворяет бесконечное множество решений. Но нас будут интересовать только натуральные. Целые, положительные решения этого уравнения представляют длины катетов х, у и гипотенузы z прямоугольных треугольников с целочисленными длинами сторон и называются пифагоровыми числами. Наша задача состоит в том, чтобы найти все тройки пифагоровых чисел. Заметим, что если два числа из такой тройки имеют общий делитель, то на него делится и третье число. Поделив их все на общий делитель, вновь получим пифагороау тройку. Значит от любой пифагоровой тройки можно перейти к другой пифагоровой тройке, числа которой попарно взаимо просты.