Доказательства теоремы Эйлера (теория чисел)

[Learnder]

Осваивая теорию чисел в рамках самостоятельного изучения школьной олимпиадной математики, я неизбежно столкнулся с теоремой Эйлера: $ a^{\varphi(m)} \equiv 1 \pmod m $ для всякого целого $ a $ и взаимно просто с ним $ m $. Элементарное её доказательство меня поначалу не устроило. Оно заключалось в рассмотрении приведённой системы вычетов по модулю $ m $ (по сути, мультипликативной группы вычетов по этому модулю). Множество тех же чисел, умноженных на $ a $, согласно взаимной простоте $ a $ и $ m $, будет давать тот же набор остатков по модулю $ m $. Значит, если перемножить все числа из первого набора и все числа из второго, то эти произведения будут сравнимы по модулю $ m $; обозначив произведение чисел из первого набора за $ x $, получаем: $ x \equiv a^{\varphi(m)} x \pmod m $, а поскольку $ x $ обязательно взаимно просто с $ m $, то из полученного сравнения следует искомое: $ a^{\varphi(m)} \equiv 1 \pmod m $. Это доказательство мне не нравится своей неконструктивностью: непонятно, с чего бы нам перемножать числа в указанных наборах, если только не знать, что это должно привести к успеху.

Во многих источниках я нашёл другое доказательство, обращающееся к следствию теоремы Лагранжа из теории групп. Оно утверждает, что порядок группы делится на порядок любой её подгруппы. Действительно, взяв любой элемент группы вычетов по модулю $ m $, можно рассмотреть порождаемую им циклическую подгруппу: тогда, если $ k $ - порядок этой подгруппы, то $ k \ | \ \varphi(m)$. Но раз $ a $ взаимно просто с $ m $, то его остаток при делении на $ m $ лежит в группе вычетов; пусть он равен $ a' $, тогда $ (a')^{\varphi(n)} = (a')^{k \cdot q} \equiv 1^q = 1 \pmod m $. Значит, и $ a^{\varphi(m)} \equiv 1 \pmod m $, что и требовалось. Но подобный приём кажется излишним: если возможно элегантное доказательство средствами мощного результата теории групп, то, быть может, его можно перевести на язык элементарной математики для данного частного случая, сохранив при этом элегантность?

Таким образом, возник вопрос: какова связь между представленным элементарным доказательством и доказательством, использующим теорему Лагранжа? Как непосредственно показать, что одно - частный случай другого?

[nnosipov]

Learnder в сообщении #1500702 писал(а):

Это доказательство мне не нравится своей неконструктивностью: непонятно, с чего бы нам перемножать числа в указанных наборах, если только не знать, что это должно привести к успеху.

Это просто такой полезный прием, который может пригодится и в других ситуациях.

Learnder в сообщении #1500702 писал(а):

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

Вряд ли теорему Лагранжа нужно считать таковым результатом. Вполне заурядный факт, вытекающий из очевидной равномощности смежных классов по подгруппе.

Конечно, более "правильное" доказательство --- это с точки зрения теоремы Лагранжа. Но это не отменяет более элементарные рассуждения. Скажем, частный случай теоремы Эйлера для простого модуля $m=p$ (малая теорема Ферма) можно доказать совсем просто с помощью биномиальной формулы Ньютона.

-- Чт янв 14, 2021 00:27:07 --

Learnder в сообщении #1500702 писал(а):

Осваивая теорию чисел в рамках самостоятельного изучения школьной олимпиадной математики

Вот, кстати: здесь разумно решать как можно больше задач, а для этого как раз полезно коллекционировать различные методы рассуждений (а не сравнивать, какой из них "хуже-лучше", все могут пригодится при решении конкретной задачи).

[Learnder]

Цитата:

Вряд ли теорему Лагранжа нужно считать таковым результатом. Вполне заурядный факт, вытекающий из очевидной равномощности смежных классов по подгруппе.

Во всяком случае, мне она кажется намного сильнее использованного в элементарном доказательстве приёма.

Цитата:

Вот, кстати: здесь разумно решать как можно больше задач, а для этого как раз полезно коллекционировать различные методы рассуждений (а не сравнивать, какой из них "хуже-лучше", все могут пригодится при решении конкретной задачи).

Да, с этим соглашусь: с точки зрения решения задач правильно коллекционировать методы и мотать на ус. Просто в данной теме я хотел разобраться именно с чисто теоретическим аспектом вопроса. Мне понятна пригодность элементарных рассуждений в подобных доказательствах, но здесь я хочу понять их связь с более общими (в данном случае - теоремой Лагранжа).

[nnosipov]

Во всяком случае, следствие из теоремы Лагранжа ($a^{|G|}=e$ для любого $a \in G$) можно доказать этим приемом.

Я бы выделил главную идею обоих рассуждений: при умножении всех элементов группы на фиксированный элемент мы получаем все те же элементы.

[Learnder]

Цитата:

Я бы выделил главную идею обоих рассуждений: при умножении всех элементов группы на фиксированный элемент мы получаем все те же элементы.

Хм. Да, действительно. Теперь я понял, почему это важная идея.

[nnosipov]

nnosipov в сообщении #1500717 писал(а):

Во всяком случае, следствие из теоремы Лагранжа ($a^{|G|}=e$ для любого $a \in G$) можно доказать этим приемом.

Для коммутативных групп (как меня правильно поправили).