Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Функция Эйлера. Теоремы Эйлера, Ферма и др.Содержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
Теорема. Пусть каноническое разложение натурального числа . Тогда .
Утверждение теоремы вытекает из приводимых ниже лемм 1, 2. Лемма 1. Пусть − простое число, . Тогда . Доказательство. Среди чисел , ,…, имеется в точности чисел, кратных . Остальные числа взаимно просты с и, следовательно, с . ∎ Лемма 2. Если нод (, , то . Доказательство. Для утверждение леммы очевидно. Пусть . Рассмотрим множество , , …, . Его можно представить как объединение попарно не пересекающихся подмножеств , , ,…, , , , …, . Удалим из подмножества , для которых нод , . В результате в останется подмножеств . Каждое из оставшихся подмножеств содержит только числа из , взаимно простые с . Далее, любое из подмножеств представляет собой полную систему вычетов по модулю . В каждом из них содержится в точности чисел, взаимно простых с . Эти числа оставим, а остальные удалим из . В результате в останутся те и только те числа из , которые взаимно просты как с числом , так и с числом , и, следовательно, с . Всего же во множестве , после всех удалений, останется чисел. С другой стороны, в исходном множестве содержится чисел, взаимно простых с . Значит, . ∎ Теорема Эйлера. нод , . Доказательство. Пусть , ,…, , где ,− числа, образуют приведённую систему вычетов по модулю . Тогда согласно теореме числа , ,…, также образуют приведённую систему вычетов по модулю . Поэтому всякое число сравнимо по модулю с некоторым числом , и обратно. Следовательно, имеет место система сравнений , , … , где , , …, − некоторая перестановка индексов , , …, . Перемножая левые и правые части этих сравнений, получаем Так как нод , , то левую и правую части последнего сравнения можно сократить на . В результате получим . ∎ Следствие (Малая теорема Ферма). Если − простое число и , то . Доказательство. Достаточно учесть, что , и применить теорему Эйлера.∎ Следствие. Если простое число, то для любых , . Доказательство. Если , то . Если , то последнее сравнение заведомо выполняется. Но тогда . ∎ Теорема Эйлера допускает следующее обобщение: Теорема Кармайкла. Для любых взаимно простых чисел , , где − функция Кармайкла, определяемая следующим образом: , ; , если ; , если − нечетное простое число; ,…, , если − каноническое разложение числа . Замечание. Для чисел вида 2, 4, или , где − простое число, , имеет место равенство Во всех остальных случаях − собственный делитель числа и для них соотношение (2) улучшает теорему Эйлера. Доказательство. См. Приложение. ∎ Следующее утверждение является обращением теоремы Ферма: Теорема Люка ( 1876 ). Натуральное число является простым тогда и только тогда, когда существует число такое, что , но для любого простого делителя числа . (Доказательство этой теоремы откладывается.) Из Малой теоремы Ферма следует, что если нод , и , то − заведомо составное число. Вместе с тем существуют составные числа. для которых . Такие (составные) числа называют псевдопростыми. Теорема Чиполлы . Существует бесконечно много -псевдопростых чисел. Доказательство. Положим , где − нечетное простое число, взаимно простое с , и отметим, что − целое составное число, так как , а − целые числа. Имеем где Допустим, что нод , . Тогда . Поскольку ), то 1) и . Если же нод , , то и | . В любом случае , и ∎ Пример. Для и получим и . Замечание. Число может быть -псевдопростым для некоторого , но не быть таковым при другом . Однако существуют составные числа, которые являются -псевдопро- стыми при любом , взаимно простым с . Такие числа называют числами Кармайкла, или абсолютно псевдопростыми. Известно , что множество чисел Кармайкла бесконечно. Первое такое число равно . Приведём одно утверждение, используемое в криптографии (в алгоритме ): Теорема. Пусть , − различные простые числа, , − любое число, взаимно простое с . Тогда отображение является взаимно однозначным на множестве , причем обратным к нему является отображение , где − число, удовлетворяющее сравнению . Доказательство. Достаточно показать, что , рассматривая случаи: 1) и ; 2) , т.е. для некоторого , взаимно простого с ; 3) (этот случай аналогичен предыдущему, поэтому не рассматривается). Отметим, что для некоторого . В первом случае имеем: , а во втором случае: (здесь некоторое целое). ∎ Китайская теорема об остат к ах. Число называется мультипликативным обратным к по модулю , если . Очевидно, что существует тогда и только тогда, когда нод , . В этом случае в качестве можно взять любое число, сравнимое с по модулю , что непосредственно вытекает из теоремы Эйлера. В интервале , содержится в точности одно такое (действительно, ; соответствующее обозначим через . Другой способ вычисления (без привлечения функции ) основан на использовании расширенного алгоритма Евклида, в котором наряду с вычислением нод , также вычисляются числа и такие, что . Китайская теорема об остат к ах. Пусть ,…, − любые попарно взаимно простые числа; , ,…, − любые числа; … . Тогда в интервале [ , содержится число , удовлетворяющее сравнениям (1) ,…, , причём единственное. Доказательство. Построим искомое . Положим = … … , = (число существует, поскольку нод , , ,…, . Далее полагаем . Нетрудно проверить, что число удовлетворяет системе сравнений , поскольку и при , . Если и удовлетворяет , то и удовлетворяет . Отсюда следует, что любое число , где , удовлетворяет . Одно из таких чисел попадает в интервал , . Допустим на минутку, что в этом интервале содержатся два числа: и , удовлетворяющие . Пусть, для определённости, . Поскольку число удовлетворяет системе сравнений , …, , То делится без остатка на ,…, , и, следовательно, на . Так как , то и . Значит, в указанном интервале содержится в точности одно число, удовлетворяющее системе сравнений . ∎
|
||||
Последнее изменение этой страницы: 2016-12-13; просмотров: 633; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.145.44.46 (0.007 с.) |