Первообразные корни по модулю 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 как подпрограмму, так что она может не справиться с вычислениями в случае очень большого параметра.

Содержание раздела

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