10042

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

Доклад

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

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

Русский

2013-03-20

54.5 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

30323. Физико-химические основы технологических процессов 59.5 KB
  Физикохимические основы технологических процессов Этилбензол на нефтехимических предприятиях Украины и в ведущих капиталистических странах получают по каталитической реакции алкилирования бензола этиленом: С6Н6 С2Н4→С6Н5СН2СН3 2 Реакция алкилирования бензола этиленом можно классифицировать как: по зоне протекания химической реакции гетерогенная ; по использованию в ходе реакции катализатора...
30325. Роль А.С. Пушкина в развитии РЛЯ 46.5 KB
  Образование нац лит языка это процесс длит и постепенный.; б устранение препятствий в развитии языка в данном отношении много было сделано в течение XVIII в.: реформы Петра I; стилистическая система Ломоносова; создание “нового слога†Карамзиным; в закрепление языка в литературе. Главная историч заслуга Пушкина и состоит в том что им завершена закрепление рус народноразговорного языка в литре.
30326. Старославянизмы. Их роль в истории РЛЯ. Первое южно-славянское влияние. Стилистические функции старославянизмов 46 KB
  Именно в среде болгар старославянский литературный язык стал языком новой религии. Для распространения нового вероучения в широких народных массах христианские проповедники использовали церковные тексты написанные на близком для восточных славян старославянском языке на который христианские книги переводились с греческого еще в IX веке. Под пером русских книжников старославянский язык испытывает влияние древнерусского языка и выступает в новой ипостаси как церковнославянский язык. При князе Владимире церковнославянский язык получает статус...
30327. Проблема происхождения РЛЯ (концепции А.А. Шахматова и С.П. Обнорского, компромиссные теории) 52 KB
  Основная проблематика в изучении происхождения русского литературного языка три концепции происхождения русского языка: а концепция А. Основная проблематика в изучении начального этапа становления русского литературного языка: а концепция Б. Дискуссии о происхождении русского литературного языка начались еще в 18 веке и продолжаются почти беспрерывно до настоящего времени. языка с течением времени все более и более уступают место элементам русской народной речи что находит окончательное завершение к первым десятилетиям 19 в.
30329. Распределение имен по типам склонения в индоевропейском языке 85 KB
  Семантический признак основание для выделения типов склонения. По древнейшим суффиксам уже выделялось 5 типов склонения а долгое о и у краткие подтипы: согласные es en et er у долгое = ъв. Изменения древнейшей системы склонения начались с общеславянского языка.