Обсуждение:Функция Эйлера

↓

Пожалуйста, добавляйте новые темы снизу

Код на Дельфи

В том числе к ув. уч. AVB.

Delphi

program Euler1;

{$APPTYPE CONSOLE}

uses SysUtils;

function NOD (A,B: Word): Word; var X,Y: Word; begin X := A; Y := B; while (X <> Y) do begin if (X > Y) then Dec(X, Y) else Dec(Y, X); end; NOD := X; end;

var N: Word; I,A: Word;

begin WriteLn ('Input N: '); ReadLn (N); A := 0; for I := 1 to N-1 do if (NOD(I, N) = 1) then Inc (A); WriteLn ('The Euler Function of N is: ', A); ReadLn; end.

В чем энциколпедическая значимость данного фрагмента кода в данной статье? К теме статьи в нем относится только 3 (три!) строки. остальное - функция НОД (это одна из первых функций, которые пишут при изучении языков программирования) и шелуха, не несущая смысловой нагрузки (ввод-вывод, объявления переменных, delphi-специфичные параметры) -- этому тоже учат в самом начале). У нас, простите, энциклопедическая статья или учебник по программированию (плавно переходящий в склад решений школьных задач по информатике). Учебникам место на викиучебнике. Решения готовые для школьников -- это еще хуже.

IMHO не нужно приводить полный код программ, достаточно только показать основную функцию. И не нужно показывать ее в 5ти реализациях на паскале, или на куче языков. У нас здесь не сравнение языков и вариаций паскаля, а энциклопедия `a5b 20:15, 11 июля 2009 (UTC)

Да, про паскаль ошибся, это в другой статье было, там clrscr; использовался. Но, несмотря на известность Delphi, это мертвый продукт. `a5b 20:16, 11 июля 2009 (UTC)

И еще, что популярнее или известнее, delphi или python? Какие языки, по-вашему, ориентированы на математику? (Я бы отнес к ним: Fortran, C/C++.) `a5b 20:20, 11 июля 2009 (UTC)

Код на питоне

Не затирайте код целиком, если Вам в нем что-то не нравится, или покрайней мере приводите свою версию. — Эта реплика добавлена участником W-495 (о • в) 00:19, 20 июня 2009 (UTC)

• Я объясню, почему я (уже три раза) убрал пример на питоне: цель примеров - показать принципы реализации на самых используемых языках (а то вообще псевдокодом можно ограничиться), а не дать список всех возможных реализаций на всех возможных языках. А питон при этом не является языком, ориентированным на математику. Поэтому я считаю, что захламлять эту статью реализацией на питоне - не след. -- A^VB^talk 00:59, 20 июня 2009 (UTC)

  Если руководствоваться этой логикой, то пример на F# тоже стоит удалить. --Ashik ^talk 05:51, 20 июня 2009 (UTC)

• И ещё: я использовал откат, при котором нельзя дать описание правки-отката, потому что вы вставляете свой код в несколько правок, и чтобы не захламлять историю индивидуальными отменами или не формировать "отмена такая-то" вручную, я откатил ваши правки. -- A^VB^talk 01:01, 20 июня 2009 (UTC)

Про Python

• Немного захламлю тут.

Не согласен, питон является языком ориентированым на программиста, плохо комментированные примеры «на мертвых и плохо спроектированных» (при всем уважении к авторам) языках не дают понятия об алгоритме, хотя любое императивное описание будет аналогичным с приведенными. Можно попробовать написать на питоне в функциональном стиле. Про захламление не думал, теперь буду. w495 03:25, 20 июня 2009 (UTC)

Рецензия на 16 ноября 2012 года

Здесь находятся завершившиеся обсуждения. Просьба не вносить изменений.

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

Статья была значительно расширена и переработана. Объем и содержание позволяют ей претендовать на звание хорошей статьи. Материал брался из множества источников, поэтому где-то возможна неточность, хотя статья неоднократно подвергалась ревизии. Я буду признателен за любую критику, так как это моя первая статья. — Эта реплика добавлена участником Borisbelousov (о • в) 21:24, 16 ноября 2012 (UTC)

Замечания LGB

Статья в целом приятная, содержательная, но над стилем и оформлением надо ещё много работать. Несколько замечаний от первого чтения.

• Буква Ё подвергается явной дискриминации, что в Википедии не принято.
  • Исправлено Изменил, где это бросается в глаза, наподобие "чётное" и "нечётное". На будущее буду иметь в виду, спасибо. --Boris Belousov 19:20, 25 ноября 2012 (UTC)
• К чему в преамбуле перечислять свойства функции?
  • Сделано Убрал эту информацию. --Boris Belousov 19:20, 25 ноября 2012 (UTC)
• Почти все сноски ведут на малодоступные иностранные источники, и даже сноски на широко известную книгу Виноградова почему-то оформлены латинским шрифтом. Неужели в отечественной литературе совсем нет аналогов? Обобщённая мультипликативность вообще без источника, хотя её простое следствие: $~\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)$ зачем-то сноску имеет. Кстати, из приведенной формулы и из очевидного факта: $~\varphi (p)=p-1$, который лучше перенести выше, мгновенно следует, что $~\varphi (p^{n})=p^{n}-p^{n-1}$, но непонятно зачем в статье приводится отдельное доказательство.
  • Исправлено Я по привычке думал, что ref_id должен быть на латинице, поэтому сноски даже на русские источники были на английском. Я, к сожалению, не нашел отечественных книг, в которых так же подробно были бы описаны свойства функции Эйлера, как, например, это сделано в книге Hardy и Wright'а. На наиболее часто используемые источники есть ссылки в конце статьи, они в открытом доступе. Доказательство обобщенной мультипликативности опирается на свойство: $~\varphi (p^{n})=p^{n}-p^{n-1}$. К тому же последнее свойство используется для вычисления функции Эйлера и является важным само по себе. Поменял порядок расположения материала, чтобы было понятно, что откуда следует. --Boris Belousov 19:20, 25 ноября 2012 (UTC)
• Мне встречались с десяток доказательств мультипликативности функции, но такое туманное вижу впервые. Вряд ли один читатель из сотни поймёт, при чём тут биекция и почему её существование что-то доказывает.
  • Исправлено На мой вкус доказательство, опирающееся на китайскую теорему об остатках, одно из самых простых. Добавил другое доказательство, которое используют Сагалович и Hardy. Не сказал бы, что оно сильно проще. --Boris Belousov 19:20, 25 ноября 2012 (UTC)
• Таблицу значений функции я бы перенёс сразу после определения.
  • Сделано Расположил разделы в порядке: определение - вычисление - значения. --Boris Belousov 19:20, 25 ноября 2012 (UTC)
• Неэнциклопедический стиль: Функция Эйлера ведет себя очень интересно.
  • Исправлено Эх... Придется удивлять взбалмошности поведения функции Эйлера в одиночестве. --Boris Belousov 19:20, 25 ноября 2012 (UTC)
• В разделе «Нахождение порядка группы» первые 2 предложения утверждают одно и то же. Кроме того, оба утверждения относятся не только к мультипликативной группе кольца вычетов, а к числу порождающих элементов любой конечной циклической группе, о чём было бы очень полезно упомянуть.
  • Исправлено Спасибо за этот комментарий. Хотел об этом написать, но забыл. --Boris Belousov 19:20, 25 ноября 2012 (UTC)

Возможно, потом дополню, пока спасибо за труды. LGB 16:55, 20 ноября 2012 (UTC)

Продолжим.

• Общее замечание: поскольку представление о функции Эйлера вполне доступен школьнику, желательно (где это возможно) писать в расчёте на этот контингент читателей. Может быть, стоит распределить материал так: сначала то, что не требует от читателя высшего образования, а в конце статьи — дополнительные сведения повышенной трудности. Кроме того, читателю будет легче понять материал, если в начале раздела и перед сложными для понимания теоремами наглядно пояснить, о чём идёт речь. Пример: в разделе «Отношение последовательных значений» написать что-нибудь вроде: у функции встречаются как скачки вверх, так и скачки вниз неограниченного размаха.
  • Я так и старался писать, чтобы можно было разобраться, совсем не зная ни теорию чисел, ни модульную арифметику. Постараюсь еще разъяснить некоторые моменты.--Boris Belousov 11:57, 2 декабря 2012 (UTC)
    • Раздел «Приложения и примеры» в основном не требует специальных познаний, но перед ним стоит раздел «Асимптотика» для более продвинутых читателей. Может, перенести Приложения повыше, а «Асимптотику» и «Нерешённые вопросы» охватить последним разделом «Дополнительные вопросы»? Я ни в коем случае не настаиваю, но лучше дать читателю всю полезную информацию до того места, когда он перестаёт понимать текст. LGB 16:35, 2 декабря 2012 (UTC)
      • Я хотел попробовать переместить примеры ближе к началу статьи, но это получается не вполне органично, так как при этом свойства и асимптотики перемежаются примерами, а хотелось бы, все-таки, всю теоретическую информацию собрать в одном месте, а приложения - в другом. К тому же, статья довольно обзорная и является скорее собранием фактов, не предполагающим последовательного чтения раздел за разделом, поэтому, мне кажется разумным оставить примеры снизу, чтобы читатель, при желании мог к ним спуститься и, развернув все hider'ы, ознакомиться с возможностями применения функции.
• На заглавном рисунке ясно просматриваются 4 луча, вдоль которых конденсируются значения функции Эйлера. Верхний, очевидно, есть прямая y=x-1, было бы интересно узнать об остальных, если можно.
  • Самый яркий луч y=x/2, затем чуть выше y=2x/3, чуть ниже y=x/3. Причем для первых 500 значений функции около 1/5 значений попадают 'примерно' на x/2 (с погрешностью 10%). Происхождение лучей выяснить не удалось.--Boris Belousov 09:11, 2 декабря 2012 (UTC)
    • Очень интересно, спасибо! Но тогда надо найти способ упомянуть эту важную информацию в статье (например, в разделе «Асимптотика»). Не понял, в каком смысле «происхождение лучей выяснить не удалось». Самый яркий луч явно связан с тем свойством, что для всех нечётных n: $\varphi (n)=\varphi (2n)$, то есть на него попадают числа вида 2p. LGB 16:35, 2 декабря 2012 (UTC)
      • Сделано Да, это действительно так, только верно лишь для простых $n,$ так как для произвольного нечетного числа, вообще говоря, $\varphi (n)\not =n/2.$. Отразил это в статье.
• Zanka права, фраза в преамбуле «Не путать…» явно излишняя. Лучше перед текстом статьи поместить пояснение: Это статья о функции теории чисел. О других функциях, носящих имя Эйлера, см.: и далее краткий список.
  • На функцию распределения простых чисел я сделаю ссылку, а вот статьи про модулярную функцию в отечественной вики нет. Может, стоит создать ее? Я мог бы поместить туда преамбулу и кратко описать зачем она нужна. И тогда в своей статье добавить ссылку.--Boris Belousov 09:11, 2 декабря 2012 (UTC)
  • Исправлено Добавил в Список объектов, названных в честь Леонарда Эйлера информацию про другую функцию, а в начале оставил ссылку на функцию $\pi (x).$
• Раздел «Вычисление» логично поместить после теорем, на которые он опирается.
  • Это тонкий момент. Там очень много свойств, и человека, который зашел быстро посмотреть, как посчитать функцию, они могут мало интересовать, поэтому я хочу, чтобы самое основное было как можно выше. Свойства, которые используются для вычисления, указаны в доказательстве, поэтому, мне кажется, если кому-то будет интересно, почему, например, функция Эйлера мультипликативна, он сможет пройти ниже и посмотреть в свойствах.--Boris Belousov 11:57, 2 декабря 2012 (UTC)
  • Сделано
• Самое простое и наглядное, вполне школьное доказательство мультипликативности функции см., например, на странице Полная и приведенная системы вычетов. Приведенная там матрица $m\times n$ хорошо помогает пониманию доказательства.
  • Да, я видел его. Это, фактически, то же, что в статье написано сейчас, но в графическом виде. Я, наверное, добавлю тогда несколько вариантов доказательства. Тогда отпишусь.--Boris Belousov 11:57, 2 декабря 2012 (UTC)
  • Возникли трудности технического характера: не получилось вставить таблицу в шаблон hider.
• «функция Эйлера неоднозначна» — имеется в виду обратная функция. Лучше сказать: «значения функции Эйлера повторяются».
  • Исправлено Переформулировал этот раздел.--Boris Belousov 11:57, 2 декабря 2012 (UTC)
• В разделе «Определение числа генераторов в циклической группе» говорится просто о группе, хотя имеется в виду конечная группа. Ссылка на генератор у меня вызывает сомнение, см. статью Википедии о генераторах; термин «порождающий элемент циклической группы» в Википедии отсутствует, а надо бы добавить, зотя бы как перенаправление на Циклическая группа.
  • Исправлено Разумеется, предположение о конечности группы существенно, просто в статье всюду речь идет лишь о конечных множествах, поэтому упустил этот момент. Добавил перенаправление на циклическую группу с порождающего элемента.--Boris Belousov 11:57, 2 декабря 2012 (UTC)
• «Решение линейного уравнения» — может, лучше: линейного сравнения, как в статье о сравнениях?
  • Исправлено Да, эта терминология более распространена.--Boris Belousov 11:57, 2 декабря 2012 (UTC)

Пока всё. LGB 16:46, 30 ноября 2012 (UTC)

от Zanka

Для первой статьи это очень и очень хорошо, просто отлично. Пусть мои замечания вас сильно не смущают, я плохо нахожу границу между хорошими и избранными статьями и всегда хочу по максимуму. И ещё, часто мои замечания касаются стиля и некоторыми могут быть расценены как придирки. --Zanka 22:15, 27 ноября 2012 (UTC)

• Последний абзац введения мне кажется лишним. Введение - это выжимка всей статьи, а тут так много всего, про что сразу сказано, что в статье этого не будет. Где-то есть шаблон {{не путать}}, его можно применить для функции распределения простых чисел. Функцию комплексного переменного лучше упомянуть в теле статьи, а не во введении.
  • Сделано Добавил шаблон в начало статьи со ссылкой на функцию распределения простых чисел. Про функцию Эйлера из комплексного анализа добавил в статью Список объектов, названных в честь Леонарда Эйлера, на которую есть ссылка в статье Функция Эйлера внизу.
• Функцию Эйлера можно представить в виде произведения Эйлера "Можно представить" звучит не очень хорошо. И вообще, у вас вычисление функции опирается на её свойство мультипликативности, которое ещё пока и не упоминалось вовсе. При этом само произведение Эйлера, наверное, и называется так, потому что является формулой для собственно функции Эйлера. То есть фраза "Доказательство представимости в виде произведения Эейлера " тоже выглядит странно, кстати, исправьте там опечатку, пожалуйста.
  • Исправлено Да, вы правы, под произведением Эйлера понимают несколько другой объект. Был введен в заблуждение английской википедией. Переработал этот раздел.
• Некоторые значения как отдельный раздел выглядит слишком громко, может лучше сделать подразделом к вычислению? Или ещё лучше, саму таблицу поместить справа как картинку, а текст оставить просто в разделе вычисления. Если я не совсем понятно написала, скажите, я попробую исправить в самой статье и показать.
  • Сделано
• Фраза под таблицей значений мне кажется спрятана там, она как-то не читается после этой таблицы.
  • Сделано
• Функцию Эйлера от простого числа я бы тоже перенесла в раздел вычисления.
  • Сделано
• Все высказывания и формулы лучше снабдить ссылками на источники. Достаточно довольно известный учебник по теме или мат.энциклопедию. Заодно это покажет, что именно эти вопросы нужно было освезать в статье, а не какие-то другие.
  • Все формулы, которые не доказаны непосредственно в статье и не являются следствиями доказанных утверждений, имеют ссылки на источники.--Boris Belousov 12:33, 2 декабря 2012 (UTC)
    • Так не должно быть. Все формулы должны быть со ссылками на АИ, хотя бы чтобы понять что они нужны в этой статье, а не просто так. Все доказательства должны быть со ссылками на источник. Не стоит приводить доказательства от себя, даже если они вам кажутся очевидными. --Zanka 13:28, 2 декабря 2012 (UTC)
      • Сделано Добавил ссылки на АИ.
• Не пишите просто: "формула которая используется в RSA", добавьте "в криптографическом алгоритме RSA". Вообще же, у вас там есть целый раздел про применения, туда и надо помещать эту часть.
  • Сделано--Boris Belousov 12:35, 2 декабря 2012 (UTC)
• Кстати, формула у вас дана для m и n, а доказательство для m и m со штрихом.
  • В формулировке принято использовать разные буквы. В доказательстве же используются штрихи, чтобы подчеркнуть симметричность по m и n.--Boris Belousov 12:33, 2 декабря 2012 (UTC)
    • Логика от меня ускользнула. --Zanka 13:28, 2 декабря 2012 (UTC)
      • Я имел в виду, что по сути это не принципиально, какую букву писать. Однако, в конечном утверждении желательно иметь разные символы, чтобы подчеркнуть, что это просто два разных числа. В доказательстве же, акцент делается на симметрии произведения, которая активно используется там, поэтому предпочтительно выбрать обозначения, которые подчеркивают эту симметрию. С философской точки зрения, разницы, конечно, нет.
• В обобщённой мультипликативности вообще нет источников.
  • К сожалению, я не нашел книги, на которую можно было бы тут сослаться. Это иногда предлагают доказать как следствие мультипликативности в учебниках.--Boris Belousov 12:33, 2 декабря 2012 (UTC)
    • Собственно формула наверняка в книгах есть, а доказательство, если его нет в источниках, то и здесь его не должно быть. --Zanka 13:28, 2 декабря 2012 (UTC)
      • Сделано
• В частных случаях обобщённой мультипликативности есть фраза "Сравните с формулой ..." Так не пишут в энциклопедии. Предполагается какая-то аналогия, но какая, кто так сравнивает, что хотят сказать?
  • Сделано--Boris Belousov 12:33, 2 декабря 2012 (UTC)
• Структуру надо ещё раз продумать, пока не очень читается. Я дочитаю статью до конца и попробую предложить свой вариант.

Продолжение следует... --Zanka 22:15, 27 ноября 2012 (UTC)

Я бы вам предложила посмотреть на статью Логарифм в плане первого раздела. Сначала стоит снова повторить определение, дать область определения и область значений, возможно, функцию Эйлера от простого числа. Таблицу значений дать справа как картинку. Содержательная часть сейчас слабо структурирована. --Zanka 13:28, 2 декабря 2012 (UTC)

Исправил замечания, спасибо за комментарии и поддержку. --Boris Belousov 20:25, 15 декабря 2012 (UTC) --Boris Belousov 11:59, 5 января 2013 (UTC)

Некорректность доказательства мультипликативности

В статье написан бред. Фактически, там вводится отображение $\psi :\mathbb {Z} _{m}^{\times }\times \mathbb {Z} _{m'}^{\times }\rightarrow \mathbb {Z} _{mm'}$, где $\psi (a,a')=am'+a'm$. В первой теореме доказывается инъективность этого отображения. Вторая утверждает, что его область значений — не $\mathbb {Z} _{mm'}$, а $\mathbb {Z} _{mm'}^{\times }$. Для полноты доказательства необходима ещё сюръективность, сейчас можно только сказать, что $\varphi (m)\varphi (m')\leq \varphi (mm')$. Можно сослаться на китайскую теорему об остатках, можно повторить её доказательство для случая двух уравнений.

Предлагаю как-то так:

Покажем, что любой элемент $A$ приведённой системы вычетов по модулю $mm'$ представим в виде суммы $am'+a'm$. Для этого подберём соответствующие $a$ и $a'$ из приведённых систем вычетов по модулю $m$ и $m'$.

Поскольку $(m,m')=1$, расширенным алгоритмом Евклида можно найти линейное разложение единицы через $m$ и $m'$

$mn+m'n'=1$

Так как это верно для чисел, это верно и для кольца вычетов по модулю $mm'$

$mn+m'n'\equiv 1{\pmod {mm'}}$

Домножим обе части этого равенства на $A$

$m(nA)+m'(n'A)\equiv A{\pmod {mm'}}$

Найдено разложение $A$ в кольце по модулю $mm'$, а нужно в кольцах по модулю $m$ и $m'$. Положим

${\begin{matrix}a\equiv n'A&&{\pmod {m}}\\a'\equiv nA&&{\pmod {m'}}\end{matrix}}$

Покажем, что, действительно

$A\equiv am'+a'm{\pmod {mm'}}$

Домножаем определения $a$ и $a'$ на $m'$ и $m$, и, учитывая взаимную простоту $m$ и $m'$ получаем, что

${\begin{matrix}am'\equiv m'n'A&&{\pmod {mm'}}\\a'm\equiv mnA&&{\pmod {mm'}}\end{matrix}}$

Складываем

$am'+a'm\equiv mnA+m'n'A\equiv A{\pmod {mm'}}$

Что и требовалось доказать.

Pastafarianist 22:13, 26 ноября 2013 (UTC)