Бюллетень
Викторина
Глава
Диплом
Доклад
Элементы теории чисел
 Скачать 0.53 Mb.
|
1 2 3
| Муниципальное общеобразовательное учреждение «Средняя школа №2 имени Героя России Валерия Иванова» города Волжска Республики Марий Эл Реферат на тему: «Элементы теории чисел» Выполнила: Поливина Л.В., учитель I категории г. Волжск, 2015 г. Содержание Введение 2 1. О роли задач в обучении математике 2 2. Как учит решать задачи современная школа? 3 3. Формулировка проблемы 4 Глава 1. Делимость целых чисел. Простые и составные числа. Основная теорема математики 5 Глава 2. Деление целых чисел с остатком 11 Глава 3. Признаки делимости и равноостаточности 13 Глава 4. Вычисление наибольшего общего делителя двух чисел 15 Глава 5. Решение уравнений в целых числах 16 5.1. Линейное уравнение с одним неизвестным 16 5.2. Линейное диофантово уравнение с двумя неизвестными 17 5.3. Примеры решения нелинейных уравнений 18 5.4. Пифагоровы треугольники 19 Глава 6. Числа Фибоначчи 21 Заключение 25 Используемая литература 26 Введение 1. О роли задач в обучении математике В обучении математике задачам всегда отводилась достаточно большая, если не решающая, роль. Сейчас всё большее распространение получает прогрессивный метод обучения через задачи как реализация системы проблемного обучения. Основные идеи этого метода находят в какой–то мере отражение в новых учебниках. Задачи становятся не только и не столько целью, сколько средством обучения. Исторически сложилось, что на ранних этапах развития математики решение задач было целью обучения. Ученик должен был заучить образцы и затем подводить под эти образцы решения задач. В основном решались типовые, стандартные задачи, принадлежащие классам алгоритмически разрешимых задач, т.е. таких, для которых существует общий метод (алгоритм) решения. Многообразные ситуации, возникающие на математическом и нематематическом материале, приводят как к стандартным, так и нестандартным задачам, алгоритм решения которых либо неизвестен, либо не существует. В последние десятилетия постепенное изменение целей обучения математике приводит к необходимости учить детей решению не только стандартных, но и нестандартных задач, которые нельзя отнести к классу алгоритмически разрешимых. Именно по отношению к нестандартной задаче возникает необходимость в вариативном поиске решения. "Задача предполагает необходимость сознательного поиска соответствующего средства для достижения ясно видимой, но непосредственно не доступной цели. Решение задач означает нахождение этого средства". [5, с. 143] Определённые группы задач, предназначенных для классных и внеклассных занятий, вполне пригодны для выработки "надлежащих навыков мысли", навыков, направленных на поиски решения задач. В книге [5, с. 165] М. И. Махмутов рассказывает об исследовании, проведённом группой учёных, математиков и психологов с целью выявления закономерностей активизации познавательной деятельности учащихся. Вот что он пишет в книге: Теоретическое осмысление работ лучших учителей помогло обнаружить в учебном процессе общую закономерность активизации познавательной деятельности учащихся: напряжение интеллектуальных сил ученика вызывается главным образом постановкой проблемных вопросов, проблемных познавательных задач и учебных заданий исследовательского характера. Это напряжение рождается в столкновении с трудностью в понимании и осмыслении нового факта или понятия и характеризуется наличием проблемной ситуации, высокого интереса учащегося к теме, его эмоционального настроя и волевого усилия. Роль задач в обучении математике невозможно переоценить. Через задачу естественно ввести проблемную ситуацию. Разрешив систему специально подобранных задач, ученик знакомится с существенными элементами новых алгоритмов, овладевает новыми техническими элементами. Применять математические знания в жизненных ситуациях учат соответствующие практические задачи. Итак, как видно из приведённого выше обзора мнений различных специалистов в области образования и обучения математике, задача является основным звеном внутри процесса обучения, а тем более такого, как проблемное и развивающее. 2. Как учит решать задачи современная школа? Однако использование задач в процессе обучения математике и в настоящее время ещё далеко от совершенства. В психологии и педагогике обращается внимание преимущественно на то, как решаются уже кем–то найденные и вполне чётко сформулированные задачи, а не на то, как они обнаруживаются и ставятся. В результате получается, что человек, привыкший видеть перед собой чётко и корректно сформулированную задачу, просто теряется в незнакомой ситуации, будь то хоть обычная некорректная математическая задача или некая задача, возникшая как следствие из практики (прикладная). В современном математическом образовании отмечается следующий актуальный аспект: изучение математики на всех этапах должно иметь развивающий характер и прикладную направленность. Молодёжи необходимо давать не просто конкретную сумму знаний, но и прививать ей навыки творчества, интерес к исследованию, формировать у неё положительную мотивацию. Интерес к учебной деятельности, подкрепляемый постоянным активным участием в открытии новых истин, проверке гипотез, поиском способа действий в задаче, является основным психологическим условием успешности этой деятельности. Школьные уроки математики по–прежнему нацелены на прохождение программы, а не на развитие мышления у детей. Учитель видит свою задачу в том, чтобы школьники с его помощью усвоили ещё одну порцию материала. Однако главная его задача – всемерно содействовать развитию познавательных возможностей у учащихся. Основную часть времени на уроке ученик проводит, решая задачи, и во многом от их особенностей (сложности, многогранности, сюжетной формы, последовательности и др.) и зависит, насколько успешным будет процесс обучения математике. Что же мы имеем на самом деле? На практике получается, что чаще всего процесс решения задач на уроке обладает некоторой рутинностью и оставляет ученику мало возможностей для творчества. Со временем такая специфика задач вырабатывает у ученика некоторый неправильный стереотип мышления, относящийся к решению задач. Ученик просто ищет стандартную ситуацию, к которой можно было бы применить известные формулы и теоремы, и теряется, когда предложенная задача требует даже несложного нестандартного подхода. По мнению Л.Фридмана, одной из основных в обучении математике функций задач является функция формирования и развития у учащихся общих умений решений любых математических (в том числе и прикладных) задач. Анализ школьных учебников математики показывает, что они содержат вроде бы достаточное (или даже избыточное) количество задач, из которых учитель может составлять наборы задач, ориентированные на разные классы и на разных учащихся. Однако учебный эффект получается, по мнению многих педагогов–исследователей, с которым мы вполне согласны, невысоким. Большинство учащихся, встретившись с задачей незнакомого или малознакомого вида, не знают, как к ней подступиться, с чего начать решение, и при этом обычно произносят печально известные слова: "А мы такие не решали". Каковы же причины этого широко распространённого явления? Автор книги [5] видит основную причину в неудовлетворительной постановке задач в обучении математике. Он пишет: "Проблема постановки задач в процессе обучения математике до сих пор не нашла удовлетворительного решения (ни в нашей стране, ни за рубежом). Ни с точки зрения содержания учебных задач, ни с точки зрения их целевого назначения, ни с точки зрения числа обязательных или необязательных задач или представления их в виде целостной системы". Сейчас, когда учащиеся не имеют систематических знаний о задачах и сущности их решения, главное внимание учащихся (и учителей) направлено на то, чтобы найти решение задачи и притом как можно быстрей. На заключительный анализ, на установление того, какие выводы можно сделать из выполненного решения, – на всё это уже не остаётся ни сил, ни времени, ни желания, а ведь это едва ли не главные аспекты решения задач. В школе невозможно, да и не нужно, рассматривать все виды математических задач. Сколько бы задач ни решали в школе, всё равно учащиеся в своей будущей работе встретятся с новыми видами задач. Поэтому школа должна вооружать учащихся общим подходом к решению любых задач. Одной из особенностей математики является алгоритмичность решения многих её задач. Алгоритмом, как известно, называется определённое указание относительно того, какие операции и в какой последовательности надо выполнить, чтобы решить любую задачу определённого типа. Конечно, очень большое количество задач не алгоритмизируется и решается с помощью специальных, особых приёмов. Поэтому способность находить пути решения, не подходящие под стандартное правило, является одной из существенных особенностей математического мышления, как об этом пишет академик Колмогоров. 3. Формулировка проблемы. Поискам ответов на эти вопросы и посвящена настоящая работа. Мы рассмотрим серию задач на натуральные и целые числа. Натуральные и целые числа знакомы с младших классов, но полезно и поучительно подойти к ним, владея аппаратом алгебры. Задачи о делимости и уравнения в целых числах служат излюбленным материалом для математических олимпиад и факультативов. Наряду с задачами о делимости, в данном задании рассматриваются уравнения в целых числах, вводится в практику метод математической индукции. Глава 1. Делимость целых чисел. Простые и составные числа. Основная теорема арифметики Напомним некоторые понятия и утверждения. Целые числа - это числа … -3, -2, -1, 0, 1, 2, 3, …; ряд целых чисел можно неограниченно продолжить как вправо, так и влево. Положительные целые числа называются натуральными. Наименьшее натуральное число – это 1, а наибольшего натурального числа не существует. Натуральное число n называют делителем целого числа m, если m =nk для подходящего целого числа k. В этом случае говорят, что m делится на n (нацело) и обозначают этот факт так: mn. Число m называют кратным числу n. Каждое число n имеет бесконечное множество кратных: 0, ±n, ± 2n, ± 3n, … Натуральное число, имеющее ровно два различных делителя - само себя и единицу, - называется простым. Целое число, имеющее больше двух различных делителей, называется составным. Наименьшее простое число равно 2, остальные простые числа являются нечётными. Согласно определению, число 1 не считается ни простым, ни составным. Если числа m,n делятся на натуральное число c, то с называется их общим делителем. Наибольший общий делитель чисел m и n обозначается НОД(m,n). Любое число, кратное m и n, называется их общим кратным. Наименьшее натуральное число, кратное m и n, называется наименьшим общим кратным m и n. Оно обозначается НОК(m и n). Числа, не имеющие общих делителей, кроме 1, называются взаимно простыми. Имеют вместо формулы сокращённого умножения (n- натуральное число): (İ) an- bn =(a - b)(an-1 + an-2b +… + abn-2 +bn-1); (İİ) a2n+1 + b2n+1 = (a + b)(a2n – a2n-1b + …+ab2n-1 + b2n). Для целых чисел a, b из тождеств ( I ), ( II ) следует, что an – bn делится на a-b и a2n+1 + b2n+1 делится на a + b. Принцип индукции: Если некоторое множество М натуральных чисел содержит число n0 и для любого k≥ n0 из того, что k принадлежит М, следует, что k+ 1 принадлежит М, то множество М содержит все натуральные числа n≥n0. Отсюда вытекает метод математической индукции для доказательства утверждений, зависящих от n. Согласно этому методу, если (1) доказываемое утверждение верно для начального значения n = n0 (чаще всего n0=1) («основание индукции») и если (2) из предположения, что доказываемое верно для некоторого n = k («предположение индукции») следует его справедливость для n = k + 1 (шаг индукции»), то утверждение верно для всех n≥n0. Следует подчеркнуть, что на практике нельзя пренебрегать ни основанием, ни шагом индукции. Основные свойства делимости Свойство 1. Если целое число а делится на m, а m делится на k, то а делится на k. Свойство 2. Пусть а и b- целые числа, n их общий делитель. Тогда: 1) а + b, а - b делятся на n; 2) аb делится на n (точнее, на n2). Следствие (из свойства 2). Если одно из чисел а или b делится на n, а второе не делится на n, то а + b, а – b не делятся на n. Свойство 3. Если целое а число делится на взаимно простые натуральные числа m и n, то а делится на их произведение mn. Свойство 4. Если а, b- целые числа, p- простое число и аb делится на p, то а или b делится на p. Свойство 5. Если а, b- целые числа, аb делится на натуральное число n, причём b и n взаимно просты, то а делится на n. Любое натуральное число можно разделить на простые множители. Для начала необходимо располагать списком простых чисел. Метод, позволяющий перечислить не очень большие числа изобрёл древнегреческий математик Эратосфен. В его честь метод носит название «решето Эратосфена», поскольку при его применении из ряда натуральных чисел постепенно отсеиваются составные числа. Пример 1. Найти все простые числа, не превосходящие 60. Решение. Выпишем все натуральные числа от 1 до 60 в виде таблицы.
Вычеркнем число 1 (оно не простое). Простые числа 2 и 3 выпишем справа, а из таблицы вычеркнем все числа, кратные 2 и 3. Простые числа: 2, 3.
В первой строчке сохранилось простое число 5, его переносим в список простых чисел, а кратные пяти вычёркиваем; так же поступаем с числом 7 (уже вычеркнутые числа пропускаем), после которого вычёркивать уже нечего. Оставшиеся числа переносим в список. Простые числа: 2, 3, 5, 7, 11, 13, 17, 19. 23, 29, 31, 37, 41, 43, 47, 53, 59.
Задача разложения больших натуральных чисел на множители весьма трудоёмка даже для современных компьютеров. На практике можно использовать следующие наблюдения. Наименьший (больший 1) делитель k числа n является простым: если n = kl, причём k= pq, где 1 ‹ p ‹ k, то p- делитель числа n, меньший, чем k. Если число n составное: n =ab, то хотя бы один из множителей не превосходит . Действительно, допустив противное, что a › , b ›, мы получили бы, что ab › * = n – противоречие. Пример 2. Разложить на простые множители n = 29359. Решение. На 2, 3, 5, 7 число n не делится, но делится на 11, так как 9 – 5 + 3 – 9 + 2 = 0. Делим: 29359 = 11* 2669, причём 2669 на 11 не делится. Далее будем искать делители числа 2669. Так как 512 ‹2669 ‹ 522, то искомым простым делителем может быть только число от 13 до 47. Число 13 исключается по признаку 5) из §3: для числа 2669 сумма числа десятков и учетверённого числа единиц 266 + 36 = 302, для полученного числа 30 + 8 =38 не делится на 13, поэтому берём следующее простое число —17. Получаем: 29369 = 11 * 17 * 157. Так как 132 ›157, а все простые числа, меньшие 13, не являются делителями данного числа, то 157- простое число, и искомое разложение на простые множители получено. Разберём метод разложения натурального числа на множители, не требующий перебора всевозможных его простых делителей. Этот оригинальный метод был предложен знаменитым французским математиком Пьером Ферма (1601 – 1665). Кстати, современные алгоритмы разложения чисел на множители используют сходные идеи. Предварительно выведем формулу для суммирования последовательных нечётных чисел. Заметим, что 1 = 12, 1 + 3 = 22 , 1 + 3 + 5 = 32, 1 + 3 + 5 + 7 = 42. Это наводит на мысль, что Sn = 1 + 3 + … + (2n – 1) = n2 для любого натурального n. Равенство можно вывести из формулы суммы первых n натуральных чисел 1 + 2 + … + n =, её наглядная иллюстрация приведена на чертеже.
3 2 1 Сумма 1 + 2 + 3 … + n равна площади ступенчатой белой фигуры (на рисунке n = 4). Пристроим к ней такую же, только перевёрнутую (заштрихованную) фигуру и получим прямоугольник со сторонами n и (n+1). Его площадь равна n(n + 1), а площадь половинки равна Вернёмся к сумме нечётных чисел. Добавим к Sn = 1 + 3 + … +(2n-1) сумму последовательных чисел: 1 + 3 + … + (2n – 1)+(2 + 4 + …+ (2n-2))= =n(2n-1), тогда Sn =n(2n-1)- 2b(n-1)/ 2 = n2, что и требовалось. Равенство Sn =1 + 3 + … +(2n-1) = n2 можно доказать также методом математической индукции. Равенство верно при n = 1. Предположим, что для некоторого k имеем Sk = 1 + 3 + … +(2k-1) = k2, тогда Sk+1 = Sk +(2k+1)= k2 + 2k + 1 = (k + 1)2, что и требовалось доказать. Таким образом, равенство справедливо для всех натуральных n. Ниже мы покажем применение метода математической индукции для доказательства делимости. Теперь изложим метод Ферма. Пусть n › 3- нечётное натуральное число. Будем прибавлять к нему последовательно нечётные числа 1, 3, 5, 7, и т. д., пока не получим квадрат некоторого числа L: n + 1 + 3 + 5 + 7 + … + (2k-1)= L2. Так как 1 + 3 + 5 + … + (2k-1) =k2, то n= L2 – k2 = (L - k)(L + k)- искомое разложение числа n. Пример 3. Разложить на множители число 2001. Решение. Число делится на 3, 2001 = 3*667. Для отыскания делителей числа 667 применим метод Ферма: 667+1 = 668, 667 +1+3 = 671, 667 + 1 + 3 + 5 = 676 = 262. Отсюда 667 = 262-32 = (26-3)(26+3) = 23*29. Ответ: 2001 = 3*23*29 В дальнейших примерах требуется выяснить простоту выражения или разложить его на множители. Пример 4. При каких целых n число 3n4 -8n2 -3 будет простым? Найти это простое число. Решение. Разложим данный многочлен от n на множители: 3n4 – 8n2 -3 = 3n4 -9 n2 + n2 – 3 = 3n2(n2 – 3) + n2 – 3 =(n2 – 3)(3n2+1). Произведение может быть простым числом только при таких целых n, при которых одна скобка равна 1, в то время как вторая является простым числом. Уравнение n2-3=1 имеет решения n=±2, при этом 3n2 + 1 = 13. При 3n2+1=1 получается n=0, тогда данное число -3 – не простое. Ответ: 13 при n=± 2. Пример 5 . Разложить 324 + 317 + 1 на два сомножителя. Решение. Заметим, что 324 + 317 + 1 = (38)3 + 3*(38)2 + 1 и дополним выражение до куба суммы, для чего прибавим к нему и вычтем 3* 38 = 39 = (33)3. Получим (38 + 1)3 – (33)3 = (38 + 1 -33)(316+ 38 + 1). Пример 6. При каких натуральных n число а =2n+1 делится на 3? Решение. Заметим, что если n нечётно, n=2k + 1, то по формуле (II), 22k+1 + 1 = (2+ 1)(22k-22k-1 + … -2 +1) делится на 3. Покажем, что при чётном n= 2k это неверно. Так число m=2k не делится на 3, то m=3s± 1, поэтому a= m2+ 1 = 9s2 ± 6s +2 не делится на 3, что и утверждалось. Ответ: 2n + 1 делится на 3 при любом нечётном n и не делится на 3 при любом чётном n. Пример 7. Доказать, что 2n+2* 3n + 5n -425 для любого натурального n. Доказательство. Применим метод математической индукции. При n= 1 выражение равно 23 * 3 + 5 – 4 = 25 25. Предположим, что 2k+2 * 3k + 5k – 4 = 25m (*) (m натуральное). Надо доказать, что 2k+3* 3k +1+5( k + 1) – 4 = 2k+3 * 3k+1 + 5k + 125 (**). Умножим равенство (*) на 6: 2k+3 *3k+1 +30k-24 = 150m, выразим из полученного равенства: 2k+3 *3k+1 = 150m-30k+24, подставим в выражение (**) и получим, что = 2k+3 * 3k+1 + 5k + 1 = 150m-25k+25 = 25(6m – k +1) делится на 25, что и требовалось доказать. Согласно принципу математической индукции, 2n+2 * 3n + 5n – 4 25 для любого натурального n. Основная теорема арифметики. Любое натуральное число n, большее единицы, можно разложить в произведение простых чисел. Это разложение единственно, с точностью до порядка следования сомножителей. Строгое доказательство этой теоремы первым дал К. Ф. Гаусс. Его можно прочитать, например, в учебнике [2]. Если в разложении на множители числа n встречаются равные простые числа, их удобно собирать в степени. В результате получается каноническое разложение: n =p1k1 p2k2…pmkm (III), где p1, …, pm – различные простые числа. Такое разложение однозначно, если потребовать, чтобы p1‹… ‹ pm. Например, 3780 = 2 * 2 * 3 * 3 * 3 * 5 * 7 = 22 * 33 * 5 * 7. Зная каноническое разложение натурального числа n =p1k1p2k2 … psks , можно найти все делители числа n, они имеют вид d = p1L1p2L2 … pmLm, где каждый показатель степени Li, может принимать значение от 0 до ki, i = 1, …, m. Делитель будет собственным делителем числа n (т. е. меньшим n), если Li ‹ ki хотя бы для одного i. Пример 8. Найти все делители числа 496 и сумму его собственных делителей. Решение. Разложим 496 на простые множители: 496 = 8 * 62 = 24 * 31. Найдём все собственные делители: 1, 2, 22= 4, 23 = 8, 24 = 16 и 31, 2 * 31 = 62, 4 * 31 = 124, 8 * 31 = 248. Сложим найденные числа: 1 + 2 + 4 + 8 + 16 + 31 + 2 * 31 + 4 * 31 + 8 * 31 = (для удобства подсчёта сгруппируем слагаемые) = (1 + 31) + (2 + 2 * 31) + (4 + 4 * 31) + (8 + 8 * 31) = 32 * (1 + 2 + 4 + 8) + 16 = 16 * (1 + 2 + 4 + 8 + 16) = 16 * 31 = 496 . Рассматривая одновременно два или более чисел, удобно включать в разложение каждого числа простые делители, входящие хотя бы одного из этих чисел, отсутствующие – в нулевых степенях (p0 = 1 для любого числа p). Например, для 715 = 5 * 11 * 13, 364 = 2 * 7 * 13 можно записать 715 = 20 * 5 * 70 * 11 * 13, 364 = 22 * 50 * 7 * 110 * 13. Пусть n = p1k1p2k2 … psks, m = p1L1p2L2 … psLs, где p1 ‹ p2 ‹ … ps, ki, Li ≥ 0 для всех i = 1, 2, …, s. Тогда:
Выведем последнее утверждение из 1 и 2: НОД (n, m) * НОК (n, m) = p1a1+β1p2a2+β2 … psas+βs , однако для каждого i от 1 до s из пары чисел a1 , β1 одно равно k1 , другое L1, так что ai + βi = ki + Li , откуда НОД (n, m) * НОК (n, m) = p1k1+L1p2k2+L2 … psks+Ls = nm, что и требовалось доказать.
В самом деле, любой делитель имеет вид d=p1L1p2L2 … pmLm,где каждый показатель степени Li, независимо от остальных, принимает ki + 1 значений, поэтому их надо перемножить. Так, количество делителей числа 496 = 24 * 31 (пример 8) равно (4 + 1)(1 + 1) = 10. Пример 9. Найти общий вид натуральных чисел, имеющих ровно 2005 делителей. Решение. По условию, число n с каноничным разложением n = p1k1p2k2 …pmkm имеет (k1 + 1) … (km + 1) = 2005 = 5 * 401 делителей. Так как число 401 простое (поверьте сами), n имеет всего два различных простых делителя с показателями k1 = 4, k2 = 400. Ответ: n = p14p2400, где p1, p2 – различные простые числа. Замечание. Из формулы 4 не трудно вывести, что число n, имеющее нечётное число делителей, является квадратом натурального числа, и обратно, так как в этом случае все показатели в каноничном разложении числа n будут чётными. Историческая сводка. Числа, которые, наподобие числа 496, равны сумме своих собственных делителей, ещё в древности были названы совершенными. Первые совершенные числа 6 и 28 были известны в древнем Вавилоне, следующее за 496 совершенное число 8128. Евклид, живший в 3 веке до н. э. и посвятивший арифметике три тома своего труда «Начала», доказал, что множество простых чисел бесконечно. Составлять таблицу простых чисел начали ещё древние греки (школа Пифагора, V век до н. э.). По мере накопления простых чисел стало ясно, что никакой общей формулы для их вычисления не существует. Поэтому стали искать выражения, дающие много простых чисел. Пьер Ферма занимался изучением чисел вида F = 2m + 1. Такие числа могут быть простыми только при m = 2k (k = 0, 1, 2, …). В самом деле, если допустить, что m = 2kL, причём число L нечётное, то F = (22k)L + 1 = (22k + 1)(22k - 1 – 22k - 2 + … ), по формуле(II). Первые числа Ферма Fk = 22k + 1 : F0 = 2, F1 = 22 + 1 = 5, F2 = 24 + 1 = 17, F3 = 28 + 1 = 257, F3 = 28 + 1 = 257, F4 = 216 + 1 = 65537 является простым. Однако больше ни одного простого числа Ферма по сей день не обнаружено, даже с помощью современных компьютеров. Между прочим, числа Ферма участвуют в решении задачи построения правильных многоугольников циркулем и линейкой. Гаусс доказал, что правильный n-угольник тогда и только тогда может быть построен, когда разложение n имеет вид n = 2m * p1p2 … ps , m ≥ 0, p1, …, ps – различные простые числа Ферма. Числа вида 2n – 1 могут быть простыми только при простом n: если n = mk, то 2n – 1 делится на 2m – 1 и 2k – 1, ввиду. Простые числа вида 2р – 1 (р- простое число) называют числами Мерсенна (Мерсенн – французский математик, 1588 – 1648). Наибольшие из известных пока простых чисел являются числами Мерсенна. В 2001 году проверена простота числа Мерсенна для р = 13466917; это число имеет 4053946 цифр. С 1995 года охота за простыми числами приняла глобальный характер: был создан проект поиска простых чисел с помощью компьютеров, объединённых сетью Интернета (GIMPS – the Great Internet Mersenne Prime Search). С такими огромными числами оказалось возможность работать только благодаря организации взаимодействия сотен тысяч компьютеров (на специальном сайте PrimeNet). Так, в поиске упомянутого простого числа участвовало 205000 компьютеров! Числа Мерсенна тесно связаны с совершенными числами. Теорема 36 в «Началах» Евклида гласит: если число n = 2p – 1 простое, то число n * 2p-1 является совершенным. В ХVİİİ веке Леонард Эйлер (1707 – 1783) показал, что любое чётное совершенное число можно представить в таком виде. Нечётных совершенных чисел до сих пор не обнаружено (с помощью ЭВМ проверены числа до 1050), а всего известны 52 совершенных числа. Глава 2. Деление целых чисел с остатком. Всякое целое число а можно разделить с остатком на любое натуральное число n, m, e представить а в виде a = nq + r, 0 ≤ r ‹ n, где q – целое число, частное, а r – остаток от деления а на n. Частное q и остаток r определены однозначно. Алгоритм деления чисел с остатком заключается в следующем. Если 0 ‹ а ‹ n, то следует принять q = 0, r = a , а если a › n, то из большего числа a следует вычитать меньшее n, пока не получится число, меньшее чем n – остаток. При a ‹ 0 надо вначале получить –a = sn + t, 0 ‹ t ‹ n, а затем a = -sn – t = -(s + 1)n + (n – t), q = -s – 1, r = n – t. Например, разделив 2004 на 7, получим 2004 = 286 * 7 + 2. Для числа - 2004 неверно было бы написать, что -2003 = - 286 * 7 – 2, так как остаток должен быть положительным. Чтобы удовлетворить этому условию, вычтем из первой части 7 и добавим к ней 7: -2004 = - 286 * 7 – 7 + 7 – 2 = - 287 * 7 + 5. Из теоремы о делении с остатком вытекает, что среди любых выписанных подряд n целых чисел ровно одно кратно n, а остальные дают при делении все остатки от 1 до n – 1(причём эти остатки идут подряд, начинаясь, возможно, не с 1). В частности: Так как чётные и нечётные числа чередуются, то произведение а (а + 1) любых двух последовательных положительных чисел делится на 2. Произведение (а - 1) а (а + 1) любых трёх последовательных чисел делится на 3. Кроме того, среди этих множителей встречаются два последовательных целых числа, а именно, а – 1 и а или а и а + 1. Отсюда следует, что при любом целом а произведение (а – 1) а (а + 1) делится на 6, по свойству 3, так как оно делится на взаимно простые числа 2 и 3. Пример 10. Доказать, что для любого целого n число a = + + целое. Решение. Сложим данные дроби: а = Разложим числитель на множители: 4n3 + 9n2 + 5n = n (4n2 + 4n + 5n + 5) = n(n + 1)(4n + 5). Представим последнюю скобку в виде 4n + 5 = 4(n – 1) + 9, так что n(n + 1)(4n + 5) = 4(n – 1) n (n + 1) + 9n(n + 1). Оба слагаемых делятся на 6, т. к. первое кратно произведению трёх последовательных целых чисел, и второе - произведение двух последовательных чисел на 9. Следовательно, данное число целое. В следующем примере используется наблюдение, что произведение четырёх последовательных целых чисел (n – 1) n (n + 1)(n + 2) делится на 24. Как замечено выше, оно делится на 3. Кроме того, среди записанных четырёх сомножителей один делится на 4 и ещё один (через один от него) делится ровно на 2. Таким образом, по свойствам делимости, произведение делится на 8, а т. к. числа 3 и 8 взаимно простые, то оно делится на 3 * 8 = 24. Пример 11. Доказать, что если p › 4 и взаимно просто с 6, то p2 - 1 делится на 24. Решение. Выражение р2 – 1 = (р – 1)(р + 1) – это часть произведения (р – 1)р(р + 1)(р + 2), делящегося на 24. Так как р не кратно 3 и 2, то же верно для р + 2, так что (р – 1)(р + 2) делится на 24, что и требовалось. Пример 12. Найти все целые числа n такие, что а = n + 10, b = n + 14, c = 9 - 2n являются простыми. Решение. Заметим, что числа a, b, c дают разные остатки при делении на 3, поскольку b – a = 4, b – c = 3n + 5, a – c = 3n + 1 не делятся на 3. Следовательно, одно из этих чисел делится на 3, а, будучи простым, равно 3. Если a = n+ 10 =3, n = -7, b = -7 + 14 = 7, c = 26 составное. Если b = n + 14 = 3, n = 11, c = 9 – 22 ‹ 0 не может быть простым. Остаётся c = 9 – 2n = 3, n = 3, a = 3 + 10 = 13, b = 3 + 14 = 17. Ответ: n = 3. |
1 2 3