10042

Функция Эйлера. Доказательство теорем Эйлера и Ферма

Доклад

Информатика, кибернетика и программирование

Пусть m>1 целое число и а вычет по модулю m. Порядок является наименьшим положительным числом для которого выполняется сравнение. Порядок числа по модулю обозначается. Функция Эйлера. Порядки чисел по модулю различны. Существуют числа являюще

Русский

2013-03-20

54.5 KB

23 чел.

Пусть m>1 – целое число и  а – вычет по модулю m.

Порядок является наименьшим положительным числом, для которого выполняется сравнение .

Порядок числа по модулю обозначается .

Функция Эйлера.

Порядки чисел по модулю различны. Существуют числа, являющееся порядком одновременно для всех чисел, взаимно простых с . Одно  из них равно значению т.н. функции Эйлера , определяемой как количество чисел в последовательности , взаимно простых с . Из определения функции Ейлера следует, что для простого числа  р  .

Функция Эйлера является мультипликативной: если  , то и .

Пусть , тогда .

Число называется первообразным корнем (первообразным элементом) по модулю , если его порядок по модулю равен .

Если  m – простое, , то первообразные корни всегда существуют.

Доказательство теорем Эйлера и Ферма.

Теорема Эйлера. Если   , то .

Доказательство теоремы Эйлера.

Пусть все различные числа, взаимно простые с , не превосходящие . Очевидно, .

Поскольку, , в последовательности любые два члена с разными индексами несравнимы по модулю .

Поэтому после приведения по модулю m последовательности и совпадают, с точностью до перестановки.

Следовательно, произведение всех членов одной последовательности сравнимо с произведением всех членов другой последовательности, откуда, после сокращения на , получаем .

Очевидно, из теоремы Эйлера следует малая теорема Ферма: , где - простое, .

Обобщение малой теоремы Ферма: пусть - конечное поле из q элементов. Тогда для всех , , выполняется соотношение  .


 

А также другие работы, которые могут Вас заинтересовать

4502. Команды передачи управления на языке ассемблера 45.32 KB
  Команды передачи управления на языке ассемблера На предыдущих уроках мы познакомились с некоторыми командами, из которых формируются линейные участки программы. Каждая из них в общем случае выполняет некоторые действия по преобразованию или пересылк...
4503. Цепочечные команды в языке ассемблер 63.95 KB
  Цепочечные команды в языке ассемблер Эти команды также называют командами обработки строк символов. Названия почти синонимичны. Отличие в том, что под строкой символов здесь понимается последовательность байт, а цепочка — это более общее назван...
4504. Путеводитель по философии: версия Секацкого 401 KB
  Путеводитель по философии: версия Секацкого. 1. Отправляясь в путь. Путеводители предназначены для заезжих и праздных гостей, для посетителей. Сегодня, по большей части, - для туристов, в связи с чем идея путеводителя оказалась столь же дискредитиро...
4505. Бертран Рассел о философии (из книги История западной философии Рассел Б.) 33.5 KB
  Бертран Рассел о философии (из книги История западной философии Рассел Б.) Концепции жизни и мира, которые мы называем философскими, являются продуктом двух факторов: один из них представляет собой унаследованные религиозные и этические концепции,...
4506. Введение в философию 191.5 KB
  Введение в философию Предназначенные как читателю, так и самому себе Иногда говорят, что философия – не школьная наука. Ее - де может постичь только человек, умудренный жизненным опытом и долгими размышлениями. Конечно, ни то, ни другое не помеша...
4508. Разработка Windows-программ. Знакомство с Delphi 75.13 KB
  Разработка Windows-программ. Знакомство с Delphi Основой системы разработки является VCL. Визуальный конструктор форм позволяет брать компоненты-заготовки из палитры компонентов, размещать на форму, изменять свойства, добавлять методы обработки собы...
4509. Проектирование смесительных производств 2.79 MB
  Введение Технология строительных материалов, изделий и конструкций включает стадию приготовления многообразных видов формовочных смесей. В частности, технология бетона и железобетона предусматривает возможности изготовления тяжелого, легкого...
4510. Сертификация и надежность программного обеспечения 239.94 KB
  Проблемы надежности ПО Оценка надежности ПО. Определение факторов, влияющих на достижение заданной надежности. Совершенствование методов повышения надежности в процессе проектирования и в процессе эксплуатации разработанного ПО. Направления исследов...