Иллюстрированный самоучитель по Mathematica 5

Первообразные корни по модулю n. Показатели (функция MultiplicativeOrder).

Наименьшее натуральное решение т показательного сравнения km =1(modn) называется показателем числа k по модулю п. (Иногда это выражают иначе: говорят, что k принадлежит показателю т по модулю n.) В этом случае можно сказать, что k является корнем m-й степени из единицы в кольце классов вычетов по модулю т. Вот пример: 2 принадлежит показателю 4 по модулю 5.

Для вычисления показателя т в системе Mathematica предусмотрена функция:

Конечно, показатели существуют не во всех случаях, а только тогда, когда k ч п взаимно просты. Если показатель не существует, функция MultiplicativeOrder [k, n] остается невичисленной.

Функция MultiplicativeOrder может иметь еще третий параметр – список. Список {а,, а,,…, as} в вызове MultiplicativeOrder [k, n, {а,, а,,…, as } ] используется тогда, когда нужно найти наименьшее т, удовлетворяющее хотя бы одному из сравнений km =a, (mod/i). 3 является наименьшим натуральным числом, удовлетворяющим хотя бы одному из сравнений 2m =5 (mod n) и 2^m =8(modn).

Вот как это можно вычислить.

Пример 7.6.
Длина периода систематической дроби по основанию b. Вот функция, которая вычисляет длину периода систематической дроби, представляющей рациональное число r по основанию b.

Вот пример. Длина периода дроби 1/49 в десятичной системе равна 42.

А вот и подтверждение.

Что такое первообразный корень по модулю n

Решая сравнение k_m =l(modn) относительно k, можно заметить, что при некоторых n находятся такие k, которые принадлежат довольно большим показателям m. В частности, при некоторых n случается, что k принадлежит показателю, который равен числу вычетов, взаимно простых с n. Такие числа k называются первообразными корнями по модулю n.

Конечно, по составному модулю в большинстве случаев первообразных корней не существует. Первообразные корни существуют только по модулям 2, 4, рⁱ и 2 рⁱ (здесь р – произвольное нечетное простое число). Для вычисления первообразных корней по модулю и в системе Mathematica предусмотрена функция PrimitiveRoot [n].

Если первообразного корня не существует, функция остается невычисленной.

Следует помнить, что PrimitiveRoot использует Factorinteger как подпрограмму, так что она может не справиться с вычислениями в случае очень большого параметра.