Институт космических и информационных
технологий
Кафедра прикладной математики
и компьютерной безопасности
РЕФЕРАТ
по дисциплине «История информатики
и математики»
на тему:
«Линейная алгебра. Возрождение
теории чисел.»
Выполнил:
Баталов Павел Александрович
студент группы КИ13-09Б
1 курса
(очное отделение)
Научный руководитель:
Курако Михаил Александрович
Красноярск 2014
История
С XVII века вместе с интересом к точным
наукам возрастает и интерес к теории
чисел. Особенно он возрастает после издания
Клодом-Гаспаром Баше де Мезириаком греческого
текста «Арифметики» Диофанта.
Во Франции образовалась группа ученых,
занимавшихся задачами теории чисел. В
неё входили такие ученые как: Пьер Ферма,
Марен Мерсенн, Пьер де Каркави, Бернар
Френикль де Бесси, Жак де Билли, отчасти
Рене Декарт и Блез Паскаль. Общались в
основном через переписку, в которую позже
были втянуты ученые Англии – Валлис,
Броункер и Голландии – Гюйгенс, Схоотен
Однако из всей этой плеяды ученых одному
только Пьеру Ферма удалось выделить те
основные, центральные проблемы всей классической
теории чисел. Ему же принадлежит открытие
метода для доказательства теоретико-числовых
предложений – метод бесконечного спуска.
Поэтому Ферма по праву может считаться
основоположником алгебраической теории
чисел.
Биографические заметки: Ферма
Пьер Ферма (рисунок 11.5) родился в Бомоне,
близ Тулузы, в 1601 году и умер в Кастре,
также близ Тулузы, в 1665 году. Подробности
его жизни неизвестны, как и его математики,
но, по-видимому, она была относительно
не богата событиями. Отец Ферма, Доминик,
был богатым торговцем и юристом, его мать,
Клер де Лонг, происходила из известной
семьи, и у них было два сына и две дочери.
Пьер ходил в школу в Бомоне, университетскую
учебу начал в Тулузе и закончил ее получением
степени по праву в Орлеане в 1631 году. Таким
образом, академические успехи Ферма были
далеки от головокружительных, и не обязательно
потому, что его также отвлекала математика.
Насколько нам известно, его самой ранней
математической работой была аналитическая
геометрия 1629 года и, по мнению Вейля A984),
его теория чисел созрела, когда Ферма
приближался к сорокалетнему возрасту.
По имеющимся свидетельствам, Ферма,
видимо, не подпадает под обычные клише
о математическом гении: он начал немолодым,
не работал со страстной напряженностью,
и, как правило, не желал публиковать свои
результаты (хотя он иногда похвалялся
ими). Верно, что немногие математики эпохи
Ферма действительно занимались математикой
ради заработка, но Ферма был чистейший
из любителей. Повидимому, математика
никогда не приводила к какому-либо перерыву
в его профессиональной жизни.
Действительно, после получения степени
по праву в 1631 году, он женился на дальней
родственнице со стороны матери, Луизе
де Лонг, получил большое приданное и принялся
за удобную юридическую карьеру. Его положение
дало ему право на обращение господин
де Ферма, отсюда имя Пьер де Ферма, под
которым он сейчас известен. У него и Луизы
было пятеро детей, старший из которых,
Клемен-Самуэль, издал математические
труды своего отца. Вероятно, самое драматическое,
и вселяющее ужас, переживание жизни Ферма
— его заболевание чумой во время эпидемии
1652 или 1653 года. Сначала сообщили, что он
умер, но он оказался среди немногих счастливчиков,
которые выжили. В течение 1660-х гг. у Ферма
было неважное здоровье. Встречу с Паскалем
в 1660 г. вынуждены были отменить, потому
что ни тот, ни другой не был достаточно
здоров для путешествия. В результате,
Ферма упустил свой единственный шанс
встретится с ведущим математиком. Он
никогда не ездил дальше Тулузы, и вся
его работа выполнена по переписке, главным
образом, с членами кружка Мерсенна в Парилее.
После 1662 года в его письмах прекратились
упоминания о научной работе, но он подписывал
юридические документы за три дня до своей
смерти. Он умер в Кастре, во время выездной
сессии суда, и был похоронен там. Однако
в 1675 году его останки были перенесены
в фамильный склеп Ферма в церкви Августинцев
в Тулузе.
Явный отказ Ферма поставить математику
во главе своей профессиональной деятельности
делает глубину и диапазон его математических
достижений тем более ошеломляющим. Мы
можем никогда не узнать достаточно о
Ферма, чтобы понять его математическую
мысль, но попытки, которые предпринимались
до сих пор, увеличивают надежды, что можно
сделать больше. Махони дает обзор всей
математики Ферма, но ему не удается отдать
должное теории чисел. У Вейля есть блестящий
анализ теории чисел Ферма, но другие стороны
математики Ферма, по-прежнему, не проанализированы
с достойным сравнения пониманием.
Простые числа.
Ферма обратил внимание на большую роль,
которую играют простые числа. По-видимому,
он начал искать критерии для определения
того, будет ли заданное число N простым
или составным. Так же Ферма искал выражения,
F(n), которые при любом целом значении n
давали бы только простые числа. Он считал,
что таким выражением будет
Действительно, при n=0, 1, 2, 3, 4, F(n) принимает
значения 3, 5, 17, 257, 65537, являющиеся простыми.
Однако Эйлер показал, что F(5)=4294967297 не
простое. Христиан Гольдбах и Леонард
Эйлер доказали, сто не существует целого
многочлена с целыми коэффициентами, все
значения которого при целых х были бы
простыми.
Простые числа вида
называются теперь простыми числами
Ферма. До сих пор не известно, существует
ли конечное число простых чисел Ферма
или их бесконечно много.
Числа Ферма и их история.
На сегодняшний день не известно, конечно
или бесконечно количество простых чисел
Ферма. Существуют сильные аргументы как
в пользу одной, так и другой гипотезы.
Чтобы доказать, что число Ферма не простое,
существует два принципиальных способа.
- Найти хотя бы один делитель.
- Воспользоваться детерминированным
тестом (Пепин, 1877).
Теорема. Число Fm простое тогда и только тогда,
когда 3(Fm - 1)/2 + 1 делится на Fm.
В отличие от чисел Мерсенна числа Ферма
растут невообразимо быстро. После Пьера
Ферма простых чисел, носящих его имя,
больше обнаружено не было. Но и найти
делитель такого числа - весьма нетривиальная
задача. Из-за большой редкости делителей
и сложности их обнаружения каждый человек,
нашедший новый делитель числа Ферма,
попадает в историю математики. За три
с половиной века поиска найдено немногим
более 200 делителей. На сегодняшний день
список их первооткрывателей включает
60 человек из разных стран мира.
Немецкий профессор Вилфрид Келлер (Wilfrid
Keller) ведет официальную статистику всех
известных делителей чисел Ферма. Существует
несколько способов обнаружения простого
делителя у числа Ферма. Самым простым,
распространенным и достаточно эффективным
способом является поиск по числам вида k•2n + 1 - тривиальное деление.
В 1855 году немецкий астроном Томас Клаусен
в письме к Гауссу сообщил о разложении
шестого числа Ферма F6=274177•67280421310721, но этот факт
более века оставался неизвестным: еще
три человека независимо позже приходили
к этому результату.
Уральский самоучка священник-математик
Иван Михеевич Первушин прославился открытием
трех чисел. В заявлении, датированном
25 сентября 1870 года, Первушин сообщает,
что число Мерсенна 261 - 1 - простое. На тот момент это было самое
большое известное простое число, и его
стали называть «числом Первушина». А
в 1877-78 годах Первушин нашел делители для F12 и F23.
В 1903 году Вестерн (Western) за год титанической
работы нашел пять новых делителей для
различных чисел Ферма и сообщил, что у
любого числа Ферма не существует еще
неоткрытых делителей, меньших миллиона.
В докомпьютерную эпоху поиск этих чисел
выливался в долгие недели и месяцы кропотливых
вычислений. Один из самых внушительных
ручных результатов получил в 1905 году
Морхед (Morehead) - он нашел простое число
5•275 + 1, которое делит F73 (последнее число имеет 2843147923723958851728 знаков,
так что фактически записать его нет никакой
возможности). Всего же ручным способом
за три века было найдено лишь 16 делителей
для чисел Ферма.
Рафаэль Робинсон (Raphael Robinson) в начале
1950-х нашел 20 делителей на одном из первых
компьютеров SWAC. Это было одной из первых
демонстраций превосходства электронных
устройств над ручными вычислениями. Потомкам
Робинсон оставил код програмы, который
в несколько измененном виде использовался
десятилетиями. Предварительно Робинсон
опубликовал таблицу всех простых чисел
вида k•2n + 1 для n < 1000 и k < 500, а потом среди этих
простых чисел отыскал делители чисел
Ферма.
Самым плодовитым искателем делителей
для чисел Ферма является американский
разработчик компьютерных систем Гэри
Гостин (Gary Gostin), который на суперкомпьютерах
разных времен нашел уже 60 делителей. В
1993 году он приостановил свои вычисления.
Метод бесконечного спуска.
В математике, метод бесконечного спуска —
это метод доказательства от противного,
основанный на том, что множество натуральных
чисел вполне упорядочено.
Часто метод бесконечного спуска используется
для доказательства того, что у некоторого
уравнения нет решений по следующей схеме.
Из предположения, что решение существует,
вытекает существование другого решения,
которое в некотором смысле меньше. Тогда
можно построить бесконечную цепочку
решений, каждое из которых меньше предыдущего.
Это вызывает противоречие с тем, что в
любом подмножестве множества натуральных
чисел есть минимальный элемент, значит
предположение о существовании начального
решения неверно.
Пример
Допустим, что число √2 рационально. Геометрически
это означает, что диагональ квадрата
длины c соизмерима с его стороной длины
a, то есть найдутся отрезок длины d и целые
числа m и n такие, что c = dm, a = dn. Отметим
m–1 точек на диагонали AC и n–1 точек на
стороне DC, делящие эти отрезки на кусочки
длины d. Отложим на [AC] отрезок AK: |AK| = |AD|;
на [DC] — отрезок DE: |DE| = |KC|. Точки K и E попадут
в отмеченные точки (см. рис.). Докажем,
что треугольники ACD и KEC подобны. Угол C у них общий. Значит,
достаточно , проверить равенство |KC|=|EC|. |
Малая теорема Ферма.
Знаете ли вы об удивительном свойстве,
которым обладают числа, составленные
из одних девяток? Каково бы ни было простое
число р, отличное от 2 и 5, всегда можно
указать такое число, составленное из
одних девяток - 9999...99, - что оно будет делиться
на р. Так, на 3 делится 9, на 7 - число 999999,
на 11 - число 99, на 13 - опять-таки число 999999.
Чтобы получить число, делящееся на 17,
придется взять число из 16 девяток, на
19 - число из 18 девяток. И всегда можно быть
уверенным, что нужное число найдется,
хотя и может оказаться очень длинным.
На чем основано доказательство этого
факта? Дело в том, что при делении с остатком
на р может встретиться конечное число
различных остатков: 0, 1, 2…, р-1. Поэтому
найдутся два числа из девяток (пусть одно
- из l девяток, а другое - из m девяток, l>m),
такие, что оба они при делении на p дают
один и тот же остаток. Тогда число из l-m девяток
будет делиться на p. Заметим, что обсуждаемое
утверждение равносильно тому, что для
всякого простого p, не равного 2 и 5, существует
число вида 1000...00 (единица с нулями), дающее
при делении на простое число p остаток
1. Это очень важное утверждение. На нем
основана, например, периодичность бесконечной
десятичной дроби, полученной при обращении
обыкновенной дроби 1/p, где p не равно 2 и
5 (если выписывать последовательные десятичные
знаки при делении 1 на p, то с некоторого
места они начнут периодически повторяться).
Другая связь имеется с признаками делимости.
Признак делимости на 3 основывается на
том, что 9 делится на 3. Для того чтобы узнать,
делится ли на 11 число A=anan-1…a2a1, достаточно
разбить его на двузначные числа справа
налево: a2a1, a4a3… (последнее
число может оказаться однозначным), сложить
эти числа, и если полученная сумма делится
на 11, то на 11 делится и A, а если не делится,
то и A не будет делиться. Этот признак делимости
основывается на том, что 99 делится на
11. Аналогичный признак делимости с разбиением
на трехзначные числа имеется для 37. Такие
признаки делимости можно построить для
всех простых чисел p, не равных 2 и 5, но
они могут оказаться неудобными.
Естественно попытаться уточнить, сколько
же в точности девяток надо взять, чтобы
получилось число, делящееся на p. Оказывается,
что всегда годится число, состоящее из p-1 девяток.
Однако иногда достаточно и меньшего числа,
но всегда это наименьшее число девяток l является
делителем p-1. До сих пор не известен ответ
на вопрос, волновавший еще Гаусса: конечно
или бесконечно число таких p, для которых l=p-1 (так
обстоит дело для p=7, 17, 19, 23, 29…).
Утверждение о делимости чисел, составленных
из девяток, является частным случаем
значительно более общего утверждения,
носящего название малой теоремы Ферма:
если p - простое число, a - натуральное число,
не делящееся на p, то ap-1 при делении
на p дает остаток 1 (утверждение о девятках
получается при a=10). «Меня озарило ярким
светом», - писал Ферма, впервые сообщая
об этом своем открытии в письме (1640). В
самом деле, эта теорема стала одним из
самых фундаментальных фактов в теории
делимости натуральных чисел. Ферма не
оставил доказательства теоремы, и первое
известное доказательство принадлежит
Л. Эйлеру. В заключение дадим формулировку
этой теоремы, не содержащую ограничений
на число a: если p - простое число, a - натуральное
число, то ap -a делится
на p.