Учебник + задачник АП Ильиных

Шаг 3. Рассмотрим каноническое разложение числа n. Получим

n = pα1 1 pα2 2 · · · pαk k .

Покажем, что для каждого сомножителя pαi i, где i = 1, 2, . . . , k, существует число ai с показателем равным pαi i.

Запишем каждое из чисел n1, n2, . . . , np−1 в каноническом виде, и применим правило вычисления НОК по каноническому разложению. Сфор-

мулируем это правило.

Пусть a = pl11 pl22 . . . plkk и b = pm1 1 pm2 2 . . . pmk k . Тогда

Поэтому, если в правой части из (14.2) содержится сомножитель pαi i, то он является или сомножителем plii в a, или сомножителем pmi i в b. Итак, pαi i является делителем некоторого из чисел a или b. То же самое верно для НОК нескольких чисел.

В нашем случае в каноническом разложении n = pα1 1 pα2 2 · · · pαk k для НОК чисел n1, n2, . . . , np−1 взят сомножитель pαi i. Тогда pαi i является делителем некоторого числа nj, т. е. nj = pαi it. Показателем числа j является nj = pαi it. Тогда показателем числа ai = (j)t по свойству показателей 7 является число pαi i. Итак, найдено число ai с показателем pαi i.

Шаг 4. Рассмотрим произведение a = a1a2 . . . ak, где показатель числа ai равен pαi i. Покажем, что a – искомый первообразный корень.

По свойству 6 показателем числа a = a1 · · · ak будет произведение показателей сомножителей, т.е. pα1 1 pα2 2 · · · pαk k = n. Так как n = p − 1, то мы нашли число a с показателем ϕ(p) = p − 1. Поэтому a является первообразным корнем по модулю p. Теорема доказана.

ТЕОРЕМА 14.2. Первообразный корень по модулю m существует тогда и только тогда, когда выполнен один из случаев:

Доказательство теоремы можно найти в [4].

71

Пусть требуется определить, является ли число a первообразным корнем по модулю m. Нужно проверить, что ak 6≡1 (mod m) для всех k N, где k < ϕ(m). Число проверок можно уменьшить с учетом следующего утверждения.

ТЕОРЕМА 14.3 Пусть (a, m) = 1. Число a является первообразным корнем по модулю m тогда и только тогда, когда ak 6≡1 (mod m) для всех делителей k числа ϕ(m), отличных от ϕ(m).

Доказательство. Пусть a является первообразным корнем по модулю m и k – делитель числа ϕ(m), отличный от ϕ(m). Тогда k < ϕ(m). По пункту 2) из определения первообразного корня ak 6≡1 (mod m).

Обратно, пусть ak 6≡1 (mod m) для всех делителей k числа ϕ(m), отличных от ϕ(m). Если a не первообразный корень, то для показателя δ числа a имеем aδ ≡ 1 (mod m) и δ < ϕ(m). По свойству показателей 4 δ – делитель числа ϕ(m). Получили делитель k = δ числа ϕ(m), отличный от ϕ(m), для которого ak ≡ 1 (mod m), противоречие с условием. Поэтому a – первообразный корень по модулю m. Теорема доказана.

ТЕОРЕМА 14.4 . Пусть γ – первообразный корень по модулю p.

Тогда числа

γ0, γ1, γ2, . . . , γp−2

образуют приведенную систему вычетов по модулю p.

Доказательство. Применим признак приведенной системой вычетов при m = p (теорема 8.4 ). Нужно проверить, что для чисел из данной совокупности выполнены следующие три условия:

1)все числа взаимно просты с модулем p,

2)количество чисел равно ϕ(p) = p − 1,

3)все числа попарно не сравнимы по модулю p.

Справедливость условия 2) очевидна. Проверим условие 1). Так как γ – первообразный корень по модулю p, то (γ, p) = 1. Отсюда (γi, p) = 1 при i = 0, 1, . . . , p − 2.

Проверим 3). Пусть δ – показатель числа γ по модулю m = p. Так как

γ– первообразный корень, то δ = p−1. По свойству показателей 2 числа

γ0, γ1, γ2, . . . , γp−2 попарно не сравнимы по модулю p. Теорема доказана.

72

Лекция 15. Индексы. Свойства индексов.

Введем понятие индекса, во многом аналогичное понятию логарифма. Рассмотрим модуль m = p, где p – простое число. По теореме 14.1 существует первообразный корень γ по модулю p. Рассмотрим p − 1 чисел

γ0, γ1, γ2, . . . , γp−2. (15.1)

По предыдущей теореме эти числа образуют приведенную систему вычетов по модулю p.

Пусть a Z и a не делится на p. Тогда a взаимно просто с p и a содержится в некотором классе, взаимно простом с модулем p. В этом же классе содержится ровно одно число из приведенной системы вычетов (15.1). Поэтому существует такое число k, что a ≡ γk (mod p). Будем называть число γ основанием системы индексов.

ОПРЕДЕЛЕНИЕ 15.1. Число k > 0 называется индексом числа a по модулю p при основании γ, если

Таким образом, индекс числа a – это показатель степени, в которую нужно возвести основание, чтобы получить число, сравнимое с данным числом a. Индекс числа a при основании γ обозначаем через indγ a или через ind a, если ясно, о каком основании идет речь. Поэтому

Определение индекса аналогично определению логарифма, однако индекс определен неоднозначно. Допустим, что для некоторого числа k1 имеется запись k1 = indγ a. Это означает a ≡ γk1 (mod p). Рассмотрим

Поэтому любое число k2 > 0, сравнимое с индексом k1 по модулю p − 1, также индекс данного числа a. Обычно в качестве индекса будем указывать одно из чисел 0, 1, 2, . . . , p − 2.

73

Пусть m = 7. Существуют два первообразных корня γ = 3 и γ = 5.

ПРИМЕР. Найти индекс числа 4 при основании γ = 5.

РЕШЕНИЕ. Подбором найдем число k с условием 5k ≡ 4 (mod 7)). Имеем 52 ≡ 4 (mod 7)). Поэтому ind 54 = 2.

Рассмотрим в качестве основания индексов некоторый первообразный корень γ по модулю p. Справедливы следующие свойства индексов.

СВОЙСТВО 1. Два числа a1 и a2 сравнимы по модулю p, тогда и только тогда, когда их индексы сравнимы по модулю p − 1.

Доказательство. Обозначим indγ a1 = k1, indγ a2 = k2. По определению индекса γk1 ≡ a1 (mod p) и γk2 ≡ a2 (mod p). В равносильности (15.4) заменим γk на a1 и γl на a2. Получим

что и нужно.

СВОЙСТВО 2. Справедливы следующие утверждения:

а) indγ (a1a2 · · · ak) ≡ indγ a1 + indγ a2 + · · · + indγ ak (mod p − 1), б) indγ ak ≡ k · indγ a (mod p − 1).

Аналогичное свойство справедливо для логарифма: логарифм от произведения равен сумме логарифмов, показатель степени выносится за знак логарифма. В нашем случае знак равенства « = » заменяется на знак сравнимости « ≡ ».

Докажем а). По определению индекса справедливы сравнения

Умножив почленно данные сравнения, получим

Это сравнение означает, что indγ a1 + indγ a2 + · · · + indγ ak есть индекс числа a1a2 · · · ak при основании γ, что и утверждается в пункте а).

Пункт б) следует из пункта а) при a1 = a2 = . . . = ak = a.

74

Решение сравнений с помощью таблицы индексов. Рассмотрим применение индексов к решению сравнений. Для этого нам потребуются таблицы индексов для определенных значений p. Впервые таблицы индексов для всех простых модулей p 6 200 составил в 1837 г. академик М.В. Остроградский.

Найдем таблицу индексов по модулю p = 13 при основании γ = 2. Для этого возводим основание γ = 2 в степени с показателями, равными 0, 1, . . . , 11. Получаем ряд сравнений, где каждое последующее сравнение может быть получено из предыдущего умножением на число 2.

После этого заполняем таблицу индексов по модулю 13

Чтобы найти, например, индекс числа 12, рассматриваем строку с номером 1 и столбец номером 2. На пересечении находим индекс, равный 6.

Если известен индекс числа, то само число можно найти по таблице индексов. Однако удобнее воспользоваться другой таблицей

Эта таблица по индексу восстанавливает число. Допустим, что индекс некоторого числа x равен 6. По таблице находим x = 12.

Рассмотрим три вида сравнений, которые можно решить с помощью таблицы индексов. При этом используется основание γ, по которому составлены таблицы индексов.

Вместо indγ a записываем для краткости ind a.

75

ПРИМЕР 1. Решить сравнение первой степени

5x ≡ 2 (mod 13). (15.8) По свойству 1 из свойств индексов числа 5x и 2 сравнимы по модулю

p= 13 тогда и только тогда, когда их индексы сравнимы по модулю

p− 1 = 12.

Запишем сравнимость индексов чисел 5x и 2. Получим

При этом учтен пункт а) свойства 2.

Подставляя значения индексов из таблицы индексов по модулю 13, получим сравнения

По полученному индексу 4 из второй таблицы находим, что x = 3. Ответ x ≡ 3 (mod 13).

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

ПРИМЕР 2. Решить степенное сравнение

76

ПРИМЕР 3. Решить показательное сравнение

Поскольку (4, 12) = 4 и 10 6... 4, то сравнение 4x ≡ 10 (mod 12) неразрешимо. Поэтому и исходное сравнение неразрешимо.

Ответ. Сравнение не имеет решений.

77

Лекция 16. Системы счисления.

Рассмотрим некоторые арифметические приложения теории сравнений. Для записи натуральных чисел обычно применяется десятичная система счисления. При этом используется десять цифр 0, 1, . . . , 9. Рассмотрим, например, число a = 23759. Тогда

a = 2 · 104 + 3 · 103 + 7 · 102 + 5 · 10 + 9.

Каждая цифра в зависимости от позиции указывает число единиц, десятков, сотен и т.д. Мы имеем позиционную систему счисления.

Вместо десятичной системы счисления можно рассматривать g-ичную систему счисления, где g N и g > 1. В этом случае мы будем записывать натуральное число a в виде

где 0 6 ai < g. Числа an, an−1, . . . , a1, a0 – цифры, изображающие число a. В случае g = 2 получим двоичную систему счисления с цифрами 0, 1, при g = 8 – восьмиричную, при g = 16 – шестнадцатиричную. В последнем случае цифрами будут символы 0, 1, . . . , 9, A, B, C, D, E, F . При этом цифры A, B, C, D, E, F обозначают соответственно числа

10, 11, 12, 13, 14, 15.

ПРИМЕР. Дано число a = 1B5 в системе счисления с основанием 16. Чтобы указать на шестнадцатиричную систему счисления, записываем a = 1B516. Записать число a = 1B516 в десятичной системе счисления.

Решение. Имеем a = 1 · 162 + 11 · 16 + 5 = 43710.

ТЕОРЕМА 16.1. Всякое натуральное число a единственным способом записывается в g-ичной системе счисления.

Доказательство. Установим существование записи. Разделим число a на основание системы счисления g. Получим

где a0 – частное, a0 – остаток от деления a на g. По признаку остатка имеем 0 6 a0 < g. Поэтому рассматриваем a0 как g-ичную цифру.

Далее делим a0 на g, получаем a0 = a00 · g + a1. Подставим эту запись в (16.2). Тогда

78

Далее делим a00 на g, подставляем в (16.3) и т.д. Поскольку числа a0, a00, . . .

убывают, то процесс оборвется на некотором an, где 0 < an < g. Получим равенство (16.1). Оно означает, что число a имеет следующую запись в g-ичной системе счисления: a = ( anan−1 . . . a1a0 )g.

Докажем единственность записи. Пусть число a двумя способами записано в g-ичной системе счисления, т.е. наряду с записью (16.1), есть

где 0 6 a0 < g и 0 6 b0 < g Поэтому, как число a0, так и число b0 – можно считать остатком от деления a на g. Поскольку остаток определен однозначно, то a0 = b0. Приравняем записи в (16.1) и (16.4), сократим на a0 = b0, разделим на g и повторим рассуждение. Получим a1 = b1 и т.д.

Теорема доказана.

Признаки делимости. Из школьного курса математики хорошо известны следующие признаки делимости на 2, 3 и 9.

Число a делится на 2 тогда и только тогда, когда последняя цифра этого числа делится на 2.

Число a делится на 3 (делится на 9) тогда и только тогда, когда сумма цифр числа a делится на 3 (делится на 9).

С помощью теории сравнений легко получить эти и другие признаки делимости. Пусть требуется найти признак делимости числа a на число m. Если a ... m, то на языка делимости выражаем этот факт следующими словами:

1) число a делится на число m.

То же самое можно выразить на языке сравнений в виде записи a ≡ 0 (mod m), или в виде фразы:

2)число a сравнимо с нулем по модулю m.

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

79

ТЕОРЕМА 16.2. Число a делится на 9 тогда и только тогда, когда сумма цифр числа a делится на 9.

Доказательство. Имеем запись числа a = (an . . . a1a0)10, т.е. a = an ·10n + · · ·+ a1 ·10 + a0. То, что нужно доказать на языке делимости записывается в виде

Умножаем первое сравнение на a0, второе на a1 и т.д. Просуммировав получим

(an + · · · + a1 + a0) .. 9, что и нужно.

Аналогично получим признак делимости на m = 11. Рассмотрим число a = (an . . . a1a0)10, и просматриваем его цифры от a0 к an. Тогда

S = a0 + a2 + a4 + . . .

сумма цифр числа a, стоящих на нечетных местах,

S1 = a1 + a3 + a5 + . . .

сумма цифр стоящих на четных места.

ТЕОРЕМА 16.3 . Число a делится на 11 тогда и только тогда, когда S − S1 делится на 11, т.е.

80