АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Указание к работе. В силу теоремы Эйлера, для любых взаимно простых а и n выполняется соотношение:

Читайте также:
  1. IX. Отношение к работе (учебе).
  2. Анализ деятельности по работе с молодежью городского исполнительного комитета г. Набережные Челны
  3. Аннотация к работе (не менее 4-х предложений)
  4. АУТОТРЕНИНГ В РАБОТЕ ПЕДАГОГА
  5. Бригады к работе по наряду и распоряжению
  6. В СОЦИАЛЬНОЙ РАБОТЕ»
  7. Возвратившиеся члены бригады могут приступить к работе только с разрешения производителя работ (наблюдающего).
  8. Вопрос 104. Что является указанием на трубный глас и сколько раз протрубят в трубу в День воскресения?
  9. Вопрос 125. Что является указанием на (обязательность) веры в заступничество (шафа'а), кто станет заступником, кто получит право на заступничество и когда это будет?
  10. Вопрос 4. Мотивация к работе
  11. Вопрос 99. Что является указанием на обязательность веры в смерть?
  12. вопросов к контрольной работе по дисциплине «Управленческий консалтинг»

В силу теоремы Эйлера, для любых взаимно простых а и n выполняется соотношение:

af(n) º 1 mod n, (9.1)

где f(n) обозначает функцию Эйлера, значение которой равно числу положительных целых значений, меньших n и взаимно простых с n. Для простого числа p

f(p)=p-1,

Если предположить, что два числа p и q простые, тогда для n=pa*qb функция Эйлера будет иметь вид

f(n)= f(pa*qb)= f(pa)* f(qb)=[(p-1) pa-1]*[(q-1)qb-1]. (9.2)

 

Рассмотрим более общее соотношение, чем (9.1). Говорят, что число a, взаимно простое с модулем n, принадлежит показателю m, если m – такое наименьшее натуральное число, что выполняется сравнение

am º 1 mod n. (9.3)

Если а и n являются взаимно простыми, то существует, по крайней мере, одно число m=f(n), удовлетворяющее (9.3). Наименьшее из положительных чисел m, для которых выполняется (9.3), является длиной периода последовательности, генерируемой степенями а.

Справедливы следующие свойства.

Свойство 1. Числа a 0, a 1,…, a m-1 попарно несравнимы по модулю n. Действительно, al º ak mod n, l > k Þ al-k º 1 mod n, где l – k ÎN, l – k < m.

Свойство 2. ag º ag mod n Û g º g ’ mod m. Разделим g, g ’ на m с остатками

g = mq + r, g ’ = mq’ + r’. Тогда ag º ag Û amq+r º amq’+r Û ar º ar Û r’=r. Отсюда вытекает следующее свойство.

Свойство 3. m | f(n). Число, принадлежащее показателю f(n), называется первообразным корнем по модулю n.

Свойство 4. По любому простому модулю p существует первообразный корень. Первообразные корни существуют по модулям 2, 4, pa, 2 pa,где p – нечетное простое, a Î N.

Свойство 5. Пусть c = f(n) и q1, q2,…, qk – различные простые делители числа c. Число a, взаимно простое с модулем n, будет первообразным корнем тогда и только тогда, когда не выполнено ни одно из следующих сравнений:

Необходимость следует из того, что af(n) º 1 mod n и сравнение не имеет места при меньших показателях степени. Обратно, допустим, что a не удовлетворяет ни одному из сравнений, и пусть a принадлежит показателю m < c. Тогда m | c Þ c=mn. Обозначим через q простой делитель u. Тогда легко получить противоречие:

ac/q= amu/q =(am)u/q º 1 mod n.

 

Если некоторая последовательность имеет длину f(n), тогда целое число а генерирует своими степенями множество всех ненулевых вычетов по модулю n. Такое целое число называют первообразным корнем числа а по модулю n. Количество их равно для числа n

f(n-1), (9.4)

где f - функция Эйлера.

 

Пример ( Проверка Свойства 5. ). Пусть n =41. Имеем c = f(41) = 40 = 23 × 5. Итак, первообразный корень не должен удовлетворять двум сравнениям

 

a 8 º1(mod 41), a20 º1(mod 41).

 

Испытаем числа 2, 3, 4, …: 28 º 10, 220 º 1, 38 º 1, 48 º 18, 420 º 1, 58 º 18, 520 º 1, 68 º 10, 620 º 40. Отсюда видим, что 6 является наименьшим первообразным корнем по модулю 41.

 

Задание

Спроектировать и реализовать программу, определяющую для заданного числа все его первообразные корни и их количество.


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)