10042

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

Доклад

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

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

Русский

2013-03-20

54.5 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

48261. Літературознавство як наука 224 KB
  Автор будьякого художнього твору завжди репрезентує певний культурний прошарок своєї доби спостерігаючи яку беручи участь в її житті він водночас представляє певний ідеологічний або політичний напрям. Щоб розібратися в задумі письменника в політичній спрямованості його твору чи творчості треба знати основні факти біографії митця його зв'язки з іншими людьми участь у політичному і громадському житті. Вужчим за науковим обсягом вважаються так звані допоміжні галузі літературознавства – бібліографія археологія текстологія методика...
48262. Уголовно-процессуальное право 108.76 KB
  Структурно уголовно-процессуальное право распадается на части; Общую и Особенную. Деление это носит двойственный характер. С одной стороны, оно отражает специфику структуры Уголовно-процессуального кодекса, что уже понятия уголовно-процессуального права. С другой стороны, такая дифференциация оправдана методологически.
48264. ПРЕДМЕТ І ЗАВДАННЯ ЕПІЗООТОЛОГІЇ 4.42 MB
  Епізоотологія наука яка вивчає об'єктивні закономірності процесів виникнення розвитку поширення і згасання інфекційних хвороб тварин та на основі пізнання загальних закономірностей а також сучасних даних суміжних наук розробляє раціональні заходи профілактики і ліквідації епізоотій. Назва науки Епізоотологія як вчення про заразні захворювання сільськогосподарських і диких тварин птахів риб бджіл складається з трьох грецьких слів: ері на zoon тварина і logos вчення. Тобто мова йде про значне ураження тварин...
48265. Редагування як вид професійної діяльності і складова редакційно-видавничого процесу 256 KB
  Редагування як вид професійної діяльності і складова редакційновидавничого процесу. План Предмет і завдання курсу Загальне редагування. Зміст поняття редагування.
48266. ЕКОНОМІЧНА ІНФОРМАЦІЯ І ЗАСОБИ ЇЇ ФОРМАЛІЗОВАНОГО ОПИСУ 186 KB
  ЕКОНОМІЧНА ІНФОРМАЦІЯ І ЗАСОБИ ЇЇ ФОРМАЛІЗОВАНОГО ОПИСУ Економiчна інформація ЕКІ – це послiдовнiсть повiдомлень економiчного змiсту що можуть бути введенi вiдображенi збереженi обробленi переданi та загалом використанi для прийняття управлiнських рiшень на рiвнi окремих установ чи структурних одиниць так i економiки в цiлому. Економiчна інформація ЕКІ один з найбiльш масових рiзновидiв iнформацiї що вiдображає процеси виробництва розподiлу обмiну i споживання матерiальних благ та послуг. Види ЕКІ Вiдповiдно до виконуваних...
48267. Бюджетний механізм, його призначення та структура, роль в регулюванні соціально-економічних процесів у державі 45 KB
  Бюджетний механізм його призначення та структура роль в регулюванні соціальноекономічних процесів у державі. Бюджетний механізм може бути охарактеризований як комплекс спеціально розроблених і законодавчо закріплених у державі форм і методів створення і використання фінансових ресурсів для регулювання економічних і соціальних процесів. В економічній літературі відсутня єдина думка щодо визначення поняття фінансовий механізм . У працях провідних західних учених фінансовий механізм не вивчається як окремий об'єкт але всебічно досліджуються...
48268. Використання природи як засобу виховання в історії російської педагогіки 69.5 KB
  Мукачево 2011 Тема: Використання природи як засобу виховання в історії російської педагогіки. Концепція національного виховання “Освітаâ€. Теорія національного виховання.
48269. АВТОМАТИЗАЦІЯ ТЕХНОЛОГІЧНИХ ПРОЦЕСІВ ТА ОБЄКТІВ В ЧОРНІЙ МЕТАЛУРГІЇ 15.25 MB
  Всі задачі контролю і регулювання вихідних параметрів процесів і об’єктів класифікуються таким чином: 1 Задача стабілізації параметрів. Структура: 2 Задача програмного регулювання програмна зміна параметрів. 3 Задача слідкуючого регулювання співвідношення паливоповітря. Розглянемо задачу регулювання співвідношення паливоповітря для одної зони методичної печі.