Теорема Эйлера

Содержание

  1. 1. Определение
  2. 2. Предложение
  3. 3. Доказательство
  4. 4. Определение
  5. 5. Лемма
  6. 6. Доказательство
  7. 7. Следствие
  8. 8. Теорема
  9. 9. Примечание
  10. 10. Доказательство

Благодаря плодотворному труду Эйлера существует большое количество теорем, известных под названием «теорема Эйлера». Примерами из них являются теорема Эйлера о смещении для смещения твердого тела с одной фиксированной точкой, теорема Эйлера о распределении расстояний со знаком на прямой, теорема Эйлера о сходствах степеней функции тотиента и теорема Эйлера о треугольнике (см. обычно называется формулой треугольника Эйлера , дающей расстояние между центром описанной окружности и центром вписанной треугольника.

Теорема Эйлера обобщает теорему Ферма на случай составного модуля.
Ключевым моментом доказательства теоремы Ферма было то, что, если p простое число, {1,2,…,p-1} они взаимно просты с p.

Это говорит о том, что в общем случае может быть полезно смотреть на числа, меньшие модуля n, которые взаимно просты с n. Это мотивирует следующее определение.

Определение

Функция Эйлера φ — это функция над положительными целыми числами, определяемая формулой

image.png

Например φ(24)=8 , потому что существует восемь положительных целых чисел меньше 24, которые взаимно просты с 24:

1,5,7,11,13,17,19,23

С другой стороны φ(11)=10, потому что все числа {1,…,10} взаимно просты с 11.

Вот график (n,φ(n)) для 1 ≤ n ≤ 5000:

image.png

Вы можете видеть, что функция немного скачет, но точки данных ограничены сверху линией y=x . Точка будет находиться почти на этой прямой всякий раз, когда n простое число, а поскольку простых чисел бесконечно много, рядом с ней всегда будут точки.

Позже я выведу формулу для вычислений φ(n) в терминах простой факторизации числа n.

Предложение

(a) Если p простое, φ(р)=p-1.
(b) Если p простое число и n≥1, то φ(pn)=pn - pn-1.
© φ(р) подсчитывает элементы, в {1,2,…,n-1} которых обратимы по модулю n.

Доказательство

(a) Если p простое, то все числа {1,2,…,p-1} взаимно просты с p. Следовательно, φ(р)=p - 1.

(b) Есть pn элементы в {1, 2 ,…, pn}. Элемент этого множества не взаимно прост с p тогда и только тогда, когда он делится на p. Элементы этого множества, которые делятся на p, равны
image.png

(Обратите внимание, что pn-1・p = pn это последний элемент набора.) Таким образом, существуют pn-1 элементы набора, которые делятся на p, т. е pn-1. элементы набора, которые не взаимно просты с p. Следовательно, существуют pn - pn-1 элементы множества, взаимно простые с p.

(Определение φ(pn) применяется к множеству {1, 2 ,…, pn-1}, в то время как я просто считал числа от 1 до pn. Но это не проблема, потому что я считал pn в множестве, но затем вычел его, так как оно не было взаимно простым с p.)

( c ) (a,n)=1 тогда и только тогда, когда ax=1(mod n) для некоторого x, поэтому a взаимно просто с n тогда и только тогда, когда a обратимо по модулю n. Теперь φ(n) количество элементов, в {1, 2 ,…, n-1} которых относительно просто n, φ(n) равно и количество элементов, в {1, 2 ,…, n-1} которых обратимы по модулю n.

Определение

Приведенная система вычетов по модулю n представляет собой набор чисел

image.png

так что:
а) Если ί ≠ j , то aί ≠ aj (mod n). То есть а различны по модулю n.
b) Для каждого i, (aί , n) = 1. То есть все a взаимно просты с n.
Таким образом, редуцированная система вычетов содержит ровно одного представителя для каждого числа, взаимно простого с n. Сравните это с полной системой вычетов по модулю n, которая содержит ровно одного представителя для каждого числа по модулю n.

В качестве примера {1,5,7,11} можно привести систему с уменьшенным остатком мод 12. Так же {-11,17,31,-1}.

С другой стороны {0,1,2,3,4,5,6,7,8,9,10,11}, это полный остаток системы мод 12.

Лемма

Пусть φ(n)=k , и пусть редуцированная система вычетов по модулю n.
(a) Для всех m {a1 + mn ,…, ak + mn }является редуцированной системой вычетов по модулю n.

(b) Если (m,n) = 1 , {ma1 ,…, mak }– редуцированная система вычетов по модулю n.

Доказательство

а) Это ясно, так как ai = ai + mn (mod n) для всех i.
(b) Поскольку (m,n) = 1 , я могу найти x такой, что mx = 1 (mod n). Так как (ai , n) = 1 , так что я могу найти bi такое, что aibi = 1 (mod n)

Тогда (xbi)(ami) = (mx)(aibi) =1 (mod n) , что доказывает, что ami оно обратимо по модулю n. Следовательно, (ami,n) = 1 __ ma взаимно просты с n.

Теперь если mai = amj (mod n) , то xmai = xmaj (mod n) или Поскольку a были разными по модулю n, это возможно только для i = j

Следовательно, ma также различны по модулю n.
Следовательно, {mai ,…, mak} является редуцированной системой вычетов по модулю n.

Следствие

Пусть φ(n)=k , и пусть {a1 ,…, ak} редуцированная система вычетов по модулю n. Предположим (s,n) = 1, и пусть t будет любым целым числом. Тогда приведенная система вычетов по модулю n выглядит следующим образом:

image.png

Вот несколько примеров таких результатов. {1,5} это система с уменьшенным остатком мод 6. Добавляя 12=6・2 к каждому числу, я получаю {13,17} еще один мод системы с уменьшенным остатком 6.

Поскольку {6,25} =1 , я могу умножить исходную систему на 25, чтобы получить {25,125} , еще одну систему с уменьшенным остатком.
Наконец, {25+12,125+12}={37,137} еще одна система с уменьшенным остатком мод 12.

Теорема

(Эйлер) Пусть n > 0 , (a,n) = 1. затем

image.png

Примечание

Если n простое, то , и теорема Эйлера говорит , что является теоремой Ферма.

Доказательство

Пусть φ(n)=k , и пусть {a1 ,…, ak} редуцированная система вычетов по модулю n. Я могу предположить, что ai лежат в диапазоне {1 ,…, n-1}.

Так как (a,n) = 1, {aa1 ,…, aak} – другая редуцированная система вычетов по модулю n. Поскольку это тот же набор чисел по модулю n, что и в исходной системе, две системы должны иметь один и тот же продукт по модулю n:

image.png

Теперь каждый из них обратим по модулю n, поэтому, умножая обе части на a1-1…ak-1, я получаю

image.png

Например φ(40)=16, и (9,40)=1. Следовательно, теорема Эйлера говорит, что 916=1 (mod 40).
Аналогично, 216=1 (mod 40).

Пример. Уменьшить 37103 (mod 40) до числа в диапазоне {0,1,…,39}.
Теорема Эйлера говорит, что 3716=1 (mod 40). Так

image.png

Пример. Решить 15x = 7 (mod 32).
Обратите внимание, что (15,32) = 1 и φ(32)=16. Следовательно, 1516 = 1 (mod 32). Умножьте уравнение на 1515:

image.png

В настоящее время

image.png

Итак, решение есть x = 9 (mod 32).

Не получается самостоятельно разобраться с темой? Заказать написание статьи по геометрии!

Комментарии

Нет комментариев
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Прямой эфир