Элементы теории чисел

Занятие 7: Совершенные числа

Определение: Числа, которые равны сумме всех своих делителей (исключая само число), называют совершенными. Наименьшим совершенным числом является число 6: 6=1+2+3. За ним идет число 28: 28=1+2+4+7+14.

Теорема: Число является совершенным, если оно представляется в виде:

является простым числом Мерсенна.

Доказательство: Делителями числа P, очевидно, являются следующие числа:

Запишем сумму этих делителей которая равна

Если вы не помните формулы для суммы членом геометрической прогрессии,

то умножьте эту сумму на 2:

а затем, вычтя S, получите

Таким образом, сумма всех делителей числа P есть

а сумма всех делителей, кроме самого числа равна

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

Предполагаемые задачи:

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

Решение:

Занятие 8: Наибольший общий делитель. Наименьшее общее кратное

Возьмем некоторую дробь a/b, отношение двух целых положительных чисел a и b. Обычно мы стараемся привести ее к простейшему виду, то есть мы стараемся сократить множители, общие для a и b. Эта операция не изменяет значение дроби, например,

Общим делителем двух натуральных чисел a и b называется натуральное число d, которое является множителем как числа a, так и числа b.

Теорема: Если число d - общий делитель чисел a и b, то он также делит числа a +b и a-b

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

Чтобы получить сумму

необходимо найти общее кратное для чисел a и b, то есть число m, на которое делятся как число a, так и число b. Одно из таких чисел очевидно, а именно, их произведение m = ab; в результате получаем в качестве суммы дробей

Но существует бесконечно много других общих кратных для чисел a и b. Предположим, что мы знаем разложение этих двух чисел на простых множители:

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

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

.

Теорема: .

Доказательство: Перемножив два числа из (1), получим

.

Степень числа

в

является меньшей из двух чисел и , а в числе

она большая из них.

Предположим, что

.

Тогда степень числа в числе

равна , а в равна ;

следовательно, в их произведении

она равна ,

что в точности равняется степени произведения (2). Это показывает справедливость теоремы.

Предполагаемые задачи:

Найдите наибольший общий делитель пар чисел: а) 360 и 2010; б) 30 и 365; в) номера вашего телефона и вашего почтового индекса.

Ответ: а) ; б)

Для этих же чисел найдите наименьшее общее кратное.

Ответ: а) 72360; б)

Занятие 9: Взаимно простые числа. Алгоритм Евклида

Число 1 является общим делителем для любой пары чисел a и b. Может случиться, что единица будет единственным их общим делителем, то есть

В этом случае мы говорим, что числа a и b взаимно простые.

Одним из часто применяемых свойств взаимно простых чисел является следующее:

Если произведение ab делится на число c, которое взаимно просто с числом b, то число a делится на с.

Доказательство: Так как число с делит произведение ab, то простые множители числа с содержатся среди простых множителей чисел a и b. Но так как

то их не может быть среди множителей числа b. Таким образом, все простые множители числа с делят число a, но не делят число b, и они появляются в числе a в степенях, не меньших, чем в числе с, так как число с делит ab.

Позже мы используем другой факт.

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

,

то числа a и b являются квадратами:

Доказательство: Для того чтобы некоторое число было квадратом, необходимо и достаточно, чтобы все степени в разложении его на простые множители были четными. Так как числа a и b - взаимно простые, то любой простой множитель из содержится либо в a, либо в b, но не в обоих; отсюда простые множители чисел a и b должны иметь четные степени.

Пример: Найдите наибольший общий делитель чисел 1970 и 1066.



Следовательно, (1970, 1066) = 2.

Этот метод нахождения наибольшего общего делителя двух чисел называется алгоритмом Евклида.

Предполагаемые задачи:

Какие числа взаимно простые с числом 2?

Ответ: нечетные числа.

Почему

Решение: если простое число p является делителем чисел

,

то будет делителем числа

Занятие 10-11 : Задача Пифагора. Решение задачи Пифагора

Ранее упоминалось об одной из древнейших теоретико-числовых задач: найти все прямоугольные треугольники с целочисленными сторонами, то есть найти все целочисленные решения уравнения

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

удовлетворяющая решению нашего уравнения, называется пифагоровой тройкой.

Любая тройка чисел

,

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

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



Доказательство: Предположим, что например, x и y имеют общий делитель. Тогда они имеют общий простой делитель p. В соответствии

число p должно также делить и z. Итак,

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

Только что было получено что, числа x и y не могут быть одновременно четными. Докажем следующее утверждение.

Теорема: Числа x и y не могут быть одновременно нечетными.

Доказательство: Предположим, что

.

После возведения в квадрат этих чисел и сложения их, получим число

Это число делится на 2, но не делится на 4. В соответствии с (1), это означает, что делится на 2, но не делится на 4, но это невозможно, так как если делится на 2, то и z делится на 2, но тогда делится на 4.

Так как одно из чисел x и y - четное, а другое - нечетное, то z - также нечетное. Для определенности будем считать, что в наших обозначениях x - четное, а y - нечетное.

Чтобы найти простейшее решение уравнения Пифагора, перепишем его в виде

.

Так как x - четное, а y и z - оба нечетные, получаем, что все три числа

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

Обозначим

тогда наше уравнение примет вид

.

Числа и взаимно простые. Так как произведение этих двух взаимно простых чисел является квадратом то мы можем записать их в виде

Подставим и вместо и в уравнения (2) и (3) и получим



Проверка показывает, что эти три числа всегда удовлетворяют соотношению Пифагора

.

Остается определить, какие целые положительные числа m и n в действительности соответствуют простейшим треугольникам.

Теорема: Для чисел m и n необходимыми и достаточными являются следующие условия:

(m, n) = 1

m > n

Одно из чисел m и n четное, а другое - нечетное.

Доказательство: Сначала покажем, что если числа x, y, z образуют простейшую тройку, то данные условия выполняются. Мы уже показали, что первое условие является следствием того, что числа x, y, z взаимно простые. Второе условие следует из того, что числа x, y, z - положительны. Чтобы увидеть, что третье условие необходимо, замет, что если m и n оба нечетные, то в соответствии с (4) y и z были бы оба четные, в противоречии с результатами, полученными нами ранее.

Наоборот, если данные условия выполнены, то соотношения (4) определяют простейшую тройку: второе условие определяет положительность чисел x, y, z.

Предполагаемые задачи:

Найдите все пифагоровы треугольники, у которых длина гипотенузы не превосходит 100.

Решение: Если число с является величиной гипотенузы пифагорова треугольника, то произведение , где k - любое целое число, обладает теми же свойствами. Таким образом, достаточно рассмотреть лишь значения

,

которые не имеют делителей и могут быть величиной гипотенузы. Соответствующие значения: с = 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97.

Занятие 12-13: Определение сравнения. Свойства. Алгебра сравнений

Теория чисел имеет свою алгебру, известную, как теория сравнений.

Определение: Если a и b - два целых числа и их разность делится на m, мы выражаем это записью

которая читается так: a сравнимо c b по модулю m.

Делитель мы предполагаем положительным; он называется модулем сравнения.

Свойства.

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

1)

Доказательство: это является следствием того, что

2) означает, что и

Доказательство: Это следует из того, что

3)Из следует, что

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

поэтому

Сравнение

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

Свойство 1: Сравнения можно складывать.

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

Выполним сумму данных сравнений. По определению, это означает, что

где k и l - целые числа. Сложим данные уравнения и в результате получим



что можем записать в виде

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

Свойство 2: Также можно перемножить два сравнения.

Доказательство: Из (1) и (2) следует, что

таким образом

Свойство 3: Сравнение

может быть умножено на целое число с, при этом получается

Теорема: Если

, то

при условии, что числа m и с взаимно просты.

Доказательство: Первое сравнение означает, что

Если ,

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

Предполагаемые задачи:

Найдите остатки

Занятие 14-15: Возведение сравнений в степень. Теорема Ферма

Имеется сравнение

Как мы только что видели, можно умножить это сравнение на себя, получив

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

,

для любого положительного числа n.

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

Здесь первый и последний коэффициенты равны единице. Средними биномиальными коэффициентами являются где

Так как эти коэффициенты получаются в результате последовательного умножения на бином (x + y), то ясно, что они являются целыми числами.

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

и числителя

.

Однако знаменатель не содержит простого множителя p, поэтому после сокращения число p останется множителем в числителе. Отсюда можно сделать вывод: все биномиальные коэффициенты (кроме первого и последнего) делятся на p, если p - простое число.

Пусть теперь x и y будут целыми числами. Если мы рассмотрим формулу возведения бинома в степень как сравнение по модулю p, то можно сделать вывод, что для любых целых чисел x и y и простого p



Из этого сравнения можно сделать важные выводы. Применим его для случая x=y=1 и найдем, что

Возьмем затем x=2, y=1 и найдем, что

теперь, используя предыдущий результат, , получаем

Используя этот процесс, можно доказать по индукции, что

для всех значений числа

Случаи a = 0 и a = 1 очевидны. Так как каждое число сравнимо (mod p) с одним из остатков

Вывод:

Теорема: Для любого целого числа a и любого простого числа p

Это утверждение обычно называют малой теоремой Ферма.

Если сократить общий множитель a в обеих частях записи теоремы Ферма при условии, что a взаимно просто с числом p, являющимся модулем сравнения. Это дает следующий результат:

Теорема: Если является целым числом, не делящимся на простое число p, то

Это утверждение также называют теоремой Ферма.

Приложение теоремы Ферма: Произведение длин сторон треугольника Пифагора делится на 60.

Доказательство: Очевидно, достаточно доказать это для простейших треугольников. В соответствии с формулой

,

это произведение есть

Число P делится на 60 тогда и только тогда, когда оно делится на 4, на 3 и на 5. Так как одно из чисел m и n четно, то 2mn, а следовательно, и число P, делится на 4. Оно делится на 3, если хотя бы одно из чисел m или n делится на 3, но если ни одно из них не делится на 3, то P все же будет делится на 3, так как из условий

а также



следует, что

,

так что

Аналогично, число P делится на 5. Это очевидно, если m или n делится на 5. Если ни одно из них не делится на 5, то вновь по теореме Ферма получаем

§3.Конспекты занятий по темам

Простые и составные числа. Решето Эратосфена

Цели урока:

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

Развивающие: Развитие логического мышления, интереса к предмету.

Воспитывающие: Воспитать культуру математической речи.

Этапы урока:

Организационный момент.

Сообщение учащегося.

Обобщение материала по теме: Простые и составные числа.

Решение задач.

Введение нового материала.

Запись домашнего задания.

Этап урока	Деятельность учителя	Деятельность учеников
1	Здравствуйте, на сегодняшнем занятии мы с вами познакомимся с простыми и составными числами, а также как составлять таблицы простых чисел.	Слушают учителя и готовятся к занятию.
2	Перед тем как мы с вами начнем новое занятие, давайте выслушаем рассказ о научной деятельности Евклида.	Ученик выходит к доске и рассказывает доклад.
3	Должно быть одним из первых свойств чисел, которые открыл человек, было то , что некоторые из них могу быть разложены на два или более множителя, например, в то время как другие числа не могут быть разложены подобным образом, например, Запишите в свои тетради следующие определения: Когда число является произведением двух чисел a и b, то мы называем a и b множителями или делителями числа c. Каждое число имеет тривиальное разложение на множители Соответственно мы называем числа 1 и с тривиальными делителями числа с. Любое число , у которого существует не тривиальное разложение на множители, называется составным. Если число с имеет только тривиальное разложение на множители, то оно называется простым. Теперь мы с вами докажем одну теорему: Теорема: Любое целое число является либо простым, либо имеет простой множитель. Доказательство: Если с не является простым числом, то у него есть наименьший нетривиальный множитель p. Тогда p - простое число, так как если бы p было составным, то число с имело бы еще меньший множитель. Теперь мы подошли к нашей первой важной задаче в теории чисел: как определить, является ли произвольное число простым или нет, и в случае, если оно составное, то как найти какой-либо его нетривиальный множитель? На самом деле, чтобы узнать, имеет ли число с нетривиальный делитель, достаточно проверить, делится ли число с на простые числа, не превосходящие . Почему?	Слушают учителя. Записывают в тетрадь определения. Записывают доказательство. Высказывают свои точки зрения на данный вопрос. Потому, что если c =ab, где , то , следовательно,
3	Перед решение задач учитель раздает каждому ученику таблицу первой тысячи простых чисел Является ли число с простым(составным), если: а) , б)? Найдите простое число, следующее за простым число 2011.	Решение: а) Если Тогда простыми числами, не превосходящими, 9 буду следующие простые числа: 2, 3, 5, 7. Разделим эти простые числа на 91 и получим, что только число 7 нацело делится на 91. Получаем, что . б) Если Тогда простыми числами, не превосходящими 44, буду следующие простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. Разделим 1973 на эти простые числа и получим, что ни одно из простых чисел ни делит число с нацело и можно сделать вывод, что это число является простым. Число 2012 не будет являться простым, так как оно оканчивается четной цифрой. Проверим число 2013. .Тогда простыми числами, не превосходящими 45, буду следующие простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. Данное число будет делиться на простое число 3, следовательно, число 2013 не является простым. Число 2014 не будет являться простым, так как оно оканчивается четной цифрой. Число 2015 не будет являться простым, так как оно оканчивается цифрой 5. Число 2016 не будет являться простым, так как оно оканчивается четной цифрой. Проверим теперь число 2017. . Тогда простыми числами, не превосходящими 45, буду следующие простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. Разделим 2017 на эти простые числа и получим, что ни одно из простых чисел ни делит число с нацело и можно сделать вывод, что это число является простым. Мы получили, что 2017 является простым числом, которое следует за простым числом 2011.
4	Существуют таблицы простых чисел, простирающиеся до очень больших чисел. Как же составляются такие таблицы? Данная задача была, в известном смысле, решена (около 200 г. до н. э.) Эратосфеном, математиком из Александрии. Его схема состоит в следующем: запишите последовательность целых чисел от 1 до 15 (в действительности, мы можем записать последовательность целых чисел от 1 до нужного нам целого числа). Начнем с простого числа 2. Будем выбрасывать каждое второе число, начиная с 2(кроме самого числа 2), то есть все четные числа 4, 6, 8,10 и так далее, подчеркивая каждое из них. После этой операции первым неподчеркнутым числом будет число 3. Оно простое, так как не делится на 2. Оставив число 3 неподчеркнутым, будем подчеркивать каждое третье число после него, то есть числа 6, 9, 12, 15 и так далее. Следующим неподчеркнутым числом будет число 5, потом 7 и так далее. Повторяя этот процесс, мы, в конце концов, получим последовательность не подчеркнутых чисел; все они (кроме числа 1) являются простыми. Этот метод отсеивания чисел известен как “решето Эратосфена”. В действительности, можно продвинуться гораздо дальше по ряду простых чисел, если использовать для их хранения память ЭВМ. Подобным образом, в Научно-исследовательской лаборатории Лос-Аламоса были получены все простые числа до 100000000. Если внести небольшие изменения в метод решета, то мы сможем получить большую информацию. Предположим, что всякий раз, впервые подчеркивая числа, мы будем подписывать под ним простое число, с помощью которого оно отсеивается. Тогда 15 и 35 были бы записаны как и так далее. Таким образом, мы указываем не только простые числа, но и для каждого составного числа привели наименьшее простое число, являющееся его делителем. Такой список чисел называется таблицей делителей. Как мы видим, решето Эратосфена может быть использовано для построения таблиц простых чисел и таблиц делителей. Однако оно может быть использовано и для теоретических исследований и решении задач. Теорема (Евклид): Существует бесконечное число простых чисел. Доказательство: Предположим, что существует только k простых чисел: Тогда в решете не оказалось бы неподчеркнутых чисел, больших чем . Но это невозможно, так как произведение этих простых чисел будет отсеиваться k раз, по разу для каждого числа, поэтому следующее число не может быть подчеркнуто ни для кого из них.	Записывают последовательность чисел. Повторяют последовательность действий учителя в своих тетрадях. Записывают доказательство.
5	Какие из следующих чисел являются простыми: а) год вашего рождения; б) текущий год; в) номер вашего дома. Составьте таблицы простых чисел для каждой из сотен: 1 - 100, 101 - 200, …, 901 - 1000. Необязательное задание: Реализовать решето Эратосфена для чисел от 1 до 10000 в электронной таблице Excel.	Записывают домашнее задание.

Совершенные числа.

Цели урока:

Образовательные: Познакомить учеников с совершенными числами.

Развивающие: Развитие логического мышления, интереса к предмету.

Воспитательные: Воспитать культуру математической речи.

Этапы урока:

Организационный момент.

Введение нового материала.

Решение задач.

О современных исследованиях совершенных чисел.

Этап урока	Деятельность учителя	Деятельность учеников
1	Здравствуйте, на сегодняшнем занятии мы с вами познакомимся с совершенными числами.	Слушают учителя и готовятся к занятию.
2	Нумерология была распространенным увлечением у древних греков. Естественным объяснением этому является то, что числа в Древней Греции изображались буквами греческого алфавита, и поэтому каждому написанному слову, каждому имени соответствовало некоторое число. Люди могли сравнивать свойства чисел, соответствующие их именам. Запишите определение. Определение: Числа, которые равны сумме всех своих делителей (исключая само число), называют совершенными. Наименьшим совершенным числом является число 6: 6=1+2+3. За ним идет число 28: 28=1+2+4+7+14. Каждое совершенное число может быть представлено в виде является простым число Мерсенна, то С - совершенное число. Сформулируем это утверждение в виде теоремы и докажем его. Теорема: Число является совершенным, если оно представляется в виде: Доказательство: Делителями числа P, очевидно, являются следующие числа: Запишем сумму этих делителей которая равна Если вы не помните формулы для суммы членом геометрической прогрессии, то умножьте эту сумму на 2: а затем, вычтя S, получите Таким образом, сумма всех делителей числа P есть а сумма всех делителей, кроме самого числа равна Итак, наше число является совершенным. Из этого результата следует, что каждое простое число Мерсенна порождает совершенное число.	Слушают учителя. Записывают определение. Записывают доказательство.
3	Используя список простых чисел Мерсенна, найдите первые пять совершенных чисел.	Решение: Запишем первые пять чисел Мерсенна: 3, 7, 31, 127, 8191. Получим:
4	Мы с вами знаешь, что известно всего 46 простых числа Мерсенна, следовательно, мы знаем 46 совершенных числа. Все совершенные числа являются четными, но существуют ли нечетные совершенные числа? В настоящее время нам неизвестно ни одного нечетного совершенного числа, и вопрос о существовании нечетных совершенных чисел является одной из самых знаменитых проблем теории чисел. Если бы удалось найти такое число, то это было бы крупным достижением. Вы можете поддаться соблазну найти такое число, перебирая различные нечетные числа. Но не советую этого делать, так как по последним сообщениям Брайена Такхермана из IBM, нечетное совершенное число должно иметь по крайней мере 36 знаков.
5	Докажите что, сумма величин, обратных всем делителям совершенного числа, включая его самого, всегда равна 2. Докажите, что все совершенные числа являются треугольными числами.	Записывают домашнее задание.

Заключение

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

Изложена история возникновения и развития элективных курсов.

Определены дидактические и методические цели проведения элективных курсов.

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

Разработано содержание элективного курса “Элементы теории чисел”, подробно расписаны конспекты трех занятий.

Библиография

Атанасян, Л.С. Факультативные курсы по математике: 10-11 кл. / Л.С. Атанасян, А.А. Болибрух и др.- М.: НИИ школ Министерства образования РФ, 1989.- 378 с.

Болтянский, В.Г. Проект программы средней школы по математике/ В.Г. Болтянский, А.Н. Колмогоров, Ю.Н. Макарычев и др. // Математика в школе.- 1967.- № 1.- С. 4 - 23.

Дубровина, И.В. Формирование личности в переходный период от подросткового к юношескому возрасту/ И.В. Дубровина.- М.: Педагогика, 1987.- 184 с.: ил.

Каптерев, П.Ф. О разнообразии и единстве общеобразовательных курсов/ П.Ф. Каптерев // Педагогический сборник.- 1893.- № 1.- С. 1-18.

Кошкина, М.Д. Программы специальных курсов по математике / М.Д. Кошкина // Математика в школе.- 1967.- № 3.- С. 73 -78.

Немов, Р.С. Психология развития: учебные планы и программы курсов / Р.С. Немов.- М.: Московский психолого-социальный институт, 1998.- 72 с.

Никольская, И.Л. Факультативный курс: учебное пособие для 7-9 кл. / И.Л. Никольская.- М.: Просвещение, 1991.- 383 с.

Оре, О. Приглашение в теорию чисел/ О. Оре.- М.: Наука. Гл. редакция физ.-мат. лит., 1980.- 128 с.: ил.

Смирнова, И.М. Педагогика геометрии:монография / И.М. Смирнова.- М.: Прометей, 2004.- 336 с.

Успенский, В.А. Содержание факультативных занятий по математике / В.А. Успенский // Математика в школе.- 1967.- № 2.- С. 33 - 38.

Факультативный курс по математике: учебное пособие для 7-9 кл. средней шк. / сост. И.Л. Никольская.- М.: Просвещение, 1991.- 383 с.

Факультативный курс. Избранные вопросы математики: 7 - 8 кл. / Н.Я. Виленкин, Р.С. Гутер, А.Н. Земляков и др.; под ред. В.В. Фирсова.- М.: Просвещение, 1978.- 192 с.

Факультативный курс. Избранные вопросы математики: 9 кл. / И.Н. Антипов, Н.Я Виленкин, О.С. Ивашев-Мусатов и др.- М.: Просвещение, 1979.- 191 с.

Шарыгин, И.Ф. Факультативный курс по математике. Решение задач: 10 кл. / И.Ф. Шарыгин.- М.: Просвещение, 1989.- 352 с.

Шарыгин, И.Ф. Факультативный курс по математике. Решение задач: 11 кл. / И.Ф. Шарыгин, В.И. и др.- М.: Просвещение, 1991.- 384 с.

Размещено на Allbest.ru