10042

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

Доклад

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

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

Русский

2013-03-20

54.5 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

22045. Радиорелейные системы передачи. 175 KB
  облучатель в фокусе плоское зеркало парабола фидер облучающая парабола Радиооборудование ПРМ ПРД Радиооборудование Оборудование состоящее из передатчика приемника и антенны называют радиорелейной станцией РРС....
22046. Системы с ЧРК 1.71 MB
  Электрические сигналы при передаче от одного абонента к другому проходит через нелинейные преобразователи усилители промежуточные линейные – от понятия линии связи усилители усилители – регенераторы узловые АТС линии связи. А это в свою очередь приводит к стандартным длинам участков линии связи через которые необходимо ставить линейные усилители – регенераторы восстанавливающие сигнал и необходимое превышение его уровня над шумами. Затухание в линии связи всегда растёт с ростом частоты сигнала. Рекомендуется использовать линии...
22047. Структура многоканальной системы передачи с ЧРК 53 KB
  ГРУППОБРАЗОВАНИЕ уплотнение каналов в системе с ЧРК носит иерархический характер. На основе каналов ТЧ с рассмотренными выше характеристиками строятся следующие групповые каналы тракты: Наименование группы каналов Диапазон занимаемых частот кГц Число каналов ТЧ Число объединяемых групп Предварительная группа ПрГ Первичная группа ПГ Вторичная группа ВГ Третичная группа ТГ Четверичная группа ЧГ 1224 60108 312552 8122044 851612388 3 12 60 300 900 используется редко 4 ПрГ 5 ПГ 5 ВТ 3 ТГ Совокупность устройств...
22048. Одно и двухнаправленные системы передачи 222 KB
  Для компенсации потерь и коррекции фазочастотных искажений сигнала через определенные расстояния в линию включаются линейные усилители. Схемы включения дифференциальных трансформаторов Основное назначение РУ – обеспечить передачу сигнала в направлении клемм от 11 к 33 с малыми потерями и прием сигнала с клемм 44 к 11. Конечная величина затухания a43 приводит к тому что часть сигнала из передающей пары проводников переходит в приемные проводники действие на ближнем конце. Неполное согласование РУ на дальнем конце...
22049. Шумы в линии передачи. Расчёт длины усилительного участка. 100.5 KB
  Для такой ЭГЦ средняя за час псофометрическая мощность помехи WЭ10000 пВт или пВт 1 км для международных пВт.23LЭ и тогда Мощности различных видов шумов определяются по следующим формулам: Мощность собственных шумов тепловые шумы линии элементов схем флуктуации электропроводности дробовые шумы электронных приборов и т. Увеличивать длину l усилительного участка по сравнению с нормами МККТТ можно либо увеличивая мощность полезного сигнала – но не допуская увеличения нелинейных шумов уменьшая собственные шумы усилителей – новая...
22050. Формирование групповых сигналов в системах с ЧРК 173 KB
  Итого любой канал ТЧ в системе с ЧРК может иметь полосу f=4 кГц. Общая ширина должна быть F1= 12f=48 кГц это абсолютная ширина спектра первичной группы. Значит после преобразования НЧ спектра с полосой F1=48 кГц вверх по частоте нижняя граница нового спектра должна быть выше второй гармоники от 48 кГц.
22051. Барокко 43.5 KB
  Барокко К XVII в. широкого распространения достигли мотивы и настроения барокко утверждавшего что человек лишь странник на этой бренной жалкой земле. Это усиление лирического начала особенно заметно в поэзии барокко или в поэзии которая в той или иной степени соприкасалась с барокко. В немецких условиях именно литература барокко в течение длительного времени оказывала решающее воздействие на духовную жизнь страны.
22052. Пастораль, городской роман, шельмовской (плутовской) роман 49.5 KB
  Пастораль городской роман шельмовской плутовской роман Пастораль Пастораль франц. Жанровые формы Ппасторали многообразны: эклога поэма роман; после стихотворной драмы Сказание об Орфее Полициано 1480 развивается драматическая Пастораль принятая особенно в 16 17 вв. Систему поэтики немецкой романной пасторали XVII в. В немалой мере такому положению способствовала также устойчивая репутация пасторального романа как если не вторичной периферийной то все же некой побочной маргинальной ветви в системе немецкого романа XVII в.
22053. Пиетизм 30 KB
  Основателем Пиетизма является Ф. Становление и развитие Пиетизма таким образом детерминировано теми же факторами которые обусловили в свое время оформление протестантизма в целом и которые питают историческую эволюцию мистической традиции см. Основателями и лидерами пиетизма были Ф. Движение Пиетизма началось с молитвенных собраний в доме Шпенера.