Элективный курс: Теория делимости

Учитель математики: Кириллова Ольга Владимировна МОУ СОШ №22 г.Оленегорск-1

Содержание элективного курса по алгебре.

Тема «теория сравнений».

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

Пояснительная записка

Предлагаемый элективный курс предназначен для реализации в 8-9 классах школ математического профиля, направлен на знакомство учащихся с элементами теории конечных полей, развитие абстрактного мышления.

Этот курс может обеспечить мотивацию учащихся для более глубокого и осознанного изучения математики, и алгебры в частности. Вообще курс ориентирован на рассмотрение элементов высшей алгебры в профильной школе. Курс служит для внутри профильной дифференциации и углубленное изучение ряда вопросов. Постепенно методика обучения в профильных классах, на элективных курсах, должна постепенно развивать у учащихся навыки организации умственного труда и самообразования. Здесь и умение воспринимать объясняемый материал, достаточно быстро его конспектировать, с одной стороны, и умение работать с учебниками и иной литературой, с другой стороны. Так же учащиеся смогут научиться решать простые задачи из этого курса, в дальнейшем это умение понадобится для дальнейшего обучения в ВУЗах. Курс позволяет развивать умения учащихся мыслить и решать задачи в нестандартных ситуациях.

Кстати, одной из целей обучения является развитие уважения к книге (в первую очередь - учебной) вообще.

Цели курса:

• важной целью обучения является: знакомство учащихся с математикой как с наукой, общекультурной ценностью, выработка понимания ими того, что математика является инструментом познания окружающего мира и самого себя;

• знакомство с элементами теории конечных полей. А также может послужить базой для продолжения математического образования в вузах различного профиля;

• реализация поставленных целей будет способствовать овладению учащимися некоторыми знаниями и учениями в этой области.

Материал курса предназначен как для учеников, склонных к практическому, так и для тех, кто склонен к теоретическому мышлению.

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

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

В курсе имеются задания для состоятельного решения, которые способствуют эффективному освоению предлагаемого материала.

Основные формы организации учебных занятий: лекции, практические занятия и самостоятельные работа учащихся.

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

Задачами курса являются:

• знакомство учащихся с таким алгебраическим понятием, как конечное поле;

• актуализация знаний понятийно-терминологической базы алгебры;

• формирование умений решения задач по алгебре внутри этой темы;

• повышение математического уровня учащихся.

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

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

На изучение курса целесообразно отвести 18 часов по два часа в неделю, всего 9 недель.

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

После изучения предложенного курса, учащиеся пишут контрольную работу, и сдают зачет по теории.

Теоритические основы.

п.1. Теоретические основы делимости в кольце целых чисел.

Теорема1: Если оба числа a и b делятся на m, то их сумма a+b и их разность a-b делится на m.

Действительно, так как a делится на m, то a=km, где k - некоторое целое число. Точно так же b=lm, где l - некоторое целое число. Поэтому

a+b = km+lm = (k+l)m, a-b = km-lm = (k-l)m,

отсюда видно, что каждое из чисел a+b, a-b делится на m.

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

Докажем это, например, для случая трёх слагаемых. Слагаемые обозначим через a, b, c, а их сумму - через s:

a+b+c = s

Нам известно, что s делится на m и числа a и b делится на m, то есть s = qm, a=km, b=lm, где q, k, l - некоторые целые числа. Надо доказать, что и слагаемое c делится на m.

Мы имеем:

c = s-a-b = qm-km-lm = (q-k-l)m,

откуда и следует, что c делится на m.

Теорема 2: Если a делится на m и b делится на n, то ab делится на mn.

В самом деле, a=km, b=ln, и поэтому

ab = km×ln = (kl)mn,

то есть, ab делится на mn.

Эта теорема легко обобщается на случай трёх и большего числа сомножителей. Например, если a делится на m, b делится на n и c делится на p, то abc делится на mnp.

Следствие 2: Если a делится на m, то делится на (здесь - любое натуральное число).

Следствие 3: Если хотя бы один из сомножителей делится на m, то и произведение делится на m.

В самом деле, пусть a делится на m и пусть b - любое целое число. Так как b, очевидно, делится на 1, то (по теореме2) ab делится на m×1, то есть ab делится на m.

1.1.Деление с остатком.

Разделим 20 на 3 «в столбик».

Мы получили частное 6 и остаток 2. Но что это значит? Это значит, что если мы умножим число 20 на 2, то получим число, которое делится на 3 (и в частном будет 6), то есть, 20-2 = 3×6.

Иначе это можно записать так:

20 = 3×6+2

Рассмотрим еще один пример деления с остатком:

У нас получилось частное 16 и остаток 1. Это можно записать так:

49 = 3×16+1

Мы видим, что если число a дает при делении на 3 частное q и остаток r, то мы можем написать:

a = 3q+r

Вообще, если нам известно, что число a дает при делении на b частное q и остаток r, то мы можем написать

a = bq+r

Но не всякую запись a = bq+r можно прочесть как запись деления с остатком. Например, равенство 20 = 3×4+8 справедливое, но мы не можем сказать, что 20 при делении на 3 дает остаток 8. Остаток ведь должен быть меньше делителя! Точно так же запись 20 = 3×7+(-1) не означает, что 20 при делении на 3 дает в остатке (-1); остаток не может быть отрицательным. Значит, для того чтобы запись a = bq+r выражала деление a на b с остатком, нужно потребовать, чтобы r было неотрицательным числом, меньшим b, то есть 0≤r

Проведенные рассуждения вовсе не «доказывают» чего-либо; они лишь служат пояснением к тому, что такое деление с остатком. А теперь мы введем точное определение.

Определение: Пусть a и b - два целых числа, причем b>0. Если число a можно записать в виде a = bq+r, где 0≤r

1.2.Существование и единственность деления с остатком.

В предыдущем пункте было дано определение деления с остатком. В связи с этим определением естественно возникают два вопроса:

1. Всегда ли можно осуществить деление с остатком? Иначе говоря, если даны целое число a и натуральное число b, всегда ли можно подобрать такие целые числа q и r, что 0≤r

2. Единственным ли образом осуществляется деление с остатком? Иными словами, если число a записано двумя способами в требуемом виде:

a = b+, 0≤<;

a = b+, 0≤<,

то обязательно ли обе записи совпадают (то есть = и = )?

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

Теорема: Пусть даны целое число a и натуральное число b. Тогда можно подобрать такие целые числа q и r, что 0≤r

Из этой теоремы вытекает, что каждое целое число a может быть представимо:

либо в виде a = bq,

либо в виде a = bq+1,

либо в виде a = bq+2,

и т.д

либо в виде a = bq+(b-1)

Например, при b = 2 мы получаем: каждое целое число a может быть представимо либо в виде a = 2q (и тогда оно делится на 2, то есть четно), либо в виде a = 2q+1 (и тогда оно не делится на 2, то есть нечетно). При b = 3 получаем: каждое целое число a может быть представлено в одном из следующих видов: a = 3q, a = 3q+1, a = 3q+2. Это замечание часто используется при решении задач.

Пример 1. Доказать, что при любом целом n число делится на 6.

Решение: Разложим выражение на множители:

=

Число может быть представимо в одном из следующих видов: 6q, 6q+1, 6q+2, 6q+3, 6q+4, 6q+5. Если = 6q, то = =6q(6q+1)(6q-1); видно, что это число делится на 6. Далее, если число = 6q+1, то = = (6q+1)(6q+2)6q = 12(6q+1)(3q+1)q; и в этом случае число делится на 6 (и даже на 12). При = 6q+2 имеем: = = (6q+2)(6q+3)(6q+1) = 6(3q+1)(2q+1)(6q+1), так что число и в это случае делится на 6. Аналогично разбираются три оставшихся случая (когда имеет вид 6q+3, 6q+4, 6q+5). Итак, каково бы ни было , число всегда делится на 6.

Пример 2. Доказать, что ни при каком целом число не делится на 3.

Решение: При = 3q имеем:

= 9,

Откуда видно, что дает при делении на 3 остаток 1 и, значит, не делится на 3. Далее, при = 3q+1 имеем:

= = 9+6q+2 = 3(3+)+2;

Это число дает при делении на 3 остаток 2, то есть опять не делится на 3. Наконец, при = 3q+2 имеем:

= = 9+12q+5 = 3(3++1)+2;

Это число опять дает при делении на 3 остаток 2, то есть на 3 не делится. Итак, в любом случае число на 3 не делится.

п.2. Сравнения и их основные свойства.

Определение: Если два числа a и b имеют одинаковые остатки при делении на m, то говорят, что a и b сравнимы по модулю m, и пишут

a ≡ b(modm).

Запись a ≡ b(modm) можно прочитать так: a сравнимо с b по модулю m; это означает, что a и b имеют одинаковые остатки при делении на m. Использование этой записи делает формулировки и вычисления более удобными.

Докажем несколько простых теорем о сравнениях.

Теорема 1: Сравнение a ≡ b(modm) имеет место в том и только том случае, если разность a-b делится на m.

Иначе говоря, числа a и b в том и только в том случае имеют одинаковые остатки при делении на m, если a-b делится на m.

Доказательство: Предположим, что a ≡ b(modm), то есть a и b дают при делении на m один и тот же остаток r. Тогда

a = m+r,

b = m+r,

где, - некоторые целые числа. Вычитая одно равенство из другого, получаем: a-b = m-m = m(-), откуда и следует, что разность a-b делится на m.

Обратно, пусть a-b делится на m, то есть a-b = km. Проведем деление (с остатком) числа b на m:

b = qm+r, где 0≤r

Сложим равенства a-b = km и b = qm+r, получим

a = km+ qm+r = (k+q)m+r,

причем по-прежнему 0≤ra имеет тот же остаток r при делении на m, что и число b, то есть a ≡ b(modm).

Теорема 2: Сравнения можно почленно складывать и вычитать, то есть если a ≡ b(modm) и c ≡ d(modm) и a-c = b-d(modm).

Иначе говоря, если a и b имеют одинаковые остатки при делении на m и, кроме того, c и d имеют одинаковые остатки при делении на m, то числа a+c и b+d имеют одинаковые остатки при делении на m и также числа a-c и b-d имеют одинаковые остатки при делении на m. Как видите, с помощью сравнений эта теорема формулируется короче и удобнее.

Доказательство: Так как a ≡ b(modm) и c ≡ d(modm), то по теореме1 числа a-b и c-d делятся на m, то есть a-b = km, c-d = lm. Складывая эти два равенства, получаем a-b+ c-d = km+ lm, или (a+c)-(b+d) = (k+l)m.

Таким образом, разность (a+c)-(b+d) делится на m, а потому по теореме1a+c≡ b+d(modm).

Сравнения a-c ≡ b-d(modm) доказывается аналогично.

Теорема 3: Сравнения можно почленно умножать, то есть если a ≡ b(modm), c ≡ d(modm), то ac ≡ bd(modm).

Доказательство: Так как a ≡ b(modm) и c ≡ d(modm), то по теореме1a-b = km, c-d = lm. Поэтому ac-bd = (ac-ad)+(ad-bd) = a(c-d)+d(a-b) = alm+dkm = (al+dk)m, то есть разность ac-bdделится на m. Следовательно, по теореме1ac ≡ bd(modm). Конечно, теоремы 2 и 3 верны для любого числа слагаемых или сомножителей. Например, для трех сравнений: если a ≡ b(modm), c ≡ d(modm) и e ≡ f(modm), то a+c+e ≡ b+d+f(modm) и ace ≡ bdf(modm).

Следствие 1: Сравнения можно возводить в степень, то есть если a ≡ b(modm), то ≡(modm).

Следствие 2: Рассмотрим некоторый многочлен с целыми коэффициентами: . Если a ≡ b(modm), то значения, которые принимает этот многочлен при x = a и при x = b, также сравнимы между собой по модулю m, то есть

(modm)

п.3. Периодичность остатков при возведении в степень.

Рассмотрим последовательные степени числа 2:

и найдем, какие остатки дают эти числа при делении на 5.

Для нескольких первых чисел эти остатки легко найти:

,

,

(mod5),

(mod5).

Чтобы находить остатки дальше, нужно было бы вычислить дальнейшие значения степеней двойки: и так далее. Числа эти быстро возрастают, и считать становится труднее. Но можно находить остатки и не вычисляя степеней двойки. Для этого можно воспользоваться теоремой3 (из п.2). Именно, умножая сравнение ≡ 1(mod5) на 2, получаем:

Умножая полученное сравнение опять на 2, находим:

Еще раз умножив, получаем

,

затем

и так далее. Таким способом можно быстро найти остатки от деления на 5 чисел вида (не вычисляя самих степеней). Запишем то, что получается, в две строки, подписывая под каждой степенью её остаток от деления на 5.

2

2 4 3 1 2 4 3 1 2 4 3 1 2 …

Сразу же видно, что остатки периодически повторяются: после четырех остатков 2, 4, 3, 1 снова повторятся в том же порядке эти остатки, затем снова и так далее.

Рассмотрим еще один пример: остатки от деления степеней тройки на 7. Мы имеем:

Умножая полученное сравнение на 3, затем еще на 3 и так далее, получаем:

и так далее. Если мы продолжим эти вычисления, мы получим следующие две строки (где под каждым числом подписан его остаток от деления на 7):

3 2 6 4 5 1 3 2 6 4 5 1 3 …

И здесь наблюдается периодичное чередование остатков: после каждых шести остатков все повторяется сначала.

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

2 4 8 16 32 16 32 16 32 …

И здесь остатки повторяются, но только не с самого начала: первых три остатка не повторяются, а затем идет периодическое повторение: 16, 32, 16, 32, … .

Естественно возникает предположение, что при любых натуральных a и m остатки от деления чисел на m периодически повторятся (возможно, не с самого начала). Докажем, что это действительно так. Для этого возьмем первые m+1 степеней:

и рассмотрим их остатки при делении на m. Так как при делении на m может быть только m остатков (0, 1, 2, …, m-1), а чисел у нас m+1, то найдутся среди них два числа, имеющие одинаковые остатки при делении на m. Пусть, например,

(где l>0). Умножая на , получаем: при n≥k. Но это означает, что, начиная с , остатки, периодически повторяются (то есть, начиная сидут l остатков, которые снова и снова повторяются).

Проведенное рассуждение показывает, что периодичность остатков начинается с того места, где впервые обнаруживаются два одинаковых остатка. А для того чтобы обнаружить два одинаковых остатка при делении на m, достаточно (каким бы ни было основание a) взять m+1 первых степеней числа a.

Особенно просто обнаружить периодичное повторение остатков, если найдется такой показатель l, что Умножая это сравнение на, получаем: при любом натуральном n. Это означает, что с самого начала каждые l остатков периодически повторяются. Итак, если найдется такой показатель l, что , то остатки от деления чисел на периодически повторяются с периодом l.

Доказанные утверждения находят применение при решении ряда задач.

Пример. Найти остаток от деления числа на 7.

Решение: так как 222 = 7×31+5, то 222 ≡ 5(), и потому. Теперь посмотрим, как повторяются остатки степеней пятерки при делении на 7. Мы находим: , , , ,. Итак, . Возводя в степень k, получаем: при любом натуральном k. Но. Поэтому

.

Таким образом, число дает при делении на 7 остаток 6.

3.1. Взаимно простые числа.

Если число a делится на b, то говорят также, что b является делителем числа a. Например, числа 2 и -5 являются делителями числа 20; числа -6 и 8 являются делителями числа -24.

Определение: Два числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме 1 и -1. Иначе говоря, два числа называются взаимно простыми, кроме единицы.

Например, числа 8 и 15 взаимно просты. Действительно, число 8 не может делиться на числа, больше чем оно само. Значит, натуральные делители числа 8 можно искать только среди чисел 1, 2, 3, 4, 5, 6, 7, 8. Но на 3, 5, 6, 7 число 8 не делится. Остаются 1, 2, 4, 8-они и являются натуральными делителями числа 8. Но число 15 на 2, 4 и 8 не делится. Значит, числа8 и 15 имеют только один общий натуральный делитель - единицу, то есть эти числа взаимно просты.

Числа 21 и 34 тоже взаимно просты. А вот числа 24 и 28 не являются взаимно простыми, так как они имеют общие натуральные делители, отличные от единицы (например, их общим делителем является число2).

Рассмотрим три важные теоремы о взаимно простых числах.

Теорема 1: Если числа a и b взаимно просты, то существуют такие два целых числа и , что a+b = 1.

Теорема 2: Если число n делится на каждое их двух взаимно простых чисел a и b, то оно делится на их произведение ab.

Теорема 3: Если произведение ac делится на b и если числа a и b взаимно просты, то c делится на b.

Рассмотрим примеры применения теоремы о взаимно простых числах к решению задач.

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

Если n ≡ 0(), то ;

Если n ≡ 1(), то .

Итак, в любом случае , то есть число делится на 2. Далее, если n ≡ 0(), то ;

если n ≡ 1(), то ;

если n ≡ 2(), то .

Итак, в любом случае , то есть делится на 3.

Пример 2. Существует ли такое натуральное n, что число

Делится на 217?

Решение: Рассмотрим числа

1, 11, 111, 1111, …,

Каждое из них имеет какой-то остаток от деления на 217. Так как остатков от деления на 217 имеет 217(то есть 0, 1, 2, …, 216), а чисел у нас 218, то найдутся среди них два числа, имеющие одинаковые остатки от деления на 217. Пусть, например,

≡ ()

Тогда разность этих чисел делится на 217. Подписав первое число под вторым и произведя вычитание «в столбик», мы увидим, что разность этих чисел имеет вид:

,

то есть эта разность равна . По доказанному это число делится на 217. Остается применить теорему3: так как числа и 217 взаимно просты, то число должно делиться на 217. Мы видим, что ответ на поставленный вопрос утвердителен. Можно даже утверждать, что существует число, записываемое не более чем 217 единицами и делящееся на 217.

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

Вы, конечно, знаете, как определить, делится ли некоторое натуральное число на 10: для того чтобы некоторое натуральное число делилось на 10, необходимо и достаточно, чтобы последняя цифра этого числа была равна нулю.

Это признак делимости на 10. Например, число 257630 делится на 10, а число 38461 не делится. Хорошо известны также признаки делимости на 2 и на 5:

• Для того чтобы число делилось на 2, необходимо и достаточно, чтобы последняя его цифра была четной;

• Для того чтобы число делилось на 5, необходимо и достаточно, чтобы его последняя цифра была 0 или 5.

Похожим образом формулируются признаки делимости на 100, на 4, на 25. Несколько менее известны признаки делимости на 3 и на 9:

• Для того чтобы число делилось на 3, необходимо и достаточно, чтобы сумма его цифр делилась на 3;

• Для того чтобы число делилось на 9, необходимо и достаточно, чтобы сумма его цифр делилась на 9.

А можно ли придумать признак делимости на 11 или на 17 и как доказать сформулированные выше признаки делимости (например, признак делимости на 3)? Постараемся ответить на эти вопросы. Но прежде условимся о способе записи чисел. Если нас попросят написать шестизначное число, первая цифра которого a, вторая b, третья c, четвертая d, пятая e и шестая f. Написать abcdef нельзя - это будет обозначать произведение: abcdef=Поэтому, чтобы записать число, цифры которого обозначены буквами, мы условимся проводить над этими буквами черту. Таким образом, будет обозначать число, имеющее f единиц, e десятков, d сотен и так далее:

=

Теперь докажем сформулированный выше признак делимости на 3. Для примера мы будем рассматривать шестизначное число, но рассуждение имеет общий характер. Мы имеем:

10 ≡ 1()

Возводя это сравнение в квадрат, куб и так далее, получаем:

, , ,, …

Следовательно,

, ,,

, , .

Складывая почленно все эти сравнения, получаем:

,

или иначе:

.

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

Признак делимости на 11:

• для того чтобы число делилось на 11, необходимо и достаточно, чтобы разность между суммой цифр, стоящих на нечетных местах, и суммой цифр, стоящих на четных местах, делилась на 11.

Таким же способом можно получить признак делимости на 7. Мы имеем:

10 ≡ 3(), , ,

, ,

Так как , то дальше все будет повторяться. В результате мы получим следующие две строки чисел, причем под каждой степенью десяти подписано число, сравнимое с ней по модулю 7 (то есть дающее тот же остаток при делении на 7).

… 3 1 -2 -3 -1 2 3 1 -2 -3 -1 2 3 1

Отсюда мы получаем (взяв для примера шестизначное число ):

= .

В результате мы получаем следующее правило:

• чтобы узнать остаток от деления натурального числа на 7, нужно справа налево подписать под цифрами этого числа коэффициенты:

… -1, 2, 3, 1, -2, -3, -1, 2, 3, 1,

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

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

4 1 3 6

-4,2,9,6

(-4)+2+9+6 = 13

Таким образом, .

Этим способом можно найти признак делимости на любое число m. Надо только найти, какие коэффициенты следует подписывать под цифрами числа. А для этого нужно каждую степень десяти заменить по возможности меньшим числом (положительным или отрицательным), имеющим тот же остаток при делении на m, что и число. При m = 3 или m = 9 эти коэффициенты получились очень просты: все они равны единице. Поэтому и признак делимости на 3 или на 9 получился очень простой. При m = 11 коэффициенты тоже были несложные: они попеременно равны +1 и -1. А при m = 7 коэффициенты получились посложнее; поэтому и признак делимости на 7 получился более сложный.

Заметим, что иногда признак делимости можно получить проще. Пусть, например, нужно определить, делится ли некоторое число на 15. Конечно, можно, как указано выше, найти коэффициенты, подписать их и составить сумму произведений цифр на эти коэффициенты. Но можно поступить проще. Ведь если число делится на 15, то оно делится на 3 и на 5. Наоборот, если число делится на 3 и на 5, то по теореме2 §4 оно делится на 15. Значит,

• для того чтобы число делилось на 15, необходимо и достаточно, чтобы оно делилось на 5 и на 3, то есть чтобы оно оканчивалось нулем или пятеркой и, кроме того, сумма его цифр делилась на 3.

Аналогично

• для того чтобы число делилось на 6, необходимо и достаточно, чтобы оно делилось на 2 и на 3, то есть чтобы его последняя цифра была четной и, кроме того, сумма его цифр делилась на 3.

Таким же способом можно получить признак делимости на 8, 45 и другие числа.

п.4. Теорема Эйлера и Ферма.

Теорема Эйлера: Если a и m числа взаимно простые, тогда

.

Пример. Пусть m = 9, a = 14.

Тогда = () = - 3 = 6, далее, так как , имеем . Но по модулю 9:

, , ,

Итак, .

Теорема Ферма: для частного случая, когда m = p число простое, из теоремы Эйлера следует теорема Ферма: если p число простое и (a, p) = 1, тогда .

Пример. Пусть p = 11, a = 8. Ввиду того что 8 ≡ -3(), имеем ().

Но по модулю 11

,

Итак,

.

Часто применяется следующее следствие из теоремы Ферма: для простого p и любого a

На самом деле, по теореме Ферма

.

С другой стороны

:p при ()≠1;

поэтому при любом a произведение

×():p,

или

,

то есть

.

В заключение заметим, что предложение, обратное к теореме Ферма, не имеет место, то есть в случае, когда при .

,

нельзя еще утверждать, что n число простое.

Так, например, , однако 341 = 31×11.

Действительно,

,

поэтому

.

4.1 Применение теорем Эйлера и Ферма.

Теоремы Эйлера и Ферма имеют многочисленные применения. Рассмотрим примеры вычисления остатков при делении степеней на данное число.

Пример 1. Найти остаток при делении на 13.

По теореме Ферма , поэтому ; кроме того, .

Следовательно,

.

Итак, искомый остаток равен 12.

Пример 2. Найти остаток при делении на 83.

Теорему Ферма для данного случая нельзя применять, так как φ(83) = 82>40. Поэтому следует найти такие , чтобы при возможно больших значениях k, k≤40, получались бы при делении на 83 по возможности меньшие остатки.

; .

Итак, искомый остаток равен 28.

Пример 3. Найти остаток от деления на 15.

Так как

,то .

По теореме Эйлера

,

но = 8, поэтому .

Далее

.

Итак, при делении на 15 дает остаток 8.

Часовые разработки.

п.1. Часовое планирование.

Объем курса и виды учебной работы.

Виды учебной работы

Всего часов

Общая трудоемкость

18

Аудиторные занятия

18

Лекции

2

Практические занятия (семинары)

16

Вид итогового контроля: контрольная работа

Содержание курса

Разделы курса и виды занятий

№

п\п

Тематический план

Лекции, ч.

Практические

занятия, семинары, ч.

1

Основные теоретические положения темы: «Сравнения»

2

-

2

Теоремы о делимости.

-

1

3

Деление с остатком.

-

1

4

Существование и единственность деления с остатком.

-

2

5

Сравнения и их основные свойства.

-

2

6

Периодичность остатков при возведении в степень.

-

2

7

Взаимно простые числа.

-

2

8

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

-

3

9

Теоремы Эйлера и Ферма.

-

2

10

Итоговое занятие.

-

1

п.2. Почасовые разработки.

Семинар 1.Тема: Теоремы о делимости.

Задание 1. Доказать, что число записанное 81 единицей делится на 81.

Решение: :81

11111111100×+111111111×+…+111111111×+ 111111111 = ×(+…++1)

Следовательно, число, записанное 81 единицей делится на 81.

Задание 2. Докажите, что если ab+cd делится на a-c, то ad+cb тоже делится на a-c (a, b, c, d- целые числа, причем a≠c).

Решение: по условию (ab+cd):(a-c)

По следствию1: ab:(a-c) и cd:(a-c)

По следствию3: либо a:(a-c) и c:(a-c), то (ad+cb):(a-c)

(по следствиям 1 и 3).

либо b:(a-c) и d:(a-c), то (ad+cb):(a-c).

либо a:(a-c) и b:(a-c), c:(a-c) и d:(a-c), то (ad+cb):(a-c).

Семинар 2.Тема: Деление с остатком.

Задание 1. Найдите частное и остаток при делении на 7 следующих чисел: 3, 5, 10, 35, 100, 0, -1, -7, -12, -50.

Решение:, частное 0, остаток 3

, частное 0, остаток 5

, частное 1, остаток 3

, частное 5, остаток 0

, частное14, остаток 2

, частное 0, остаток 0

, частное -1, остаток 6

, частное (-1), остаток 0

, частное (-2), остаток 2

, частное (-7), остаток 1

Задание 2. Докажите, что если число a дает при делении на b остаток r, то a-r делится на b.

Решение: по условию a = qb+r, отнимем от обеих частей r, получим

a - r = qb + r - r, следовательно, a - r = qb, что и означает делимость (a - r) на b.

Задание 3. Найдите частные и остатки при делении на 10 следующих чисел: 3, 5, 10, 35, 100, 0, -1, -7, -12.

Решение:, частное 0, остаток 3

, частное 0, остаток 5

, частное 1, остаток 0

, частное 3, остаток 5

, частное 10, остаток 0

, частное 0, остаток 0

, частное -1, остаток 9

, частное -1, остаток 3

, частное -2, остаток 8

Семинар 3-4. Тема: Существование и единственность деления с остатком.

Задание 1. Докажите, что при любом n, :5

Решение: n() = n()() = n()()() = n()((()+5) = + +

Следовательно :5

Задание 2. Докажите, что при любом целом n, число четно.

Решение:

1. Если n нечетное, то число четное, а произведение нечетного числа на четное дает четное число.

Получаем, что четное число.

2. Если n четное, то число нечетное, но так как произведение четного числа на нечетное дает четное число, то получим, что четное число.

Задание3. Может ли быть число точным квадратом?

Решение: так как не является целым числом, следовательно, число не может быть точным квадратом.

Задание 4. Может ли число вида делиться на 121?

Решение:

Пусть

не делится на 121

Семинар 5-6. Тема: Сравнения и их основные свойства.

Задание 1. Доказать, что при любом натуральном m число делится на 133.

Решение: Мы имеем:

Но 144 ≡11(), и потому согласно следствию 1 п.2.

Умножая на 12, получаем:

≡ (), так что (). Далее, . А так как 121 ≡ -12().

Складывая сравнения:

(),

.

получаем

, то есть число делится на 133.

Задание 2. Докажите, что при любом целом n число делится на 6.

Решение: Всякое целое число n дает при делении на 6 один из остатков 0, 1, 2, 3, 4, 5, то есть имеет место одно из сравнений:

n ≡ 0(), n ≡ 1(), n ≡ 2(), n ≡ 3(), n ≡ 4(), n ≡ 5().

Если n ≡ 0(), то по следствию2:

,

то есть .

Если n ≡ 1(), то , то есть .

Если n ≡ 2(), то , то есть .

Если n ≡ 3(), то , то есть .

Если n ≡ 4(), то , то есть .

Если n ≡ 5(), то , то есть .

Итак, в любом случае , то есть делится на 6.

Задание 3. Найти две последние цифры .

Решение:

Семинар 7-8. Тема: Периодичность остатков при возведении в степень.

Задание 1. Найдите остаток от деления числа на 3.

Решение: .

.

Сложим полученные результаты:

,

.

Это означает, что число делится на 13.

Задание 2. Найдите остаток от деления на 11.

Решение: .

Таким образом, число при делении на 11 дает остаток 3.

Задание 3. Делится ли число на 10?

Решение: *7≡

.

Выполним вычитание:

,

.

Это и означает, что число делится на 10.

Задание 4. Докажите, что число делится на 7.

Решение: Так как 2222 = 7*317+3, то 2222 ≡ 3(), и потому .

Теперь посмотрим, как повторяются остатки степеней тройки при делении на 7. Мы находим:

, , , , .

Итак, . Возводя в степень k, получаем: при любом натуральном k. Но 5555 = 6*925+5. Поэтому:

Таким образом, число дает при делении на 1 остаток 5.

Так как 5555 = 7*793+4, то 5555 ≡ 4(), и потому:

≡ .

Теперь посмотрим, как повторяются остатки степеней четверки при делении на 7. Мы находим:

, .

Итак, . Возводя в степень k, получаем:

при любом натуральном k.

Но 2222 = 3*740+2. Поэтому

.

Складывая, получим:

,

.

Что доказывает делимость.

Семинар 9-10. Тема: Взаимно простые числа.

Задание 1. Докажите, что числа n и n+1 взаимно простые.

Решение: По теореме 1 .

Проведем доказательство от противного:

Предположим, что c>1, разделим n на c с остатком: 0≤r

,

то есть натуральное число r, меньшее, чем c, нам удалось представить виде . Но это не возможно, так как c - наименьшее натуральное число.

Значит, r=0, так что . Иными словами, число n делится на c.

Аналогично доказывается, сто и n+1 делится на c.

Значит, числа n и n+1 имеют общий делитель c>1.

Получили противоречие.

Задание 2. Докажите, что при любом целом n число делится на 30.

Решение: Если , то ;

Если , то ;

Если , то ;

Если , то ;

… … …

Если , то .

Итак, в любом случае , то есть делится на 30.

Задание 3. Докажите, что при любом нечетном n число делится на 24.

Решение: n принимает значения от 0 до 23.

n - нечетное: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23.

Если , то ;

Если , то ;

Если , то ;

… … …

Если , то .

Итак, в любом случае , то есть делится на 24.

Задача 4. Делится ли число на 48, при любом нечетном a?

Решение: - нечетное число, a произведение любого числа на 48 - четное число.

Следовательно, число не делится на 48.

Семинар 11-13. Тема: Признаки делимости.

Задание 1. Выведите признак делимости на 11.

Решение: Заметим, что 10 ≡ -1().

Возводя это сравнение в квадрат, куб и так далее, получим:

,

,

,

,

и так далее.

Следовательно,

; ;

; ;

;.

Складывая почленно все эти сравнения, получаем:

.

Задание 2. Делится ли число 542379 на 11?

Решение: .

Следовательно, число 542379 не делится на 11.

Задание 3: Делится ли число 8546216 на 7.

Решение:

8 5 4 6 2 1 6

.

Таким образом, , то есть число 8546216 делится на 7.

Задание 4. Вывести признак делимости на 12.

Решение: = .

.

Следовательно,

Складывая почленно все эти сравнения, получаем:

Задание 5. Выведите признак делимости на 8.

Решение: = .

Следовательно,

Складывая почленно все эти сравнения, получаем:

Семинар 14-15. Тема: Теоремы Эйлера и Ферма.

Задание 1. Найти остаток от деления на 45.

Решение: .

(23, 45) = 1, следовательно, по теореме Эйлера

.

.

.

.

Остаток равен 32

Задание 2. Показать, что 100 степень любого целого числа либо делится на 125, либо при делении на 125 дает остаток 1.

.

, по теореме Эйлера .

.

следовательно, .

.

.

Задание 3. Найти остаток от деления числа на 13.

Решение:

.

.

, по теореме Эйлера

.

, по теореме Эйлера

.

Остаток равен 10.

Семинар 16. Контрольная работа.

Задание 1. Найти остаток от деления числа на 5 не вычисляя.

Решение:

.

Задание 2. Найдите две последние цифры числа .

Решение:

Две последние цифры числа равны 32.

Задание 3. Делится ли число на 7?

Решение:

,

Возводя в степень , получаем:

при любом натуральном k.

.

Складывая полученные сравнения, получаем:

.

Таким образом, число делится на 7.

Зачет.

Учащиеся к зачету должны выучить все формулировки теорем и определений, изученных в элективном курсе.

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

Оценка в виде зачет или незачет.

Заключение

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

Изучение школьных программ и программ элективных курсов по математике показало, что, например, элементы современной абстрактной алгебры, в частности, элементы теории конечных полей в них не включены. В качестве элективного курса нами был разработан курс «Теории сравнений» для учащихся 8-9-х классов.

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

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

Все поставленные цели и задачи исследования выполнены.

Список использованной литературы

1. Епишева О.Б. Общая методика преподавания математики в средней школе / Тобольск, Изд-во ТГПИ им. Д.И. Менделеева, 1997

2. Методические рекомендации по изучению курса методики преподавания математики / Сост. Петрова Е.С., Саратов, Изд-во "Полиграфист", 1983

3. Учебники для средней школы и соответствующие пособия для учителя.

4. Сикорский К. П. «Дополнительные главы по курсу математики 7-8 классов для факультативных занятий». Издательство « Просвещение», Москва 1969г.

5. Михелович Ш. Х. «Теория чисел», государственное издательство « Высшая школа», Москва 1962г.

6. Скопец З. А. «Дополнительные главы по курсу математики 10 класса для факультативных занятий». Издательство «Просвещение», Москва 1970г.

7. Цели, содержание и организация пред профильной подготовки в выпускных классах основной школы: Рекомендации директорам школ, руководителям региональных и муниципальных управлений образованием. - М., 2003.

8. Элективные курсы в профильном обучении: Образовательная область «Математика»/ Министерство образования РФ - Национальный фонд подготовки кадров. - М., 2004.

9. Журнал «Математика в школе».

45