Благодаря плодотворному труду Эйлера существует большое количество теорем, известных под названием «теорема Эйлера». Примерами из них являются теорема Эйлера о смещении для смещения твердого тела с одной фиксированной точкой, теорема Эйлера о распределении расстояний со знаком на прямой, теорема Эйлера о сходствах степеней функции тотиента и теорема Эйлера о треугольнике (см. обычно называется формулой треугольника Эйлера , дающей расстояние между центром описанной окружности и центром вписанной треугольника.
Теорема Эйлера обобщает теорему Ферма на случай составного модуля.
Ключевым моментом доказательства теоремы Ферма было то, что, если p простое число, {1,2,…,p-1} они взаимно просты с p.
Это говорит о том, что в общем случае может быть полезно смотреть на числа, меньшие модуля n, которые взаимно просты с n. Это мотивирует следующее определение.
Определение
Функция Эйлера φ — это функция над положительными целыми числами, определяемая формулой
Например φ(24)=8 , потому что существует восемь положительных целых чисел меньше 24, которые взаимно просты с 24:
1,5,7,11,13,17,19,23
С другой стороны φ(11)=10, потому что все числа {1,…,10} взаимно просты с 11.
Вот график (n,φ(n)) для 1 ≤ n ≤ 5000:
Вы можете видеть, что функция немного скачет, но точки данных ограничены сверху линией 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, равны
(Обратите внимание, что 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 представляет собой набор чисел
так что:
а) Если ί ≠ 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 выглядит следующим образом:
Вот несколько примеров таких результатов. {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. затем
Примечание
Если n простое, то , и теорема Эйлера говорит , что является теоремой Ферма.
Доказательство
Пусть φ(n)=k , и пусть {a1 ,…, ak} редуцированная система вычетов по модулю n. Я могу предположить, что ai лежат в диапазоне {1 ,…, n-1}.
Так как (a,n) = 1, {aa1 ,…, aak} – другая редуцированная система вычетов по модулю n. Поскольку это тот же набор чисел по модулю n, что и в исходной системе, две системы должны иметь один и тот же продукт по модулю n:
Теперь каждый из них обратим по модулю n, поэтому, умножая обе части на a1-1…ak-1, я получаю
Например φ(40)=16, и (9,40)=1. Следовательно, теорема Эйлера говорит, что 916=1 (mod 40).
Аналогично, 216=1 (mod 40).
Пример. Уменьшить 37103 (mod 40) до числа в диапазоне {0,1,…,39}.
Теорема Эйлера говорит, что 3716=1 (mod 40). Так
Пример. Решить 15x = 7 (mod 32).
Обратите внимание, что (15,32) = 1 и φ(32)=16. Следовательно, 1516 = 1 (mod 32). Умножьте уравнение на 1515:
В настоящее время
Итак, решение есть x = 9 (mod 32).
Не получается самостоятельно разобраться с темой? Заказать написание статьи по геометрии!
Комментарии