10042

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

Доклад

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

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

Русский

2013-03-20

54.5 KB

23 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

12471. Інтерполяційні поліноми Лагранжа. Сплайн-інтерполяція 86.49 KB
  Лабораторна робота №5 Інтерполяційні поліноми Лагранжа. Сплайнінтерполяція. Мета роботи: познайомитися з методами інтерполяції складних функцій реалізувати заданий за варіантом метод інтерполяції у середовищі МatLAB. Завдання до виконання роботи: Доповнити сис...
12472. Чисельне інтегрування. Формули Ньютона-Котеса 508.05 KB
  Лабораторна робота №6 Чисельне інтегрування. Формули НьютонаКотеса. Мета роботи: познайомитися з методами чисельного інтегрування реалізувати заданий за варіантом метод інтегрування у середовищі МatLAB. Завдання до виконання роботи: Доповнити систему МatLAB файл
12473. Борьба за Ленинград 49 KB
  Борьба за Ленинград. В планах гитлеровского вермахта Ленинграду отводилось особое место. Ленинградское направление согласно плану Барбаросса являлось одним из трёх главных направлений на котором наряду с Московским и Киевским началось вторжение немецкофашис...
12474. Блокада Ленинграда 519.44 KB
  Реферат Блокада Ленинграда. ВВЕДЕНИЕ Самая страшная осада города в военной истории человечества длилась 871 день Враг снова вокруг Ленинграда Замкнул огневое кольцо. Узнали мы страшное слово блокада И смерти взглянули в лицо [1] Война грянула как г
12475. Блокада Ленинграда (8 сентября 1941 г. – 1 марта 1944 г.) 58.5 KB
  Реферат Блокада Ленинграда ОГЛАВЛЕНИЕ 1. Введение 2. Блокада Ленинграда 8 сентября 1941 г. 1 марта 1944 г. 3. Дорога жизни сентябрь 1941 г. март 1943 г 4. Борьба Ленинграда в кольце блокады 5. Факторы стойкости 6. Прорыв блокады и боевые действия советски
12476. Блокада Ленинграда 872 дня 834.11 KB
  Блокада Ленинграда. Цифры: 332 059 убитых 24 324 небоевых потерь 111 142 пропавших без вести Гражданские потери: 16 747 убито при артобстрелах и бомбардировках 632 253 погибли от голода Блокада Ленинграда длилась с 8
12478. Блокада Ленинграда самое громкоговорящее событие в истории Второй мировой войны 7.67 MB
  Блокада Ленинграда Предисловие Блокада Ленинграда самое громкоговорящее событие в истории Второй мировой войны. В этом страшном и роковом событии погибло около 800 тыс.человек гражданского населения 4 из которых погибло от бомбёжек а остальные 96 от голода. Офици
12479. 27 января – День снятия блокады г. Ленинграда (1944 г.) 1.45 MB
  27 января День снятия блокады г. Ленинграда 1944 г. На Невском надписи пестрели. Кричала каждая стена: Внимание При артобстреле Опасна эта сторона Огонь И смерть вставала к