Элементы теории чисел
методическая разработка по алгебре (9, 10, 11 класс) на тему

Муниципальное общеобразовательное учреждение

«Средняя школа №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 =, её    наглядная иллюстрация приведена на чертеже.

4

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. НОД (n, m) = p1a1p2a2 … psas , где аi – меньший из показателей   ki, Li.
2. НОК (n, m) = p1β1h2β2 … psβ s , где βi – больший из ki, Li, i = 1, …,s.
3. НОД (n, m)* НОК (n, m) = nm.

Выведем последнее утверждение из 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, что и требовалось доказать.

4. Количество делителей числа n = p1k1p2k2 … pmkm можно найти по формуле (k1 + 1)(k2 + 1) … (km + 1).                                                   (İV)

В самом деле, любой делитель имеет вид 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.

Глава 3. Признаки делимости и равноостаточности.

 Для разложения на множители многозначного числа требуется найти хотя бы небольшие его делители. Для этого предназначены признаки делимости натуральных чисел по их цифрам. Вспомним простейшие признаки делимости и выведем дальнейшие. Пусть натуральное число имеет десятичную запись a = anan-1 ... a1a0 = 10n an + 10n-1 an-1 + … 10a1 + a0 

(a0 – цифра единиц, а1 – десятков и т. д.). По смыслу десятичной записи, число кратно 10k, если его последние k цифр равны нулю.

Сформулируем некоторые известные признаки делимости.

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

Чтобы объяснить признак делимости на 9, заметим, что для любого к = 1, 2 … разность 10к – 1 кратна девяти. Это видно из десятичной записи этих чисел. В самом деле, 10 – 1 = 9, 102 – 1 = 99, 103 – 1 = 999 и вообще 10к – 1 = 99 … 9 (к девяток). Данное число можно преобразовать так:                     а = (99 … 9 + 1)аn + (9 … 9 + 1) an-1 + … +(99 + 1) a2 + (9 + 1) a1 + a0 =         = 9 * (11 … 1* an+ 1…1*an-1 +…+    a1) + (an + an-1 + … + a2 + a1 + a0).

Так  как  подчёркнутое   выражение кратно 9(в частности, трём), то остаток от деления данного числа на 3 или на 9 равен остатку суммы цифр этого числа.

Займёмся делением на 11, 7, 13. Для деления на 11 учтём, что 11 = 10 + 1; из формулы (İİ) следует, 10 + 1,  1000 + 1,  вообще  нечётные  степени десяти, увеличенные на 1, делятся на 11.   (Также в силу формулы (İ)) делятся на 11 чётные степени 10, уменьшенные на 1:100 – 1 = 99,               1000 – 1 = 999 и т. д. Перепишем наше число в виде                                        а = а0 + (11 – 1) а1 + (99 + 1) а2 + (1001 – 1) а3 + … = а0 – а1 + а2 – а3 + … +11а1 + 99а2 + 1001а3 + …

Все подчёркнутые слагаемые кратны 11, поэтому остаток от деления данного числа на 11 равен остатку знакочередующейся суммы его цифр.

Например, число 1522906  11, так как 6 – 0 + 9 – 2 + 2 – 5 + 1 = 11 делится на 11.

Можно разбивать данное число на двузначные доли – грани, начиная справа на лево. Представим а в виде а = а1а0 + а3а2 * 100 + а5а4 * 1002+ … = =а1а0 + а3а2 + а5а4 + … +(99 * а3а2 + 9999 а5а4 + …); так как 99 = 100 – 1 делится на 11, то число, взятое в скобки, кратно 99. Тем самым делимость а на 11 определяется делимостью суммы двузначных граней.

Пример 13. Делится ли на 11 число а = 94317991999?

Решение. Разбиение на двузначные грани 9/43/17/99/19/99. Вычислим их сумму 9 + 43 + 17 + 99 + 19 + 99 = 286. Не производя деления, подсчитаем сумму двузначных граней полученного числа: 2 + 86 = 88 – делится на 11, следовательно, 286 делится на 11, как и данное число.

    Приведём пример применения объединённого признака делимости на 7, 11, 13.

Пример 14. Являются ли 7, 11, 13 делителями числа 5159539?

Решение. Разобьём данное число справа налево на трёхзначные числа (грани): 5/159/539 (последняя грань однозначная). Знакочередующая сумма полученных чисел равна 539 – 159 + 5 = 385. Так как 385 = 5 * 7 * 11 делится на 7 и 11, то данное число делится на 7 и 11, но не делится на 13. Остаток от деления на 13 данного числа такой же, как у 385, т. е. 8.

Доказательство признака опустим, только обратим внимание, что причина в разложении 1000+ 1 = 1001 = 7 * 11 * 13.

Аналогично, признак делимости на 37 по трёхзначным граням получается, если учесть, что 1000 = 999 + 1 = 37 * 27 + 1

Пример 15. Найти все пятизначные числа вида 71Х1Y, делящихся на 132.

Решение. Искомое число должно делиться на 3, 4, и 11. Сумма его цифр равна 9 + X + Y, так что X +Y  3. Знакочередующаяся сумма цифр Y – 1 + X – 1 + 7 = X + Y + 5 должна делиться на 11, откуда    X + Y = 6.  Для делимости на 4 необходимо, чтобы двузначное число 1Y делилось на 4, откуда Y = 2 или 6. Соответственно, X = 4 или 0.

Ответ: 71412 и 71016. 

Закончим параграф несколькими частными признаками делимости.

Пример 16. 1)Трёхзначное число, написанное одинаковыми цифрами, делится на 37.

2) Если сумма цифры единиц с учетверённой цифрой каждого из остальных разрядов числа делится на 6, то число делится на 6, и обратно.

3) Пусть а, b, c, d обозначают соответственно единицы, десятки, сотни и тысячи некоторого числа N. Число N делится на 4, если a + 2b делится на 4, и обратно; оно делится на 8, если a+ 2b + 4c a делится на 8, и обратно; оно делится на 16, если a + 2b +4c + 8d делится на 16 и b – число чётное, и обратно.

4) Если сумма цифр трёхзначного числа равна 7, то число будет делиться на 7, если цифра единиц равна цифре десятков.

5) Если у числа сумма количества всех десятков с учетверённой цифрой единиц делится на 13 , то само число делится на 13.

6) Если сумма удвоенной цифры единиц и утроенного числа десятков числа N делится на 17, то N делится на 17.

Доказательства. 2) a -  (a0 + 4a1 + 4a2 + …) = 10a1 +100a2 + …- (4a1 + 4a2 + …) = 6a1 + 96a2 + … делится на 6.

3) Рассмотрим делимость на 8. По основному признаку, 100c + 10b + a  должно делиться на 8, тогда 100c + 10b + a –(4c + 2b + a)= 96c + 8b =

8 (12c + 1 ) делится на 8, что и требовалось.

6) Обозначим через М число десятков числа а, тогда а =10М + а0 . По условию, 3М + 2а0 =17k ( k натуральное ), следовательно, 2a = 20M + 2a0= 20M + ( 17k – 3M ) = 17M + 17k . Получили, что 2а кратно 17, а так как 2 и 17 взаимно просты, то само а делится на 17 , что и утверждалось.

Глава 4. Вычисление наибольшего общего делителя двух чисел.

    Чтобы найти НОД двух натуральных чисел  a u b, не обязательно знать их разложения на простые множители. Существует иной способ, основанный на делении с остатком. Он известен как алгоритм Евклида.

Допустим, a › b, и разделим а на b с остатком: a = bq0 + r1.

Если r1= 0 ,то d = НОД (а, b)= b ; если r1  0, то НОД ( a, b) = НОД ( b, r1 ). В самом деле, так как a, b делятся на d , то и  r1 делится на d, по свойству 1 делимости. Наоборот, если с делитель b и r1, то число а = bq0 + r1 будет делиться на с, т. е. с является общим делителем a и  b.

Затем разделим b на   r1  : b =r1q1 + r2 . Если r2 = 0, то НОД ( b1r1)= r1 = d. В случае r1  0 получим  d = НОД (r1, r2). Теперь разделим  r1    с остатком на r2 ‹ r1  : r1 = r2q2 + r3   и т.д. Так как после каждого деления числа уменьшаются: a › b › r1 › r2 ›, … то найдётся такой номер n, что rn-2 = rn-1qn-1 + rn, rn ≠ 0 , rn-1 = rnqn. На  этом  процесс   закончится,   причём

d =НОД(а,b)= НОД (rn-1 ,rn) =rn. 

Пример 17. Найти НОД (1176, 315).

Решение. Представим  решение  как   последовательность   делений    с остатком.

Ответ:  НОД (1176, 315) = 21. 

 С помощью алгоритма Евклида  можно найти такие целые числа x, y, что ax + by + = d.

Покажем это для чисел примера 17. Имеем  d =  r4 =   r2 – r3 ,  r3 = r1 – 2r2 , r2 = b –r1 ,    r1 = a – 3b .   Подставляя эти соотношения друг в друга, находим d =r2 – ( r1 – 2r2 )= 3r2 – r1 = 3 ( b – r1 ) – r1 = 3b – 4 r1 =3b – 4r1 = 3b- 4 ( a – 3b ) = -4a + 15b.

Окончательно, 21 = -4 * 1176 + 15 * 315.

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

Пример 18. Определить, на какие натуральные числа может сокращаться дробь  при целых х. 

Решение. Пусть d – общий делитель числителя и знаменателя. Тогда

    , для подходящих целых  l, k. Исключим х из этих  

уравнений: а т.к. 23 – простое , то d = 23.

Ответ: На  23.

Замечание. Чтобы найти все  значения х, при  которых  это  возможно, требуется решить уравнение  5l – 3k =23. Решение  уравнений  в   целых числах рассматривается в параграфе 5, где мы вернёмся и к полученному уравнению.

Глава 5. Решение уравнений в целых числах.

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

5.1. Линейное уравнение с одним неизвестным

ax = b                                 (1)

где a, b – целые числа, a ≠ 0, имеет единственное целое решение x = b ⁄ a, если a – делитель b, и не имеет целочисленных  решений   в   противном случае.

Пример 19. Квадратные керамические плитки были приготовлены, чтобы покрыть ими пол в комнате размерами 2n + 1 на n + 2 плиток (число  n натуральное). Затем решили использовать эти плитки в комнате шириной n + 4 плитки. Возможно ли это, и какими могут быть размеры комнаты?

Решение. Если х – длина ряда плитки (натуральное число), то общее количество плиток равно x(n + 4)=(2n+1)(n+2) так что x =  при условии, что значение дроби равно целому числу. Найдём, при каких n это возможно. Разделим числитель дроби на знаменатель с остатком. Для этого раскроем скобки в числителе:   (2n + 1)(n + 2) = 2n2  + 5n +2  и заменим  n + 4 на е, так что n = t – 4, и подставим в выражение числителя: 2n2 + 5n + 2 = 2(t – 4)2 + 5(t – 4) + 2 = 2t2 – 16 t + 32 + 5t – 20 + 2 = 2t2 – 11t + 14

Заменим этим выражением числитель, разделим его на t = n + 4, затем вернёмся к n:

х =  = 2t – 11 +  = 2n – 3 + .

Число 2n – 3 целое при натуральном  n, поэтому x может быть целым, если 14 делится на n + 4, а это возможно в двух случаях: при n + 4 = 7, n = 3, тогда x = 6 – 3 + 2 = 5, и при n + 4 = 14, n = 10, тогда x = 20 – 3 + 1 = 18.

Ответ: 7 × 5 при n = 3 или 14 × 18 при n = 10.

Уравнения в целых числах с двумя или более неизвестными рассматривал в своём произведении « Арифметика» Диофант (III в. н.э.). В его честь неопределённые    целочисленные   уравнения    обычно   называют диофантовыми.

5.2. Линейное диофантово уравнение с двумя неизвестными:

ax + by = c,                     (2)

где a, b , c – данные целые числа, причём ab ≠ 0 (иначе это уравнение с одним неизвестным).

Пример 20. Показать, что любую сумму  (в рублях), кроме 1 и 3 рублей, можно заплатить монетами по 2 и 5 рублей, а если допустить сдачу (теми же монетами) – то вообще любую.

Решение. Пусть требуется заплатить n рублей х монетами по 2 рубля и у монетами по 5 рублей (х, у – целые числа, отрицательные значения х или у указывает, что получена сдача), тогда составим уравнение 2х + 5у = n.

Если (х; у) решение, то х = , n – 5y должно делиться на 2. Ввиду взаимной простоты 2 и 5, это  будет  выполнено,   если  у  одинаковой чётности с n. При n = 1 или 3 подойдёт у = -1, х = 3 или 4 соответственно (т.е. заплатить 3 или 4 монеты по 2 рубля и взять сдачу 5 рублей), при n = 2к достаточно у = 0, х = к. Если же n ≥ 5 нечётное число, можно взять

 у = 1, тогда получим  х ≥ 0.

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

Например, уравнение 2х – 4у = 21 не имеет решений, так как левая часть делится на 2, а правая не делится.

Теорема. Уравнение (2) тогда и только тогда имеет целочисленное решение (х; у), когда с делится на НОД ( a, b ).При этом множество его решений бесконечно.

Это условие выполнено, если a и b взаимно простые числа, как было в примере 22.

Зная одно (« частное») решение, можно найти все решения уравнения

ax + by = c c взаимно простыми a, b. Пусть (x, y) произвольное решение, а (х0. у0 ) частное решение. Вычтем почленно из равенства ax + by = c  равенство ax0  + by0  = c , получим a(x - x0) + b(y - y0) = 0, т.е.

X = x – x0, Y = y – y0 – решение соответствующего однородного уравнения aX + bY = 0   (3). Перенесём  bY в правую часть равенства (3): aX = - bY. Так как X, Y целые числа, то aX делится на b; по свойству 5 делимости, X делится на b в силу  взаимной простоты a, b, т.е. X = -bt для подходящего  целого  t, откуда Y = at. Итак, любое решение уравнения (2) находится по формуле

Пример 21. Найти все целочисленные решения уравнения 5х – 3у = 23.

Решение. Выразим, например, у через х : у =. Сразу видно, что при

 х = 4 получим у = - 1; мы нашли частное решение х0 = 4, у0 = - 1. Теперь запишем 5х – 3у = 5 * 4 – 3 (-1), 5 (х – 4 ) – 3( у +1) = 0. Нам остаётся решить однородное уравнение 5Х – 3Y = 0,  5X = 3Y, где X = x – 4, Y =y+1

Так как числа 5 и 3 взаимно простые, отсюда следует, что Х делится на 3 , а Y делится на 5, так что X = 3t,  Y = 5t,  t є Z.

Oкончательно    

Примечание. Тем самым мы нашли все х, удовлетворяющие требованию примера 18:  15х = 3 + 3dk =3 + 3*23* (-1 + 5t),  x = 23t.

5.3. Примеры решения нелинейных уравнений

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

Пример 22. Найти все целые корни уравнения х3 – 4х – 15 = 0.

Решение.  Перепишем  уравнение  в  виде  х3 – 4х = 15  и  левую  часть разложим на множители: х3 – 4х = х ( х2 – 4 ) = 15. Возможны варианты:

 х = 3, х2 – 4 = 5 или х – 2 =-5,  х =-3 , х + 2 = -1, но тогда произведение равно -15. Значит, других целых корней это уравнение не имеет.

Ответ: х = 3.

Пример 23. Найти все решения уравнения 4х2 – у2 = 28 в натуральных числах.

Решение. Разложим левую часть уравнения на множители:

( 2х – у )( 2х +у ) = 28. Так как х  и  у – натуральные числа, то 2х + у  и

2х – у  также натуральные  числа,  делящие  28.  Следует  рассмотреть всевозможные  разложения   28  на  два  натуральных  сомножителя:

 28 = 1* 28 = 2* 14 = 4*7 = 7*4 =  14*2 = 28*1 и поочерёдно приравнять 2х + у одному из них, а 2х – у  другому.  Однако  в  данном  случае,   вместо составления  шести  систем  уравнений,  мы  учтём  особенности  этих выражений. Если 2х + у нечётно, то 2х – у = ( 2х + у ) -2у также не делится на 2, и их произведение не может быть чётным. Следовательно, числа 2х – у  и  2х + у чётные,  причём 2х – у  ‹  2х + у.  В результате  остаётся  только одна система

которая имеет единственное решение х = 4, у = 6.

Замечание. Если бы искали все целые решения уравнения, пришлось бы рассмотреть также разложения ( -1 )*( - 28 ) = (-2 )* ( -14 ) и т.д.

Пример 24 .Решить в целых числах уравнение х2 – ху – 3у – 4 = 0.

   Решение. Левая часть не разлагается на множители ни с 3, ни  отдельно. Зато y входит в уравнение в первой степени. Выразим y через x: y(x+3)= x2- 4 = ( x2 – 9 ) + 5  ,   y = x – 3 + ( x -3). При целом  x  также y будет целым, если 5(x + 3), что возможно, если  x + 3  равно ± 1 или  ± 5. Получим 4 решения

5.4. Пифагоровы треугольники

     Это прямоугольные треугольники, длины сторон которых измеряются целым числом единиц.   Всем (даже  древним  египтянам)  был  известен треугольник со сторонами 3, 4 и 5, часто и называемый египетским. Вам наверняка  встречались и другие.

     Пусть x, y – катеты, а z    - гипотенуза такого треугольника, тогда, по теореме Пифагора, (x,  y,  z)- целочисленное решение уравнения

x2 + y2 = z2.                                       (v)

     Уравнение (V) имеет бесконечное множество решений, даже если не учитывать «неинтересные» тройки, получаемые из одной умножением  x,  y и  z на одно и то же число, как 62 + 82 =102, 6 = 2 * 3, 8 = 2 * 4, 10 = 2 * 5.

     Итак, пусть натуральные числа  x, y, z удовлетворяют уравнению (V). Если какое- либо два из них имеют общий делитель d , то на  d  будет  делиться  и третье из них, и равенство (V) можно сократить  на  d.   Поэтому   достаточно искать так называемые примитивные решения (они и будут «интересными»), где любые  два  из  x,  y,  z  взаимно  просты.  Можно  показать,  что  все примитивные тройки вычисляются по формулам x=2mn, y= n2 - m2, z=n2 + m2, где n, m – взаимно простые числа разной чётности, n › m.

     Произвольное решение имеет вид (tx0, ty0, tz0), где (x0, y0, z0) – примитивное решение, t – любое натуральное число.

    Таблица. 15 примитивных пифагоровых троек.

Рассматривая  таблицу,  можно  прийти  к  некоторым  закономерностям. Доказать   их  можно,  используя   явные  формулы  или  непосредственно равенство (V). Например, длина одного из катетов пифагорова треугольника делится на 4, т. к. х = 2mn, причём n или m чётно. Хотя бы одно из чисел кратно 3 или 5.

     Давно известно, что если числа a; b; c – пифагорейская тройка, т.е.

a2  +  b2 = c2,  аk; bk; ck – также пифагорейская тройка, в которой k – любое положительное число, т.е. (ак)2 + (вк)2 = (ск)2.

     Достаточно знать несколько пифагорейских троек в целых числах, чтобы написать бесчисленное множество их как в целых, так  и в дробных числах. Например, 3;      4;     5;          32 + 42  = 52

                   6;     8;      10;         (к = 2)

                   9      12      15          (к = 3)

                   8,1;   10,8;   13,5     (к = 2,7)

                   1;       1;     1      (к = )

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

Пример 25.

1.    3;     4;     5      →    32 + 42 = 52

а) 3;    4;     5      →    (3)2 + (4)2 = (5)2

б) 3;   4;    5

       ↓         ↓           ↓

     3;    4;     5

        ↓          ↓          ↓

      3,15     4,2       5,25      →   (3,15)2 + (4,2)2 = (5,25)2

2.     8;       15;        17       →     82 + 152 = 172

а)     8;  15;      17;

          ↓            ↓             ↓

         8;  15:      18   →    (8)2 + (15)2 = 182

б)      8;    15;      17           

            ↓           ↓             ↓

          9;       18;        20

            ↓           ↓              ↓

          9,6         18,        20,4     →     (9,6)2  + 182 = (20,4)2

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

     В итоге всё равно получим (ак)2 + (вк)2  = (ск)2, 

где к равен в примере 1 а) 1; б) 1; в примере 2 а) 1; б) 1,2.

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

Вывод в общем виде

Если a; b; c – пифагорейская тройка, то a;  b;  c - пифагорейская тройка.

     То есть должно выполняться равенство: (a)2 + (b)2  = (c)2.

     Проверим это. Запишем это равенство несколько иначе:

 (a + )2 + (b + )2 = (c + )2.

a2 + 2 *  +  + b2 + 2 *  +  = c2 + 2 *  +

a2(1 +  + ) + b2(1 +  + ) – c2(1 +  + ).

     Разделим обе части равенства на выражение 1 +  +  ≠ 0.

     Получим a2 + b2 = c2. Последнее равенство верно т.к. a, b, c – пифагорейская тройка по условию. Что и требовалось доказать.

     Примечание. Для геометрических задач должно быть q › 0. Но в принципе можно брать и q ‹ 0, но q ≠ - 1.

                                      Глава 6. Числа Фибоначчи

     В 1202 году Леонардо Фибоначчи (Леонардо Пизанский) в «Книге об абаке»  рассмотрел   последовательность  1,  1,  2,  3,  5,  8,  13, …  В  этой последовательности первые два числа равны 1, а каждый последующий член (начиная с третьего) равен  сумме  двух  предыдущих.  Последовательность чисел такого вида называют последовательностью Фибоначчи, а сами числа числами Фибоначчи. Формулами это можно записать так:  φ1 = φ2 = 1,

 φn+2 = φn+1 + φn. Пользуясь ими, можно посчитать сколько угодно много первых членов последовательности:

 Эти  числа  возникают  в  самых  разных  математических  ситуациях – комбинаторных, числовых, геометрических. Если вы любите отыскивать числовые  закономерности  в  живой  природе,  то  заметите,  что  числа Фибоначчи встречаются и там. Черенки листьев примыкают к стеблю по спирали, которая проходит между двумя соседними листьями: 1/3 полного оборота у орешника, 2/5 – у дуба, 3/8 – у тополя и груши, 5/13 – у ивы. Чешуйки на  еловой  шишке,  ячейки  на  ананас  и семена   подсолнечника расположены спиралями, причем количество спиралей каждого направления так же, как правило, числа Фибоначчи.

Интересно то, что числа Фибоначчи получили свое название после того, как в 1228 году Леонардо Фибоначчи сформулировал задачу:

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

Решение

    В данной задаче кролики размножаются по закономерности Фибоначчи. Решение задачи сводится к последовательности чисел Фибоначчи.

Введены обозначения:

В задаче спросили: Сколько пар кроликов родится в течение года? Кто может ответить на этот вопрос, не дорисовывая схему?

  Ответ: 144 пары кроликов

     Вот видите, если верить Фибоначчи (?!), какой доход в год получит семья,        разводящая   кроликов.   Итак,   решение   этой   задачи   сводится   к последовательности чисел Фибоначчи.

     Пример 26. Давайте выясним:  сколькими  способами   можно   разрезать полоску размером 2 × n на доминошки  (т.е. прямоугольники  размером

1 × 2)? При маленьких n можно всё нарисовать: обозначив искомое число через f (n), видим из рисунков 1 – 4, что

                 рис.1                                                    рис.2

                  рис.3

ƒ(1) = 1, ƒ(2) = 2, ƒ(3)=3, ƒ(4) = 5. Как найти следующее значение, т.е.ƒ(5)? Да очень просто: левая верхняя клетка покрыта либо вертикально (рис.5),  

                                      Рис. 5

   либо горизонтально  (рис. 6) расположенной доминошкой.                                                      

                                       Рис. 6

    Значит ,ƒ(5) вариантов  распадаются на ƒ(4) вариантов рисунка 5 и ƒ(3) вариантов рисунка 6, т.е.ƒ(5) = ƒ(4) + ƒ(3) = 5 + 3 = 8. Вообще при любом      n › 1 верна рекуррентная формула f(n + 1) = f(n) + f(n – 1).

 Поскольку f(1) = φ2  и f(2) = φ3 имеем f(n) = φn+1.

    Пример 27. Сколько существует n - значных чисел, составленных из цифр 2 и 5, в которых никакие две двойки не стоят рядом? Обозначим искомое количество способов через  g(n). Очевидно, g(1) = 2 и g(2) = 3 (годятся числа 25, 52 и 55). Легко выписать и трёхзначные числа: 252, 255, 525, 552 и 555. Значит, g(3) = 5. Впрочем, это значение находить даже и не обязательно. Важнее то, что любое интересующее нас (n + 1) – значное число начинается либо с двойки, либо с пятёрки. В первом случае после двойки должна идти пятёрка, после которой – любое из g(n – 1) чисел, во втором случае пятёрка никаких ограничений не создаёт, так что годится любой из g(n) вариантов.

Мы получили рекуррентную формулу g(n + 1) = g(n – 1) + g(n), совпадающую с формулой Фибоначчи. Поскольку g(1) = φ3, g(2) = φ4, имеем                                                              g(n) = φn+2.

Опять последовательность Фибоначчи!

     Пример 28. Между числами Фибоначчи есть и другие любопытные соотношения:

     φ1 + φ2 + φ3 + … + φn = φn+2 – 1,  

     φ1 + φ3 + φ5 + … + φ2n-1 = φ2n, 

     φ2 + φ4 + φ6 + …φ2n = φ2n+1 – 1,

     φn+1φn-1 – φn2  = ( -1 )n,  

которые можно доказать методом математической индукции. Последнее соотношение открыл в 1680 году французский астроном Жан Доминик Кассини. При n = 6 оно превращается в числовое равенство  13*5-82 = 1,  которое лежит в основе геометрического парадокса: на рисунке 7 шахматная доска разрезана на четыре части,

                           Рис.7

 из которых на рисунке 8 сложен прямоугольник размером 5 × 13.

                              Рис.8

(Аналогичная конструкция при любом  n разбивает квадрат со стороной  φn на четыре части, из которых получается прямоугольник размером φn-1 × φn+1. Одна клетка либо теряется, либо возникает лишняя – в зависимости от чётности n.) Разгадка парадокса проста: на рисунке 9 линии, соединяющие левый верхний угол с нижним правым углом, на самом деле образуют не отрезок, а незаметный для глаза параллелограмм.

     Много интересного в арифметике чисел Фибоначчи. Каждое третье число Фибоначчи чётно; каждое четвёртое кратно 3; каждое пятнадцатое оканчивается нулём; два соседних числа Фибоначчи взаимно просты; φn кратно φm в том и только в том случае, когда  n кратно m;  наибольший общий делитель чисел  φn и  φm – число Фибоначчи с номером НОД ( m, n ) (например, НОД ( φ12,φ18 ) =  НОД ( 144, 2584 ) = 8 = φ 6 ). 

     Для доказательства последнего факта полезно тождество φm+n = φmφn-1 + φm+ 1φn , которое можно доказать по индукции. Но мы разберём более интересное доказательство – выясним комбинаторный смысл этого тождества. Рассмотрим для этого полоску из k  клеток и  задумаемся, сколько существует способов пройти из левой клетки полоски в правую клетку этой полоски, если каждым ходом разрешается переходить в соседнюю справа клетку или  перепрыгивать через одну клетку. Очевидно, при  k = 1 идти некуда, да и не нужно; при  k = 2 нужно сделать ровно один шаг. Значит, при  k = 1 или 2 число способов равно 1. Для рассматриваемого числа способов выполнена в точности  такая же рекуррентная формула, что и для чисел Фибоначчи. В самом деле, если первый шаг – сдвиг на 1 клетку, то остаётся полоска из k – 1 клетки, если же первый шаг – сдвиг на 2 клетки, то остаётся полоска из k – 2 клеток.

     Итак, число способов пройти полоску – это число Фибоначчи. Осталось заметить, что все φm+n  cпособов можно разбить на два типа: можно остановиться на (m + 1 ) –й клетке ( таких способов φm+ 1φn ), а можно её перепрыгнуть ( таких способов φmφn-1 ).

     В 1728 году Даниэль Бернулли опубликовал формулу

φn = ( )n - ( )n ,    но о ней позабыли до 1843 года, когда она была вновь открыта французом Жаком Бине.

Из этой формулы следует, в частности, что φn растёт примерно как геометрическая прогрессия со знаменателем r = ( 1+ )/2, точнее, φn равно ближайшему к rn / целому числу.

     Пример 29. Последовательность чисел Фибоначчи задаётся рекуррентно:     х1 = х2  = 1; хи+1 + хn, n = 1, 2 3, … . Найдите формулу общего члена.

     Решение. Будем искать решение в виде xn = qn. Имеем qn+2 = qn+1 + qn 

    qn * q2 = qn * q + qn  q2 = q + 1  q2 – q – 1 = 0

                                              D = b2 – 4ac = 1 – 4(-1) = 5

                                              q1 = , q2 =

Тогда хn = c()n + d()n.

 Найдём c, d, исходя из данных х1, х2:

                                                       Ответ:

Заключение

  Подводя итог проделанной работе, отметим следующее.

   Разумеется, работа не может претендовать на полноту и завершённость, поскольку затронутая проблема достаточно глубинна и объёмна. Однако работа может быть использована как  справочник при подготовке к олимпиадам и  вступительным экзаменам.        

Используемая литература

1. Алгебра – 8/ под ред. Виленкина Н. Я. – М.: Просвещение, 2012.
2. Виленкин Н. Я., Шибасов Л. П., Шибасова З. Ф.. За страницами учебника математики, 10 – 11 – М.: Просвещение, 1996.
3. Гельфман Э. Г., Бек Е. Ф. и др. Дело о делимости – Томск, 1992.
4. Колосов В. А. Теоремы и задачи алгебры, теории чисел и комбинаторики. – М.: Гелиос АРВ, 2001.
5. Махмутов М.И. Проблемное обучение. – М.: Педагогика, 1975.
6. Нестеренко Ю.В. Простые и составные числа (в сб. «Факультативный курс по математике 7 – 9», сост. Никольская И. Л.). – М.: Просвещение, 1991.
7. Пойа Д. Математическое открытие. – М.: Наука, 1976.
8. Школа в «Кванте»: Арифметика и алгебра/ под ред. Егорова А. А. – М.: Бюро «Квантум», 2003 (прил. к журналу «Квант».).