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

Модулярная арифметика: деление с остатком, вычеты, сравнения и китайская теорема об остатках

• Деление с остатком. Частное при делении с остатком (функция Quotient).

  При выполнении операции деления с остатком получается частное и остаток. Для нахождения частного и остатка в системе Mathematica предусмотрены функции Quotient и Mod. | Чтобы получить частное при делении (с остатком) л на т, нужно воспользоваться функцией Quotient [n,m]. Рассмотрим пример.

• Остаток от деления (функция Mod)

  Чтобы получить остаток от деления n на m, нужно воспользоваться функцией Mod[n,m]. Наименьший возможный остаток в этом случае равен нулю, а наибольший… Как вы думаете, чему равен наибольший возможный остаток? "Конечно, m-1", – возможно, подумали вы.

• Возведение в степень в модулярной арифметике (функция Power Mod)

  Иногда приходится решать задачи такого типа: | найти вычет аb по модулю n; | найти последние m цифр числа аb в системе счисления с основанием с. | Конечно, совсем несложно написать что-нибудь вроде Mod[a^b,n] или Моd[а^b, с^m].

• Китайская теорема об остатках (функция ChineseRemainder)

  Хитрый китаец Сунь Цю около 2000 лет назад (конечно, это могло быть и 200 лет до нашей эры, и 200 лет после начала нашей эры) открыл правило "гай-йен" ("большое обобщение"), которое является частным случаем целочисленного аналога интерполяционной формулы Лагранжа для полиномов.

• Корни в системе остаточных классов. Квадратный корень по модулю (функции SqrtMod и SqrtModList).

  Задача о корзинке с яйцами представляет собой задачу о решении системы сравнений вида u=ui(modmi) с попарно взаимно простыми модулями mt. Конечно, она допускает дальнейшие обобщения. Если не считать линейных сравнений и их систем, то наиболее простой из таких задач окажется задача об извлечении квадратного корня в системе остаточных классов, т.е. задача о решении сравнения хr = d (modn).

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

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

• Критерии простоты чисел специального вида. Простые числа Мерсенна, тест Люка-Лемера.

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

• Простые числа вида k * 2 n +1

  Для чисел вида k*2n +1 существует весьма эффективный критерий простоты. Он состоит в проверке сравнения а2n-1 =-1 (mod k*2n +1) для некоторого а. Однако выбор этого а зависит от k. Оказывается, нужно различать случаи, когда k не делится на 3 и делится на 3.