10042

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

Доклад

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

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

Русский

2013-03-20

54.5 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

76851. Артерии стопы 180.84 KB
  Дуга проецируется на уровне оснований плюсневых костей и заканчивается соединением с глубокой ветвью тыльной артерии стопы проходящей в первом межплюсневом промежутке. От дуги начинаются четыре плюсневые артерии . Прободающие артерии через межкостные промежутки соединяются с тыльными плюсневыми артериями.
76853. Плечеголовные вены 184.63 KB
  Обе плечеголовные вены: правая и левая (vv. brachiocephlicae dextra et sinistra) начинаются при слиянии подключичных и внутренних яремных вен правой и левой стороны на уровне и позади грудино-ключичных суставов, а заканчиваются образованием верхней полой вены на уровне прикрепления к грудине
76856. Вены головы 186.78 KB
  Кровь из вен головы поступает в яремные вены шеи и внутреннее позвоночное сплетение. Поверхностные вены головного мозга впадают в венозные синусы твердой мозговой оболочки. cerebri superiores имеющих восходящее направление: вены пре и постцентральной извилин предлобные лобные теменные и затылочные которые впадают в верхний сагиттальный синус.
76857. Вены верхней конечности 179.85 KB
  В области надплечья и плеча они вливаются в глубокие вены. Вторые проходят вместе с артериями собирая кровь от костей мышц суставов и вливаясь в подключичные вены. Вены верхней конечности клапанные начинаясь от пальцев они формируют на кисти тыльные венозные сети и ладонные дуги с перфорантными ветвями на предплечье и плече поверхностные и глубокие вены с анастомозами между ними.
76858. Вены нижней конечности 182.02 KB
  Прободающие вены соединяют между собой многочисленные глубокие и поверхностные вены расположенные в разных плоскостях и уровнях. В области лодыжек перфорантные вены не имеют прямых связей с подкожной сетью. Поверхностные вены вливаются в глубокие в разных отделах ноги в подколенной ямке и под паховой связкой.
76859. Принципы строения лимфатической системы 182.88 KB
  Лимфатические капилляры отсутствуют в тех органах и тканях где кровеносные капилляры не имеют базальной мембраны: в головном и спинном мозге и их оболочках глазном яблоке внутреннем ухе эпителии кожи и слизистых оболочек в пульпе селезенки хрящах костном мозге и плаценте. Начиная с выносящих лимфатические сосуды располагают полулунными клапанами в виде складок эндотелия придающих сосуду снаружи четкообразный вид. Лимфатические сосуды подразделяются на висцеральные органные и париетальные поверхностные и глубокие. Внеорганные...