10042

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

Доклад

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

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

Русский

2013-03-20

54.5 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

26. Анализ общества с ограниченной ответственностью ООО Башкирский кирпич 80.32 KB
  К основной производственно-технической базе предприятия относятся цеха и участки в которых производится ремонт, техническое обслуживание и восстановление узлов и агрегатов подвижного состава предприятия. В ООО Башкирский кирпич имеются следующие цеха и участки:
27. Дослідження теоретичної та практиченої бази ТОВ Універсалпродукт 324.5 KB
  Характеристика організаційно-економічної діяльності ТОВ Універсалпродукт, загальна характеристика та напрямки діяльності. Оцінка маркетингової діяльності ТОВ Універсалпродукт, оцінка факторів макросередовища підприємства.
28. Философия сознания. Сознание как объект науки и высшая форма отражения 21.06 KB
  Сознание как объект науки и высшая форма отражения, определение сущности сознания. Психология, социология, кибернетика, логика и этология как связующие элементы изучения сознания. Эволюция разных форм биологического отражения, синтез материального и идеального.
29. Экономика городского строительства и хозяйства 98.4 KB
  Оценка экономической эффективности предприятий ЖКХ, анализ эффективности инвестиций в разработку и реализацию проекта. Действующая нормативная база: ГЭСНы, ФЕРы, ТЕРы, оценка экономической эффективности предприятий.
30. Основні поняття міжнародного ринку 154.5 KB
  Міжнародний ринок є найбільш затратним та найбільш привабливим для інвестування, головні показники щодо аналізу законодавчої бази країни, на ринок якої планується вихід. Практична значимість теорії життєвого циклу товару в міжнародного маркетингу.
31. Математические основы теории сетей 986.5 KB
  Операции удаления вершин или ребер графа могут изменить количество компонент связности. В связи с этим выделяются следующие вершины и ребра. Разбиение множества ребер графа на циклы, по своей сути, является важным специальным случаем следующей конструкции, устанавливающей тесную связь между графами и векторными пространствами над конечными полями.
32. Изучение основных технико-экономических показателей барабанного разгужателя 1.7 MB
  Разработка схем комплексной механизации и определение их технико-экономических параметров, описание устройства и принципа работы барабанного разгружателя. Механизация и комплексная автоматизация технологических участков и всего производственного процесса.
33. Схемотехническое проектирование фильтра и корректирующего устройства. АЧХ и ФЧХ функционального узла 1.99 MB
  Принципиальная схема, АЧХ и ФЧХ проектируемого фильтра, переходные процессы скорректированного фильтра и функционального узла, расчет электрических параметров, реализация фильтра на основании резисторов, конденсаторов и операционных усилителей.
34. Анализ финансового состояния изучаемого предприятия 1.47 MB
  Увеличение коэффициента оборачиваемости и уменьшение оборотного периода, изменение капитализированной прибыли. Объем уровня переменных затрат на единицу продукции, анализ динамики производства и реализации товара.