? — классическая теорема теории чисел, которая утверждает, что
Если p — простое число, и не делится на , то Другими словами, при делении нацело на даёт в остатке 1.
Равносильная формулировка:
Для любого простого и целого :
делится на
Теорема называется малой во избежание путаницы с Великой теоремой Ферма.
Доказательство
Докажем, что для любого простого p и целого неотрицательного a, делится на p. Доказываем индукцией по a.
База. Для a=0, и делится на p.
Переход. Пусть утверждение верно для a=k. Докажем его для a=k+1.
Но делится на p по предположению индукции. Что же касается остальных слагаемых, то . Для , числитель этой дроби делится на p, а знаменатель — взаимно прост с p, следовательно, делится на . Таким образом, вся сумма делится на p.
Для отрицательных a и нечётных p теорему легко доказать подстановкой b=-a. Для отрицательных a и p=2 истинность теоремы следует из ?
Свойства и некоторые следствия
Если — простое число, а и — такие положительные целые числа, что , тогда . Это утверждение используется в системе шифрования с открытым ключом RSA.
Если — простое число, отличное от 2 и 5, то число , запись которого состоит из одних девяток, делится на . Отсюда легко следует, что для любого целого числа , которое не делится на 2 и на 5, можно подобрать число, состоящее только из девяток, которое делится на [1]. Этот факт используется в теории признаков делимости и периодических дробей.
Обобщения
Малая теорема Ферма является частным случаем теоремы Эйлера, которая, в свою очередь, является частным случаем теорем Кармайкла и Лагранжа для конечных циклических групп.
Малая теорема Ферма также имеет изящное обобщение в теории конечных полей.
Псевдопростые числа
Основная статья: Псевдопростое число
Обращение малой теоремы Ферма неверно, то есть приведенные в определении формулы могут выполняться не только для простых чисел: если и — взаимно простые числа такие, что делится на p, то число может не быть простым. В случае, когда является составным, это число называется псевдопростым по основанию a.
Пример: Ф. Саррус в 1820 году нашёл, что число делится на 341 (потому что N делится на ). Но 341 — составное число: — это первое псевдопростое число по основанию 2.
Число p, являющееся псевдопростым по основанию a для всех a, взаимно простых с p, называется числом Кармайкла (например, 561 — наименьшее из чисел Кармайкла).
Хотя выполнение теоремы Ферма не гарантирует, что p — простое число, теорема может быть полезна для тестирования числа: если не делится на , то p — составное число.
История
Пьер Ферма сформулировал исходное утверждение теоремы около 1636 года. Письмо от 18 октября 1640 года Пьера Ферма к французскому математику Бернару Френиклю (Bernard Frénicle de Bessy) содержало следующее положение: p делит в случае, когда p является простым числом и a не делится на p. Опубликовано в посмертном издании его трудов (1660).
Ещё в древности китайским математикам была известна гипотеза (иногда называемая «Китайской гипотезой»), что p является простым числом в том и только в том случае, когда (фактически, частный случай малой теоремы Ферма)[2]. Тем не менее, обратное утверждение (о том, что из следует, что p простое), а, следовательно, и гипотеза в целом, оказались неверными (см. выше).
Существует также предположение, что китайская гипотеза была выдвинута примерно за 2000 лет до аналогичных работ Ферма. Стоит отметить, что гипотеза могла быть известна и другим математикам древности, даже несмотря на то, что она оказалась частично неверной. Тем не менее, в некоторых источниках[3] утверждается, что предположение относительно столь раннего появления гипотезы является распространённым заблуждением, а в действительности гипотеза была выдвинута лишь в 1872 году.
Сам Ферма оставил свою теорему без доказательства. Первым, кому удалось его найти, был Готфрид Вильгельм Лейбниц, в рукописях которого утверждается, что доказательство ему было известно до 1683 года. Лейбниц не знал о результате Ферма и открыл теорему независимо[1]. Но работа Лейбница не была опубликована, и доказательство (очень похожее) в 1736 году обнародовал Эйлер в статье Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio.
Доказательство малой теоремы Ферма, основанное на том, что целые числа сравнимы в некотором порядке с числами , было опубликовано в 1806 году Джеймсом Айвори.
Список литературы
Винберг Э. Б. Малая теорема Ферма и ее обобщения // Математическое просвещение. — 2008. — В. 12. — С. 43–53.
Гиндикин С. Г. Малая теорема Ферма // Квант. — 1972. — № 10.
Данциг, Т. Числа - язык науки. — М.: Техносфера, 2008. — С. 111. — ISBN 978-5-94836-172-7
Для подготовки данной работы были использованы материалы с сайта ru./
Другие работы по теме:
Теорема 15.2
Теорема 15.2. Если две точки прямой принадлежат плоскости, то вся прямая принадлежит этой плоскости. Доказательство . Пусть данная прямая и @ — данная плоскость. По аксиоме I существует точка
Простое доказательство великой теоремы Ферма
Представление великой теоремы Ферма как диофантового уравнения. Использование для ее доказательства метода замены переменных. Невозможность решения теоремы в целых положительных числах. Необходимые условия и значения чисел для решения, анализ уравнений.
Доказательство великой теоремы Ферма
Доказательство теоремы Ферма методами теоремы арифметики, элементарной алгебры с использованием методов решения параметрических уравнений для четных и нечетных показателей степени. Теорема о разложении на простые множители целых составных чисел.
Доказательство великой теоремы Ферма
Суть великой теоремы Ферма. Формирование диофантового уравнения. Доказательство вспомогательной теоремы (леммы). Особенности составления параметрического уравнения с параметрами. Решение великой теоремы Ферма в целых положительных (натуральных) числах.
Элементарное доказательство Великой теоремы Ферма
Идея предлагаемого вниманию читателя элементарного доказательства Великой теоремы Ферма исключительно проста: после разложения чисел a, b, c на пары слагаемых, затем группировки из них двух сумм U' и U''.
Теорема Ферма. Бесконечный спуск для нечетных показателей n
Получены другие формулы для решений уравнения Пифагора x^2+y^2=z^2, отличные от формул древних индусов, и делающие возможным доказательство для всех нечётных значений показателя n тем же способом бесконечного спуска Ферма, что и для n=4. Доказательство.
Доказательство теоремы Ферма для n=4
Формулирование и доказательство великой теоремы Ферма методами элементарной алгебры с использованием метода замены переменных для показателя степени n=4. Необходимые условия решения уравнения. Отсутствие решения теоремы в целых положительных числах.
Доказательство теоремы Ферма для n=3
Доказательство великой теоремы Ферма для n=3 методами элементарной алгебры с использованием метода решения параметрических уравнений. Диофантово уравнение, решение в целых числах, отсутствие решения в целых положительных числах при показателе степени n=3.
Доказательство Великой теоремы Ферма за одну операцию
Идея элементарного доказательства великой теоремы Ферма исключительно проста: разложение чисел a, b, c на пары слагаемых, группировка из них двух сумм U' и U'' и умножение равенства a^n + b^n – c^n = 0 на 11^n (т.е. на 11 в степени n, а чисел a, b, c на 1
Физическое доказательство малой теоремы Ферма
Простые числа играют важную роль в теории чисел. Используя свойства симметрии спиновых конфигураций Изинга, можно доказать малую теорему Ферма о простых числах и обобщить её на некоторые составные числа. Используемый в статье метод доказательства приводит к «физической» интерпретации простых чисел.
Доказательство теоремы Ферма для n 3
Доказательство великой теоремы Ферма для показателя степени n=3 Великая теорема Ферма формулируется следующим образом: диофантово уравнение: Аn+ Вn = Сn (1)
Теорема Ферма история и доказательства
ГОРОДСКОЙ КЛАССИЧЕСКИЙ ЛИЦЕЙ РЕФЕРАТ Великая теорема Ферма Подготовил: Петров А. А., 9Б класс (физ-мат) г. Кемерово - 1998 Содержание 1. Биография Ферма
Доказательство Великой теоремы Ферма за одну операцию
Идея предлагаемого вниманию читателя элементарного доказательства Великой теоремы Ферма исключительно проста: после разложения чисел a, b, c на пары слагаемых, затем группировки из них двух сумм U' и U'' и умножения равенства a^n + b^n – c^n = 0 на 11^n (т.е. на 11 в степени n, а чисел a, b, c на 11) (k+3)-я цифра в числе a^n + b^n – c^n (где k – число нулей на конце числа a + b – c)
Доказательство Великой теоремы Ферма для степени n 3
Файл: FERMA-n3-algo © Н. М. Козий, 2009 Украина, АС № 28607 ДОКАЗАТЕЛЬСТВО ВЕЛИКОЙ ТЕОРЕМЫ ФЕРМА ДЛЯ ПОКАЗАТЕЛЯ СТЕПЕНИ n=3 Великая теорема Ферма для показателя степени n=3 формулируется следующим образом: диофантово уравнение:
Доказательство Великой теоремы Ферма 6
Файл: FERMA-ЛАРЧИК © Н. М. Козий, 2009 Авторские права защищены свидетельством Украины 28607 Доказательство Великой теоремы Ферма Великая теорема Ферма формулируется следующим образом: диофантово уравнение:
Доказательство теоремы Ферма для n 4
Доказательство великой теоремы Ферма для показателя степени n=4 Великая теорема Ферма формулируется следующим образом: диофантово уравнение: Аn+ Вn = Сn (1)
Краткое доказательство великой теоремы Ферма
Теорема Ферма, ее формулировка и доказательство в случаях, если показатель степени n - нечетное число и если n - четное число. Теорема о единственности факторизации. Дополнительные обоснования теоремы. Состав наибольшего составного числового множителя.
О необычности путей развития математики
Теорема есть некое математическое утверждение, правильность которого требует построения логической цепочки доказательств, основанной на использовании законов формальной логики с привлечением аксиом – истин, принимаемых как само собой разумеющееся.
Трехмерность бытия и теоремы Ферма и Пифагора
Трехмерность бытия, Великая теорема Ферма и теорема Пифагора имеют логическую взаимосвязь. Эта взаимосвязь позволяет сформулировать еще один довод в пользу того, что существует только 3-мерный мир.
Великая теорема Ферма
История Великой теоремы Ферма весьма занимательна и поучительна, и не только для математиков. Пьер де Ферма внес вклад в развитие самых различных областей математики, однако основная часть его научного наследия была опубликована лишь посмертно.
Велика теорема Ферма
Короткий нарис життя, особистісного та творчого становлення відомого французького математика П'єра Ферма. Історія розробок та формування Великої теореми Ферма, її призначення та сфери використання. Доказ першої та другої леми, доведення для показника 4.
Теорема Ферма Бесконечный спуск для нечетных показателей n
Терема Ферма. Бесконечный спуск для нечётных показателей Получены другие формулы для решений уравнения Пифагора x^2+y^2=z^2, отличные от формул древних индусов, и делающие возможным доказательство для всех нечётных значений показателя n тем же способом бесконечного спуска Ферма, что и для n=4.
Великая теорема Ферма
Когда дьявол узнал об условии заключения договора с ученым-математиком о продажи его души, он рассмеялся и сказал: «Нет ничего проще. У меня есть доказательство этой теоремы, написанное самим Ферма».
Проверка больших чисел на простоту
Изучение основных подгрупп алгоритмов проверки простоты больших чисел: детерминированные и вероятностные проверки. Исследование методов генерации и проверки на простоту больших чисел с помощью метода Ферма (малая теорема Ферма), составление программы.