Элективный курс по математике для 8 класса на тему «Прикладные алгоритмы разложения целых чисел на сомножители».

Элективный курс по математике для 8 класса на тему «Прикладные алгоритмы разложения целых чисел на сомножители».

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

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

В рамках данного курса мы рассмотрим: Простые числа. Основная теорема арифметики. Метод Ферма. Деление целых чисел с остатком. Алгоритм Евклида. Сравнение целых чисел по модулю. p - метод - Полларда. После каждой темы представлены задачи для закрепления изученной темы.

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

Цель элективного курса:

обучающие

·        пробуждение и развитие устойчивого интереса к математике;

·        овладение конкретными математическими знаниями по программному материалу для продолжения образования;

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

развивающие

·        интеллектуальное развитие учащихся, формирование качеств мышления, характерных для математической деятельности;

·        расширять представления о числах, ознакомление учащихся с терминологией, помочь понять ее и правильно использовать;

·        Способствовать формированию самостоятельного приобретения знаний и умений.

Воспитывающие

·        вооружить конкретными знаниями, для выбора будущей профессии и продолжения образования;

·        понимание значимости математики для общественного прогресса;

·        подготовка к сознательному усвоению элементов прикладной алгебры.

Задачи данного курса:

1. Представить учащимся некоторые методы разложения целых чисел на сомножители.

2. Расширить представления о числах.

3. Развивать интерес учащихся к предмету.

4. Способствовать формированию самостоятельного приобретения знаний и умений.

На занятия отводится по 2 часа в неделю.

2.Учебно-тематическое планирование.

№ п/п	Тема		Количество Часов
1.	Простые числа		2
2.	Основная теорема арифметики		2
3.	Метод Ферма		2
4.	Деление целых чисел с остатком. Алгоритм Евклида		2
5.	Сравнение целых чисел по модулю		2
6.	ρ- метод Полларда	2

 

3.Тематическое планирование.

3.1.Простые числа.

Определение Натуральное число p>1, называется простым, если оно имеет в точности два натуральных делителя 1 и p.

Определение Натуральное число p>1 называется составным, если оно имеет более двух натуральных делителей 1, p и т.д.

Свойства простых чисел:

Свойство 1. Если p,- простые числа и p≠ ,то p не делится на .

Свойство 2. Если произведение нескольких чисел делится на простое число p, то хотя бы один из сомножителей делится на p.

Свойство 3. Для любого целого положительного числа n > 1 наименьший, отличный от единицы положительный делитель всегда представляет собой простое число.

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

Для того, чтобы находить простые делители относительно небольших чисел, необходимо иметь список относительно маленьких простых чисел.

Пример 1. Найти все простые числа от 1 до 50.

Решение:

Вычеркнем число 1.

Выпишем простые числа 2 и 3, а из таблицы вычеркнем, все числа кратные 2 и 3.

В первой строчке сохранится число 5, его тоже выписываем, все числа кратные 5 – вычеркиваем.

Точно так же поступаем с числом 7 и со всеми  простыми числами. После чего останутся числа:2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

Данная таблица поможет найти делители чисел < 50 →n = 2500.

Задания для самостоятельной работы:

1. Найти все простые числа от 1 до 60,

2. Найти все простые числа от 1 до 120.

 

3.2. Основная теорема арифметики.

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

Таким образом, если m – целое положительное число, а p,,,…,- простые, то m = ,××…×.Если среди чисел ,,…, есть одинаковые, то m =××…- каноническое представление целого числа.

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

Пусть целое положительное число, отличное от единицы.

1. Если число m- четное, то разделим его на первое простое число 2.

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

2. Если число m- нечетное, то если это, возможно, делим его на следующее простое число.

3.Частное от этого деления делим на три, если это возможно, если нет - переходим к п.3.

4. Делим полученное частное на следующее простое число и т.д., пока в частном не получится простое число.

Пример 1. Разложить на простые множители число n = 30191 (пример решается вместе с классом).

Решение: на 2,3,5 число 30191 не делится (по признакам делимости), но делится на 7, получим 30191=7 ×4313. Причем 4313 на 7 не делится. Далее ищем делители числа 4313. Воспользуемся свойством и определим границу делителей, не превосходящею =65, но так как мы уже проверили все числа от 2 до 7 и они не являются делителями, то будем проверять простые числа от 11 до 65. На 11,13,17 число 4313 не делится, но делится на 19 и получаем 4313=19×227. Аналогично ищем делители числа 227 среди простых чисел от 2 до 11, но так как все эти числа мы тоже проверили и они не являются делителями, то следует вывод, что 227 – простое число. Поэтому в результате получили 30191=7×19×227.

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

Задания для самостоятельной работы:

1. Разложить на простые множители число n= 239;

2. Разложить на простые множители число n= 3795

 

3.3.Метод Ферма.

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

Теорема. Нечетное число является простым тогда и только тогда, когда оно единственным образом представляется в виде разности квадратов целых неотрицательных чисел. N = nm ↔ N = - .

Данный метод основан на следующей идее: если число N может быть представлено в виде разности квадратов двух чисел (- , то разложение его на множители получается немедленно: N= - = (a +b) (a -b).

Будем последовательно строить числа вида ( - N) и проверять, являются они квадратами целых чисел или нет. Как только разность ( - N) станет равной квадрату целого числа , мы будем иметь равенство N=- и, значит, разложение числа N на множители. Первые числа этой последовательности будет выглядеть так:  – N, - N,  - N и т.д., где≤ a≤ .

Пример 1. Разложим на множители число N = 3977.

Решение:

Так как 3977<и = 1989, то 64≤ a≤ 1989. И первый член последовательности будет  - 3977 = 119,  - нацело не извлекается.

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

 - 3977 = 248,  - нацело не извлекается;

 - 3977 = 379, - нацело не извлекается;

 – 3977 = 512,  - нацело не извлекается;

 – 3977 = 647,  - нацело не извлекается;

 – 3977 = 784,  =28.

Таким-образом получили b = 28 при a = 69, подставим в формулу, найдем разложения числа 3977, 3977 = (69 +28)(69 – 28) = 97×41.

Пример 2. Разложить на множители число 621.

Решение:

Так как 621 <и = 311, то 25 ≤ a≤ 311. И первый член последовательности будет  - 621 = 4,  = 2.

Таким-образом получили b = 2 при a = 25, подставим в формулу, найдем разложения числа 621, 621 = (25 + 2)(25 – 2) = 27 × 23.

Задания для самостоятельной работы:

1. Разложить на множители число 2759.

2. Разложить методом Ферма число 323 на простые множители.

3.4. Деление целых чисел с остатком. Алгоритм Евклида.

Основную роль во всей арифметике целых чисел играет теорема о делении с остатком.

Теорема. Для любого целого a и целого b>0 существуют и единственные целые q,r, такие, что a = bq + r, 0≤ r ≤ b, где q называется неполным частным, а r – остатком от деления a на b.

Замечание. В частности, если r = 0, то a = b q и a делится на b.

Из теоремы следует, что при фиксированном целом b> 0 любое целое число a можно представить в одном из следующих видов:

a=bq;

a =+ 1;

a =b + 2;

……

a=b+ (b – 1).

При этом a < b, то будем иметь a = b ×0 + a, если a > 0 и a = b×(-1) + (b + a), если a < 0.

Пример 1. Разделить - 2023 на 20.

Решение.

Из равенства 2023= 20 × 101 + 3 получим – 2023 = - (20 × 101 + 3) = - 20 × 101 – 3 = - 20(102 – 1) – 3= - 20 × 102 + 17.

Таким образом, неполное частное – 102 (а не - 101), остаток равен 17.

Так же на делении целых чисел с остатком основывается алгоритм Евклида, который требуется для нахождения НОД двух целых чисел.

Представим  = a,  = b и обозначим через ,…, последующие делители в алгоритме. Далее делим число a на b и получаем - неполное частное,  – остаток от деления, после чего делим число b на остаток , и получаем  – неполное частное и  – остаток от деления, и так далее. Алгоритм останавливается, когда деление произойдет без остатка, т.е. = 0.

Тогда получаются следующие равенства:

a=  =  + , 0 ≤  < b,

b =  =  + , 0  < ,

 =  + , 0 ≤  < ,

…

=  + , 0 ≤  < ,

 =

Деление заканчивается, когда  = 0, при этом  = НОД (a, b) .

Пример 2. Найдем НОД чисел (5058,552) по Алгоритму Евклида.

Решение.

5058 = 552 × 9 + 90,

552 = 90 × 6 + 12,

90 = 12 × 7+ 6,

12 = 6 × 2 + 0.

Таким-образом НОД(5058, 552) = 6.

Задания для самостоятельного решения:

1. Разделить 1359 на 13.

2. Найти остаток при делении - 1473 на 73.

3. Найти НОД (2283, 216).

4.Найти НОД (839, 21).

3.5.Сравнение целых чисел по модулю.

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

″0″ - числа a вида a = km,

″1″ - числа a вида a = km + 1,

″2″ - числа a вида a = km + 2,

….

″m - 1″ - числа a вида a = km + (m – 1).

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

Определение 1. Если целые числа a и b таковы, что их разность делится на натуральное число m, то говорят, что a и b сравнимы по модулю m.

Обозначается это так: a ≡ b (mod m).

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

Пример 1.

545 ≡ 17 (mod 22), 24 ≡ 0(mod 4), - 258 ≡ - 6 ≡ 3 (mod 9).

Задания для самостоятельного решения.

1. Проверить: 969 ≡ 1(mod 44), - 15 ≡ 409 (mod 8), 385 ≡ 5432 (mod 4), 485 ≡ 5301(mod 9), 41 × 21 ≡ 51 × 35 (mod 14), 31 ≡ 5 (mod 13) и 68 ≡ 3 (mod 13).

2. Записать, используя отношения сравнимости: остаток при деления числа (- 421) на 19 равен 3.

3. Записать, используя отношения сравнимости: 957 ⁞ 29.

4. Записать, используя отношения сравнимости: m= 37 k + 5, m = 25 k + 3, m = 49 k + 7, m = 97 k + 5.

3.6. ρ – метод Полларда.

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

Идея данного метода заключается в следующем: Берем произвольный многочлен (чаще всего многочлен вида f (x) =  + a) и произвольное число . Далее строим последовательность  ≡ f () mod N, ≡ f ()mod N,  ≡ f () mod N и т.д., если члены последовательности начинают повторяться, то переходим к вычислению НОД ( - ,N). Если найдется такой НОД ( - , N), что 1 < НОД ( - ,N) < N, то найден искомый простой делитель.

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

Пример 1. Разложить на сомножители число N= 66.

Решение.

Возьмем произвольный многочлен f (x) =  + 1, и  = 3. Строим последовательность  =  + 1 = 10 ≡ 10 (mod 66),

 =  + 1 = 101 ≡ 35 (mod 66),

 =  + 1 = 1226 ≡ 38 (mod66),

 =  + 1 = 1445 ≡ 59 (mod 66),

 =  + 1 = 3482 ≡ 50 (mod 66),

 =  + 1 = 2501 ≡ 59 (mod 66).

Так как последовательность начала повторяться, то переходим к вычислению НОД.

При k = 1.

НОД ( - , N) = НОД (3 – 10, 66) = 1.

При k = 2.

НОД ( - , N) = НОД (10 – 35, 66) = 1;

НОД ( - , N) = НОД (3 – 35, 66) = 2. Следовательно, 66 = 2 × 33.

Переходим к новому шагу N = 33

Возьмем произвольный многочлен f (x) =  + 1, и  = 3. Строим последовательность  =  + 1 = 10 ≡ 10 (mod 33),

 =  + 1 = 101 ≡ 2 (mod 33),

 =  + 1 = 5 ≡ 5 (mod 33),

 =  + 1 = 26 ≡ 26 (mod 33),

 =  + 1 = 677 ≡ 17 (mod 33),

 =  + 1 = 290 ≡ 26 (mod 33),

Так как последовательность начала повторяться, то переходим к вычислению НОД.

При k = 1.

НОД ( - , N) = НОД (3 – 10, 33) = 1,

При k = 2.

НОД ( - , N) = НОД (10 – 2, 33) = 1;

НОД ( - , N) = НОД (3 – 2, 33) = 1.

При k = 3.

НОД ( - , N) = НОД (2 – 5, 33) = 3. Следовательно, 33 = 3 × 11.

Получаем разложение 66 = 2 × 3 × 11.

Задания для самостоятельной работы:

1. Разложить на сомножители методом p–Полларда число 387, 437.

2. Проверить методом Полларда можно ли разложить число 143, 213 на простые сомножители.