Региональная научная конференция школьников «Инициатива молодых» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Региональная учебно-научная конференция учащихся 8-11 классов общеобразовательных... 5 1130.02kb.
Программа мероприятий 1 108.05kb.
Название конференции 1 36.13kb.
Апреля 2013 года состоится ХI ежегодная всероссийская научная конференция... 1 42.56kb.
Поволжская научная экологическая конференция школьников общие положения 1 35.34kb.
Неделя студенческой науки икб научная студенческая конференция (в... 1 41.77kb.
Отчет о работе научной конференции молодых ученых, аспирантов и студентов... 1 39.41kb.
Iv международная научная конференция моделирование-2012 1 54.37kb.
37-я студенческая научная конференция «Физика Космоса» 28 января... 1 32.11kb.
Научная конференция молодых исследователей научно-социальной программы... 2 580.45kb.
Первые шаги в науку 1 24.49kb.
Тесты простоты Тесты разложимости (вероятностные тесты простоты) 1 155.06kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Региональная научная конференция школьников «Инициатива молодых» - страница №1/1

Региональная научная конференция школьников

«Инициатива молодых»
секция Алгебра


Работу выполнили

Руслан Хусаинов

обучающийся 10 класса

МОУ-СОШ с. Кировское
Руководитель

учитель математики и


информатики высшей
квалификационной категории

Таутинова В.М.

2011 г.
г. Маркс



СОДЕРЖАНИЕ
ВВЕДЕНИЕ ……………………………………………………………………3

Глава 1. ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ ………………………...4

Глава 2. РАЗЛОЖЕНИЕ ЧИСЕЛ НА ПРОСТЫЕ МНОЖИТЕЛИ ………...5

Глава 3. ТЕСТЫ ПРОСТОТЫ ………………………………………………..9

Глава 4. САМОЕ БОЛЬШОЕ ПРОСТОЕ ЧИСЛО ………………………….14

ЗАКЛЮЧЕНИЕ ……………………………………………………………….15

ИСТОЧНИКИ ИНФОРМАЦИИ ……………………………………..………16


ВВЕДЕНИЕ

Число – одно из основных понятий математики, позволяющее выразить результаты счета или измерения.

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

Примеры составных чисел строить очень легко. Для этого нужно взять какие-нибудь два числа, отличные от 1, и перемножить их. Так, Поэтому числа 6, 1081, 11111111 составные.

Составные числа не исчерпывают весь натуральный ряд. Нельзя разложить на меньшие множители 2 и 3, 5 и 7, а также числа 239, 701 и многие другие. Подобные числа, т. е. натуральные числа, отличные от единицы, которые нельзя разложить в произведение меньших множителей, называются простыми.

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр организация EFF (Фонд Электронных Рубежей) назначила денежные призы соответственно в 150 000 и 250 000 долларов США. Чем же вызван интерес к простым числам?

Интерес к простым числам, возникший в глубокой древности, вероятно еще в школе Пифагора (V в. до н. э.), объясняется тем, что из них с помощью умножения можно построить все натуральные числа. Таким образом, простые числа – элементарные «строительные блоки» натуральных чисел.

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



Цель проекта:

1. Изучить свойства простых чисел.

2.  Узнать, существуют ли нестандартные приемы разложения чисел на
простые множители.

3.  Изучить способы, по которым можно определить, простым или


составным является данное натуральное число?

4. Узнать, существует ли самое большое простое число.


Глава 1. ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ

Пусть нам надо построить множество натуральных чисел N, а в качестве инструмента для этой работы имеется только операция сложения. Какие понадобятся материалы? Ясно, что на «складе» необходимо иметь большой (бесконечно большой!) запас единиц – из этих единиц-«кирпичиков» можно построить всё множество N. Действительно, сначала возьмем 1, прибавим ещё одну 1 – операция сложения нам разрешена – получим 2, прибавим ещё одну 1 – получим 3, ещё одну… . К любому числу можно прибавить ещё одну 1, и, таким образом, всё множество N будет построено.

А теперь пусть надо построить множество N, но сложение запрещено, разрешено применять только умножение. Возьмём 1 – начальный элемент множества N. Но путём умножения из единиц следующий элемент – 2 – не получить, её придётся брать со «склада». Такая же картина и с 3. 4 получим легко: надо умножить 2 на 2, но за 5 – снова на «склад». 6 – это 2*3, здесь тоже всё в порядке, но с 7 опять неладно! Зато 8 = 2*2*2 , 9=3*3, 10=2*5. 11 с помощью операции умножения из 1, 2, 3, 5, 7 не получишь, снова надо идти на «склад». «Складом» в этом случае будет множество простых чисел P. Таким образом, любое натуральное число – либо составное, и тогда его можно получить, перемножая некоторые простые числа, либо простое, и тогда его придётся взять из P, так как «создать» его при помощи умножения других чисел невозможно. Можно сказать так: каждое отличное от 1 натуральное число может быть разложено в произведение простых чисел. Такое разложение единственно, если не обращать внимания на порядок множителей. Это утверждение называется основной теоремой арифметики.

В «Началах» Евклида эта теорема отсутствует. И впоследствии она, вероятно, воспринималась как сам собой разумеющийся факт. Первая точная ее формулировка и доказательство приводятся в книге «Арифметические исследования» известного немецкого математика К.Ф. Гаусса (1777-1855), изданной в 1801 г. Эта важная теорема вскрывает структуру натуральных чисел по отношению к операции умножения. Она показывает, что все натуральные числа, кроме 1, получаются из простых с помощью всевозможных умножений, причем в результате различных умножений получаются различные числа.

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

В общем случае получаем разложение

(1)

где k1, k2, …, kr натуральные числа. Из основной теоремы арифметики следует, что, как бы мы ни раскладывали число N на простые множители, окончательное разложение (1) будет одним и тем же; оно называется каноническим разложением.


Глава 2. РАЗЛОЖЕНИЕ ЧИСЕЛ НА ПРОСТЫЕ МНОЖИТЕЛИ

При разложении чисел на простые множители используют признаки делимости. Разложим, например, на простые множители число 756.



  1. 2

  1. 2

  1. 3

  1. 3

  1. 3

  1. 7

1

Значит,


А как быть, если существующие признаки делимости чисел не позволяют определить первый множитель в каноническом разложении числа (например: 2077)? В частности, рассмотрим способы разложения составного числа на два множителя.

В XVII веке французский математик П.Ферма (1601-1665) предложил способ разложения чисел на множители, который основан на следующей идее: если число N может быть представлено в виде разности квадратов двух чисел a2-b2, то разложение его на множители получается немедленно:



N= a2-b2=a2-ab+ab-b2=a(a-b)+b(a-b)=(a-b)(a+b).

Будем последовательно строить числа вида a2-N и проверять, являются они квадратами целых чисел или нет. Как только разность a2-N станет равной квадрату целого числа b2, мы будем иметь равенство N= a2-b2 и, значит, разложение числа N на множители.

Первые числа этой последовательности будет выглядеть так:

a2-N, (a+1)2-N, (a+2)2- N, (a+3)2-N и т. д. Определим на сколько отличается следующее число от предыдущего:


  1. (a+1)2-a2 = a2+2a+1- a2= 2a+1.

  2. (a+2)2-(a+1)2= a2+4a+4-a2-2a-1=2a+3.

  3. (a+3)2-(a+2)2= a2+6a+9-a2-4a-4=2a+5.

Таким образом, второе число от первого отличается на 2a+1, третье от второго на 2a+3, четвертое от третьего на 2a+5 и т.д. Это значительно упрощает вычисления.

Попробуем таким образом разложить на множители число N=2077. Так как 452<2077<462, то начальное значение a равно 46 и первый член нашей последовательности есть 462-2077=39.

Определим числа, которые нам следует прибавлять для получения следующих членов:

2a+1=+1=93
2a+3= 93+2=95

2a+5=95+2=97 и т. д.

В итоге получаем последовательность:

39 (– не извлекается)

39+93=132 (– не извлекается)

132+95=227 (– не извлекается)

227+97= 324 ( = 18).

Таким образом, b= =18. Найдем a из формулы:

N= a2-b2; a2=N+b2; a=== = 49.

Тогда, 2077 = (49-18)(49+18)= .

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

Program metod_ferma;

Var n: longint;

a,k,r,x1,x2: real;

Begin

Writeln('Введите число n');

Readln (n);

a:=int((sqrt(n)))+1;

k:=sqr(a)-n;

r:=2*a+1;

While frac(sqrt(k))<>0 do

begin

k:=k+r;

r:=r+2;

end;
x1:=sqrt(n+k)-sqrt(k); x2:=sqrt(n+k)+sqrt(k);

Writeln('x1=',x1:10:0,' x2=',x2:10:0);

Readln

END.

Разложим с помощью этой программы на два множителя следующие числа: 2077, 10001, 11111, 1111111.



В результате тестирования данной программы мы видим, что задача разложения на множители очень трудоемкая. Например, при разложении числа 1111111 на два множителя методом Ферма, пришлось построить 1389 членов последовательности.

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

F7=227+1=2128+1=340282366920938463374607431768211457 составное. Лишь

в 1970 г. с использованием ЭВМ было найдено его разложение на множители: F7=59649589127497217причем оба множителя являются простыми числами. Известно, что F9=2512+1 составное. Но даже с помощью самых совершенных ЭВМ до сих пор не удается разложить это число на множители.

Глава 3. ТЕСТЫ ПРОСТОТЫ

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



Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:



  1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

  2. Пусть переменная p изначально равна двум – первому простому числу.

  3. Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)

  4. Найти первое, не вычеркнутое число, большее, чем p, и присвоить значению переменной p это число.

  5. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n

  6. Все не вычеркнутые числа в списке — простые числа.

Этот алгоритм можно немного улучшить следующим образом. На шаге 3, числа можно вычеркивать, начиная сразу с числа p2, потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем  n.

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

Как же узнать, простым или составным будет заданное число? Будут ли простыми, например, числа 1009, 1517 или число 11…1411…1, записанное 65 десятичными знаками?

Заметим, что каждый из множителей, в произведение которых раскладывается составное число, является его делителем. Поэтому можно сказать:



Правило 1. Натуральное число составное, если оно делится на некоторое меньшее его число, отличное от 1.

Чтобы проверить, пользуясь указанным правилом, будет составным число 1009 или нет, нужно проверить, делится ли оно на все числа из ряда 2, 3, 4, …, 1007, 1008, т. е. совершить 1007 делений. Это утомительное занятие. Его можно значительно сократить, если воспользоваться следующим правилом:



Правило 2. Каждое составное число N имеет делитель, больший 1 и такой, что квадрат его не превосходит N.

По этому правилу делители составного числа N следует искать среди чисел, квадраты которых не больше чем N. Из соотношения 312=961<1009<1024=322 следует, что если число 1009 составное, то у него есть делитель, содержащийся среди чисел 2, 3, 4, …, 31. Таким образом, количество делений при проверке, является число 1009 составным или нет, может быть сокращено с 1007 до 30. Разделив 1009 на каждое из чисел 2, 3, …, 31 убеждаемся, что 1009 не делится ни на один из делителей. Такой исход означает, что число 1009 составным не является.

Попробуем теперь объяснить, почему выполняется правило 2. Если N – составное число, то в соответствии с определением его можно разложить в произведение двух множителей, скажем a и b, т. е. N=, где a>1 ,b>1.

Пусть a. Тогда , и составное число N имеет делитель a>1, квадрат которого не превосходит N.

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

Program test_prost;

Var i,k,n:longint;

Begin

Writeln('Введите натуральное число n');

readln(n);

k:=2;

for i:=2 to round(sqrt(n)) do if n mod i = 0 then k:=k+1;

if k=2 then writeln('nпростое число')

else writeln ('n – составное число');

Readln

END.

С помощью данной программы были протестированы следующие числа: 13, 18, 9091, 99990001, 11111111 и найдены среди них простые.



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



Числа Мерсенна

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


2
р – 1, где р – простое число. Составим таблицу таких чисел.


р

2

3

5

7

11

13

17

19

2р

4

8

32

128

2048

8192

131072

524288

М

3

7

31

127

2047

8191

131071

524287

М(2) = 3, М(3) = 7, М(5) = 31 – простые числа, это видно сразу. Нетрудно убедиться, что и М(7) = 127 – тоже простое число. Но М(11) = 2047 = – число составное. Числа М(р) с ростом р увеличиваются очень быстро, и поэтому трудно установить, являются ли они простыми или составными. Леонарду Эйлеру удалось доказать, что М(31) = 2 147 483 647 есть простое число. Очень долго оно считалось самым большим из известных науке простых чисел, но уже в 1883 году Иван Михеевич Первушин сумел доказать, что М(61) = 2 305 843 002 913 693 951 есть простое число. В наше время с помощью ЭВМ найдено еще несколько простых чисел этого вида.



Числа Ферма

Пьер Ферма высказал предположение, что простыми являются все числа вида F(n) = .

Проверим это предположение для нескольких n, составив таблицу.


n

0

1

2

3

4

5

2n

1

2

4

8

16

32



2

4

16

256

65536

4294967296

F=

3

5

17

257

65537

4294967297

Первые числа – 3, 5, 17, 257 – простые. С помощью программы можно проверить, что 65 537 – тоже простое число. Хочется думать, что все F(n) – тоже простые, но оказывается, что F(5) = 4 294 967 297 – составное, оно делится на 641. Проверить это несложно, гораздо сложнее установить, что именно на 641 надо делить. Установил это Л. Эйлер. Любопытно, что до сих пор никому не удалось установить, имеются ли простые числа вида F(n) = при n, большем 4.



Близнецы

Пары простых чисел, одно из которых на 2 больше другого: 3 и 5, 11 и 13, 1997 и 1999 называются близнецами. До сих пор неизвестно, конечно или бесконечно множество простых чисел-близнецов. Самая большая (на сегодняшний день) пара близнецов была открыта в 1995 году: это числа

и

Репьюниты и палиндромы

Все предыдущие числа-гиганты были примечательны тем, что их совершенно невозможно не только запомнить, но и просто выписать. Однако можно назвать огромное простое число, запись и запоминание которого не вызовет почти никаких трудностей. Это число 111...11, состоящее из 1031 единицы. Подобные числа называют репьюнитами (от англ. repeat unit  – повторение единицы). Математики интересуются также и числами, в записи которых все цифры, кроме одной, одинаковые. Например, простое число 11...1911...1, слева и справа от девятки стоит по 874 единицы. Это число является к тому же и палиндромом, то есть читается одинаково слева направо и справа налево. А самый большой найденный палиндром, являющийся простым числом – 100...0146564100...01 (5901 нуль слева и столько же справа, – всего 11811 цифр). Забавно, что и количество цифр в этом числе, тоже палиндром.


Глава 4. САМОЕ БОЛЬШОЕ ПРОСТОЕ ЧИСЛО

Ученые открывают простые числа постепенно, все большие и большие. Но, может быть, когда-нибудь будет построено последнее, самое большое из возможных простое число? Оказывается, ответ на этот вопрос получили еще древние греки. В 9-й книге «Начал» Евклида содержится следующее утверждение:



Теорема. Множество простых чисел бесконечно.

Докажем эту теорему.

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

Рассмотрим число.

N= ,

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



Теорема доказана.

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа. Наибольшим известным простым числом по состоянию на февраль 2011 года является 243112609-1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Его нашли 23 августа 2008 года на математическом факультете Калифорнийского университета в Лос-Анджелесе в рамках проекта по поиску простых чисел Мерсенна. Простые числа Мерсенна давно удерживают рекорд как самые большие известные простые числа.



ЗАКЛЮЧЕНИЕ

До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены Эдмундом Ландау на V Международном математическом конгрессе:



  1. Проблема Гольдбаха (первая проблема Ландау): доказать или опровергнуть, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел.

  2. Вторая проблема Ландау: бесконечно ли множество «простых близнецов» – простых чисел, разность между которыми равна 2?

  3. Гипотеза Лежандра (третья проблема Ландау) верно ли, что между n2 и (n + 1)2 всегда найдётся простое число?

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

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



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


ИСТОЧНИКИ ИНФОРМАЦИИ

  1. Гальперин Г. «Просто о простых числах» // Квант. 1975. № 4.

  2. Нестеренко Ю. В. Алгоритмические проблемы теории чисел // Введение в криптографию / Под редакцией В. В. Ященко. — Питер, 2001.

  3. Ю. Матиясевич Формулы для простых чисел // Квант. 1975. № 5. -13.

  4. Н. Карпушина Палиндромы и «перевёртыши» среди простых чисел // Наука и жизнь. 2010. № 5.

  5. Д. Цагер Первые 50 миллионов простых чисел // Успехи математических наук. – 1984. № 6.

  6. http://wikipedia.org/