10042

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

Доклад

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

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

Русский

2013-03-20

54.5 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

64308. ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЕКСПЛУАТАЦІЇ КОМПРЕСОРНИХ СТАНЦІЙ ШЛЯХОМ ВДОСКОНАЛЕННЯ КОНСТРУКТИВНИХ ЕЛЕМЕНТІВ ГАЗОПЕРЕКАЧУВАЛЬНИХ АГРЕГАТІВ 772.5 KB
  Безперебійне перекачування природного газу неможливе без ефективної і надійної роботи газоперекачувальних агрегатів ГПА. В Україні Алжирі Росії та інших країнах налічуються тисячі одиниць ГПА різного типу потужності і конструкцій.
64309. АВТОМАТИЗАЦІЯ ПРОЦЕСУ УПРАВЛІННЯ ВИДОБУВНИМИ КОМБАЙНАМИ НА ОСНОВІ МОДЕЛЮВАННЯ РОБОТИ ШНЕКА 229 KB
  Це призводить до того що видобувні комбайни на тонких шарах при автоматичному управлінні працюють із заштибовкою шнека. Таким чином наукова задача дисертаційної роботи полягає у створенні інтегральної моделі яка описує процеси формування навантаження на шнеку та...
64310. МОДЕЛЮВАННЯ ПРОЦЕСІВ САМООРГАНІЗАЦІЇ В СОЦІАЛЬНО-ЕКОНОМІЧНИХ СИСТЕМАХ 1.19 MB
  В економічній теорії відбувається перехід до нової парадигми розвитку, що ґрунтується на інформації; змінюються погляди на простір і час. В інформаційній економіці провідну роль відіграє людський фактор, а отже, змінюються вимоги до побудови нових відносин у суспільстві.
64311. МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ НЕІЗОТЕРМІЧНОГО ВОЛОГОПЕРЕНЕСЕННЯ І В’ЯЗКОПРУЖНОГО СТАНУ В ДЕРЕВИНІ У ПРОЦЕСІ СУШІННЯ 293.5 KB
  Процеси що відбуваються у деревині під час сушіння характеризуються взаємозвязаними анізотропними фізикомеханічними властивостями і істотно залежать від густини температури вологовмісту та реологічної поведінки деревини.
64312. ОБҐРУНТУВАННЯ ПАРАМЕТРІВ ПІДНІМАЛЬНО-ТРАНСПОРТУВАЛЬНОЇ МАШИНИ І РЕЖИМІВ ЇЇ ФУНКЦІОНУВАННЯ НА ЛІСОВИХ СКЛАДАХ З МАЛИМ ВАНТАЖООБІГОМ 9.11 MB
  Невідповідність між можливостями наявного устатковання лісових складів і обсягом робіт усувають шляхом його замінювання що є актуальним завданням вирішення якого дасть змогу підвищити ефективність роботи устатковання та впровадити комплексну механізацію лісоскладських робіт.
64313. Вплив пізнього модифікування та швидкості охолодження на структуру виливків з високоміцного чавуну 176 KB
  Проблема покращення структуроутворення тонкостінних виливків з високоміцного чавуну може бути вирішена підвищенням ефективності модифікування. Дослідження особливостей гідродинаміки і тепломасообміну процесів модифікування в проточних реакторах та розробка...
64314. СУХА БУДІВЕЛЬНА СУМІШ ДЛЯ ОТРИМАННЯ ТЕПЛОІЗОЛЯЦІЙНИХ МАТЕРІАЛІВ ЗНИЖЕНОЇ ПАРОПРОНИКНОСТІ 250.5 KB
  Для досягнення поставленої мети розв'язувалися наступні завдання дослідження: теоретично обґрунтувати зниження паропроникності теплоізоляційних матеріалів на основі спученого перліту цементного вяжучого і хімічних добавок...
64315. Підвищення експлуатаційних показників систем автоматичного регулювання напруги низьковольтних кіл електрорухомого складу 502 KB
  Основними елементами систем автоматичного регулювання напруги низьковольтних кіл електрорухомого складу який знаходиться в експлуатації є акумуляторна батарея генератор постійного струму та вузол керування генератором який впливає на струм збудження генератора.
64316. ВИЗНАЧЕННЯ НАДІЙНОСТІ БУДІВЕЛЬ ПІДВИЩЕНОГО РІВНЯ ВІДПОВІДАЛЬНОСТІ З УРАХУВАННЯМ ФАКТОРІВ РИЗИКУ 3.03 MB
  Зростання рівня аварійності будівель та споруд внаслідок дії різноманітних невизначених факторів які непередбачені нормами проектування або невраховані проектними рішеннями що проявляються в реальних умовах експлуатації обєкта актуалізує питання удосконалення...