Обсуждение участника:MetaMockery — различия между версиями
(→Функции \sigma(n), \tau(n) и \varphi(n), их мультипликативность и значения) |
(→Малая теорема Ферма и теорема Эйлера) |
||
Строка 81: | Строка 81: | ||
Число <math>\overline{x}</math> называется вычетом по модулю <math>n</math>, если <math>\overline{x} \equiv x \ (mod \ n)</math>. Вычет <math>\overline{x}</math> называется обратимым вычетом, если существует вычет <math>\overline{y}</math>, такой что <math>\overline{x}\overline{y} \equiv 1 \ (mod \ n)</math>. Заметим, что вычет <math>\overline{x}</math> обратим тогда и только тогда, когда <math>\overline{x}</math> и <math>n</math> взаимно просты. Это обосновывается тем, что данное выражение можно представить в виде [https://e-maxx.ru/algo/diofant_2_equation линейного диофантово уравнения второго порядка] <math>\overline{x}\cdot\overline{y} + m \cdot n = 1</math>. Как видно из статьи, решение существует только при <math>(\overline{x}, n) = 1</math>. В таком случае, у числа <math>n</math> существует всего <math>\varphi(n)</math> обратимых вычетов. Пусть <math>\mathbb{Z}_{n}^{*}</math> {{---}} множество всех обратимых вычетов по модулю <math>n</math>. | Число <math>\overline{x}</math> называется вычетом по модулю <math>n</math>, если <math>\overline{x} \equiv x \ (mod \ n)</math>. Вычет <math>\overline{x}</math> называется обратимым вычетом, если существует вычет <math>\overline{y}</math>, такой что <math>\overline{x}\overline{y} \equiv 1 \ (mod \ n)</math>. Заметим, что вычет <math>\overline{x}</math> обратим тогда и только тогда, когда <math>\overline{x}</math> и <math>n</math> взаимно просты. Это обосновывается тем, что данное выражение можно представить в виде [https://e-maxx.ru/algo/diofant_2_equation линейного диофантово уравнения второго порядка] <math>\overline{x}\cdot\overline{y} + m \cdot n = 1</math>. Как видно из статьи, решение существует только при <math>(\overline{x}, n) = 1</math>. В таком случае, у числа <math>n</math> существует всего <math>\varphi(n)</math> обратимых вычетов. Пусть <math>\mathbb{Z}_{n}^{*}</math> {{---}} множество всех обратимых вычетов по модулю <math>n</math>. | ||
− | Достаточно доказать данную теорему только для вычетов, так как мы знаем, что если остаток числа <math>a</math> по модулю <math>n</math> взаимно прост с <math>n</math>, то и само число взаимно просто с <math>n</math>. | + | Достаточно доказать данную теорему только для вычетов, так как мы знаем, что если остаток числа <math>a</math> по модулю <math>n</math> взаимно прост с <math>n</math>, то и само число взаимно просто с <math>n</math>. Напомним, что данный факт был ранее доказан в доказательстве мультипликативности функции Эйлера. |
Рассмотрим вычеты по модулю <math>n</math>. Так как <math>n</math> и <math>a</math> взаимно просты, то вычет <math>\overline{a}</math> обратим. Пусть <math>\overline{b_1}, \overline{b_2}, \dots , \overline{b_{\varphi(n)}}</math> {{---}} все обратимые вычеты по модулю <math>n</math>. Тогда вычет <math>\overline{b} = \overline{b_1}\overline{b_2}\dots\overline{b_{\varphi(n)}}</math>, равный произведению всех обратимых вычетов, тоже обратим. Заметим, что отображение <math>\mathbb{Z}_{n}^{*} \to \mathbb{Z}_{n}^{*}</math>, заданное формулой <math>\overline{x} \mapsto \overline{a}\cdot\overline{x}</math> является биекцией. Действительно, мы просто умножаем каждый остаток на какую-то константу, от этого множество вычетов не изменится. В таком случае в выражении <math> \overline{a}^{\varphi(n)}\overline{b} = (\overline{a} \overline{b_1}) \dots (\overline{a} \overline{b_{\varphi(n)}}) </math>, в правой части стоит произведение всех обратимых вычетов, но взятое в другом порядке. Тогда <math>\overline{a}^{\varphi(n)}\overline{b} = \overline{b}</math>. Умножая обе части на вычет, обратный к <math>\overline{b}</math>, получим, что <math>\overline{a}^{\varphi(n)} \equiv 1 \ (mod \ n) </math>, что и требовалось доказать. | Рассмотрим вычеты по модулю <math>n</math>. Так как <math>n</math> и <math>a</math> взаимно просты, то вычет <math>\overline{a}</math> обратим. Пусть <math>\overline{b_1}, \overline{b_2}, \dots , \overline{b_{\varphi(n)}}</math> {{---}} все обратимые вычеты по модулю <math>n</math>. Тогда вычет <math>\overline{b} = \overline{b_1}\overline{b_2}\dots\overline{b_{\varphi(n)}}</math>, равный произведению всех обратимых вычетов, тоже обратим. Заметим, что отображение <math>\mathbb{Z}_{n}^{*} \to \mathbb{Z}_{n}^{*}</math>, заданное формулой <math>\overline{x} \mapsto \overline{a}\cdot\overline{x}</math> является биекцией. Действительно, мы просто умножаем каждый остаток на какую-то константу, от этого множество вычетов не изменится. В таком случае в выражении <math> \overline{a}^{\varphi(n)}\overline{b} = (\overline{a} \overline{b_1}) \dots (\overline{a} \overline{b_{\varphi(n)}}) </math>, в правой части стоит произведение всех обратимых вычетов, но взятое в другом порядке. Тогда <math>\overline{a}^{\varphi(n)}\overline{b} = \overline{b}</math>. Умножая обе части на вычет, обратный к <math>\overline{b}</math>, получим, что <math>\overline{a}^{\varphi(n)} \equiv 1 \ (mod \ n) </math>, что и требовалось доказать. |
Версия 11:26, 29 декабря 2020
Содержание
Функция Эйлера
Определение: |
Функция Эйлера | определяется как количество натуральных чисел, не превосходящих и взаимно простых с .
Определение: |
Функция | называется мультипликативной, если для любых взаимно простых .
Теорема (Мультипликативность функции Эйлера): |
Для любых взаимно простых чисел
|
Доказательство: |
Запишем натуральных чисел, не превосходящих , в виде прямоугольной таблицы с столбцами и строками, располагая первые чисел в первой строке, вторые чисел во второй и т.д.Поскольку и взаимно просты, то целое взаимно просто с тогда и только тогда, когда оно взаимно просто как с , так и с . Итак, нужно доказать, что количество чисел в таблице, взаимно простых с и с равно .В данном доказательстве мы используем тот факт, что число Алгоритме Евклида. взаимно просто с натуральным тогда и только тогда, когда остаток деления на тоже взаимно прост с . Данный факт довольно очевиден и используется вТеперь приступим непосредственно к доказательству. Число находящееся в -ой строке и -ом столбце нашей таблицы можно представить в виде . Если это число взаимно просто с , то и остаток этого числа по модулю тоже взаимно прост с . Но тогда и все числа в данном столбце тоже взаимно просты с , так как весь столбец можно представить в виде арифметической прогрессии с разностью , а при добавлении остаток деления по модулю не меняется. Поэтому, числа взаимно простые с в таблице занимают ровно столбцов.Перед тем как продолжить доказательство, давайте рассмотрим небольшое утверждение. Пусть нам даны Воспользуемся данным утверждением, подставив разность арифметической прогресии последовательных членов арифметической прогрессии . Тогда, если , то остатки всех этих чисел по модулю разные, а значит образуют все множество остатков , причем каждый остаток получается ровно из одного из членов прогрессии. . Тогда в каждом из столбцов есть ровно чисел, взаимно простых с . Следовательно всего чисел, взаимно простых и с и с равно , что и требовалось доказать. |
Функции , и , их мультипликативность и значения
Каноническое разложение числа
, где — количество простых делителей числа , — -ый простой делитель, — максимальная степень вхождения этого простого делителя.Функция
Функция
определяется как сумма делителей натурального числа :Если
и взаимно просты, то каждый делитель произведения может быть единственным образом представлен в виде произведения делителей и делителей , и обратно, каждое такое произведение является делителем . Отсюда следует, что функция мультипликативна:Для простого числа
легко посчитать . При этом легко обобщается для некоторой степени :В силу мультипликативности функции:
Функция
Функция
определяется как число положительных делителей натурального числа :Если
и взаимно просты, то каждый делитель произведения может быть единственным образом представлен в виде произведения делителей и делителей , и обратно, каждое такое произведение является делителем . Отсюда следует, что функция мультипликативна:Для простого числа
легко посчитать . При этом легко обобщается для некоторой степени :В силу мультипликативности функции:
Функция
Для простого числа
легко посчитать . На некоторую степень формулу можно обобщить:Обосновывается следующим образом: Все не взаимно простые с
числа в диапазоне от 1 до , очевидно, кратны . Всего таких чисел .В силу мультипликативности функции:
Малая теорема Ферма и теорема Эйлера
Теорема (Теорема Эйлера): |
Если и — взаимно простые целые числа, то |
Доказательство: |
Число линейного диофантово уравнения второго порядка . Как видно из статьи, решение существует только при . В таком случае, у числа существует всего обратимых вычетов. Пусть — множество всех обратимых вычетов по модулю . называется вычетом по модулю , если . Вычет называется обратимым вычетом, если существует вычет , такой что . Заметим, что вычет обратим тогда и только тогда, когда и взаимно просты. Это обосновывается тем, что данное выражение можно представить в видеДостаточно доказать данную теорему только для вычетов, так как мы знаем, что если остаток числа Рассмотрим вычеты по модулю по модулю взаимно прост с , то и само число взаимно просто с . Напомним, что данный факт был ранее доказан в доказательстве мультипликативности функции Эйлера. . Так как и взаимно просты, то вычет обратим. Пусть — все обратимые вычеты по модулю . Тогда вычет , равный произведению всех обратимых вычетов, тоже обратим. Заметим, что отображение , заданное формулой является биекцией. Действительно, мы просто умножаем каждый остаток на какую-то константу, от этого множество вычетов не изменится. В таком случае в выражении , в правой части стоит произведение всех обратимых вычетов, но взятое в другом порядке. Тогда . Умножая обе части на вычет, обратный к , получим, что , что и требовалось доказать. |
Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будем.
Теорема (Малая теорема Ферма): |
Если целое число и простое число — взаимно просты, то |
Доказательство: |
Так как | — простое, то . Воспользуемся теоремой Эйлера, тогда , что и требовалось доказать.
Различные свойства функции Эйлера
Теорема: |
Если для каких-то натуральных чисел и верно, что , тогда верно и |
Доказательство: |
Воспользуемся формулой для .При этом, так как , то , а такжеЗначит , а значит , что и требовалось доказать. |
Теорема: |
Для любого натурального числа выполнено равенство |
Доказательство: |
Данную теорему можно доказать разложив по формуле , а можно более элегантно:Рассмотрим Заметим, что множество значений дробей . Каждую дробь представим в виде несократимой дроби . — это множество делителей числа . Так как дробь несократима, то и взаимно просты. Зная, что , легко понять, что всего дробей со знаменателем ровно . Так как, все дробей мы представили в несократимом виде, где знаменатель является делителем , то , так как всего дробей , что и требовалось доказать. |
Теорема (Обобщённая мультипликативность): |
Пусть и — любые два натуральных числа, а , тогда:
|
Доказательство: |
Пусть тогда причем в общем случае и Поэтому можно записать:Здесь первые делителей являются также делителями а последние делителей являются делителями Распишем:В силу мультипликативности функции Эйлера, а также с учётом формулы где — простое, получаем:В первой строке записано во второй — а третью можно представить, как Поэтому: |
Применение теоремы Эйлера в других задачах
Задача об ожерельях
Задача: |
Требуется посчитать количество ожерелий из | бусинок, каждая из которых может быть покрашена в один из цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).
В ходе решения задачи мы приходим к формуле
Мы можем улучшить эту формулу, если рассмотрим выражение
. Пусть , тогда числа и оба делятся на и больше не имеют общих делителей. Тогда . Таких натуральных и имеющих ровно .Пользуясь функцией Эйлера, мы можем привести формулу к более лаконичному виду
.Алгоритм
Основной идеей алгоритма является формула эффективные алгоритмы.
. Для решения задачи нам нужны только простые делители числа . Их можно найти с помощью алгоритма факторизации. Написанный ниже алгоритм использует факторизацию числа, работающую за , однако есть болееАсимптотика вычисления
.function phi (n): result = n i = 2 while (i*i <= n): if n % i == 0: while n % i == 0: n /= i result -= result / i i++ if (n > 1): result -= result/n return result