Главная > Математика > Введение в теорию чисел. Алгоритм RSA
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 11.4. Предварительные замечания

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

Лемма. Если в абелевой группе есть два элемента порядков то в ней найдется элемент, порядок которого равен наименьшему общему кратному

Доказательство теоремы о примитивных корнях, приведенное в следующем параграфе, носит конструктивный характер, и доказательство леммы, сформулированной выше, будет его важной составной частью. Нам не достаточно информации о том, что такой элемент можно отыскать, нам потребуется метод его построения.

Доказательство. Как обычно, обозначим операцию в группе символом Предположим, что a и b — элементы группы порядков соответственно. Разложим порядки на простые множители:

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

Заметим также, что мы не будем придерживаться стандартного соглашения о возрастании простых делителей в списке: Для доказательства леммы нам удобнее считать, что простые делители выписаны в таком порядке: для некоторого

Введем обозначения

Заметим, что простые делители чисел различны, поэтому С другой стороны, произведение степеней простых чисел Более того, кратность, с которой каждое простое входит в разложение числа равна наибольшему из показателей и Таким образом, наименьшее общее кратное порядков

Поскольку делит делит найдутся такие натуральные и что Напомним, что а — элемент порядка группы элемент порядка s той же группы. Мы хотим показать, что порядок произведения равен т.е. наименьшему общему кратному порядков гид.

Прежде всего напомним, что по предположению леммы группа абелева. Для доказательства леммы нам потребуется следующее свойство операции если то

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

Итак, обозначим символом наименьшее общее кратное порядков а символом порядок элемента с. Как так и s делят число и можно записать: при некоторых натуральных Имеем

и из ключевой леммы следует, что должно делить

С другой стороны, поскольку порядок элемента с, то

Значит,

потому что порядок элемента а. Из ключевой леммы следует, что порядок элемента b (который равен должен делить Ввиду равенства мы заключаем, что s делит Однако взаимно просты. Поэтому делится на s (см. лемму из § 3.6).

Аналогичные рассуждения показывают, что делит Таким образом, взаимно простые числа делят Следоваг тельно, по лемме из § 3.6 число должно делиться на произведение

В итоге мы доказали делимость натуральных чисел тип друг на друга, т.е. Так может быть только в случае равенства Иными словами, порядок построенного нами элемента с равен наименьшему общему кратному порядков

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

Наконец, разберем обещанный ранее пример. Он показывает, что требование о коммутативности операции в группе нельзя выбросить из леммы без ущерба для ее истинности. Рассмотрим группу симметрии правильного треугольника. Напомним, что она не является абелевой группой. Возьмем осевую симметрию и поворот Порядки этих элементов равны, соответственно, 2 и 3. Если бы утверждение леммы оставалось верным и для не абелевых групп, то в нашелся бы элемент порядка 6. Но такого элемента в ней нет. Если мы, проигнорировав неабелевость группы выпишем элемент с по рецепту доказательства леммы, то увидим: элемент порядка 2.

<< Предыдущий параграф Следующий параграф >>
Оглавление