Первообразные корни по модулю n
Первообразные корни по модулю n
Показатели — функция MultiplicativeOrder
Наименьшее натуральное решение т показательного сравнения km =1(modn) называется показателем числа k по модулю п. (Иногда это выражают иначе: говорят, что k принадлежит показателю т по модулю n.) В этом случае можно сказать, что k является корнем m-й степени из единицы в кольце классов вычетов по модулю т. Вот пример: 2 принадлежит показателю 4 по модулю 5.
Table[Mod[2го, 5], {m, 10}]
{2,4,3,1,2,4,3,1,2,4}
Для вычисления показателя т в системе Mathematica предусмотрена функция
MultiplicativeOrder[k, n].
MultiplicativeOrder[2,5] 4
Конечно, показатели существуют не во всех случаях, а только тогда, когда k ч п взаимно просты. Если показатель не существует, функция MultiplicativeOrder [k, n] остается невичисленной.
Функция MultiplicativeOrder может иметь еще третий параметр — список. Список {а,, а,,..., as} в вызове MultiplicativeOrder [k, n, {а,, а,, ..., as } ] используется тогда, когда нужно найти наименьшее т, удовлетворяющее хотя бы одному из сравнений km =a, (mod/i). 3 является наименьшим натуральным числом, удовлетворяющим хотя бы одному из сравнений 2m =5 (mod n) и 2m =8(modn).
Table[PowerMod[2,m,11],{m,10}]
{2,4,8,5,10,9,7,3,6,1}
Вот как это можно вычислить.
MultiplicativeOrder[2,11,{5,8}]
3
Пример 7.6. Длина периода систематической дроби по основанию b. Вот функция, которая вычисляет длину периода систематической дроби, представляющей рациональное число r по основанию b.
DigitCycleLength[r_Rational,b_Integer?Positive]:= MultiplicativeOrder[b,FixedPoInt[Quotient[#,GCD[#,b]]&, Denominator[r]]]
Вот пример. Длина периода дроби 1/49 в десятичной системе равна 42.
DigitCycleLength [1/4.9,10]
42
А вот и подтверждение.
N[1/49,151] 0.020408163265306122448979591836734693877551 020408163265306122448979591836734693877551 020408163265306122448979591836734693877551 02040816326530612244897959
Что такое первообразный корень по модулю n
Решая сравнение km =l(modn) относительно k, можно заметить, что при некоторых n находятся такие k, которые принадлежат довольно большим показателям m. В частности, при некоторых n случается, что k принадлежит показателю, который равен числу вычетов, взаимно простых с n. Такие числа k называются первообразными корнями по модулю n. Конечно, по составному модулю в большинстве случаев первообразных корней не существует. Первообразные корни существуют только по модулям 2, 4, рi и 2 рi (здесь р — произвольное нечетное простое число). Для вычисления первообразных корней по модулю и в системе Mathematica предусмотрена функция PrimitiveRoot [n].
PrimitiveRoot[5]
2
Если первообразного корня не существует, функция остается невычисленной.
PrimitiveRoot[11*13] PrimitiveRoot[143]
Следует помнить, что PrimitiveRoot использует Factorinteger как подпрограмму, так что она может не справиться с вычислениями в случае очень большого параметра.
