Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Арифметические приложения теории чисел. Теорема Паскаля. Вывод признаков делимости



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

Так как каждое целое число может быть представлено в виде суммы или разности целых чисел, в виде степени или суммы степеней, то достаточно научиться быстро находить остаток от деления суммы, разности, степени, суммы степеней на некоторое число m.

Из теории сравнении известно, что целое число a и остаток r от деления а на число m принадлежат одному в тому же классу вычетов по модулю m, т.е. ar (mod m). Остаток r является наименьшим неотрицательным вычетом класса а по модулю m. Пусть r1, r2,…, rn - остатки от деления чисел a1, a2,…, an на m. Тогда:

a1r1 (mod m)

a2r2 (mod m)

……………. (1)

anrn (mod m)

а)Складывая почленно сравнения (1), получим:

a1 + a2 + …+ anr1+ r2 +…+rn (mod m) (2)

Из (2) следует, что остатки от деления чисел a1 + a2 + …+ an и r1+ r2 +…+rn на m равны. Следовательно, нахождение остатка от деления числа a1 + a2 + …+ an на m можно заменить более легкой задачей - нахождением остатка от деления числа r1+ r2 +…+rn на m. Если r1+ r2 +…+rn < m, то r1+ r2 +…+rn и будет искомым остатком.

Вычитая, например, второе сравнение (1) из первого почленно, получим: a1 - a2 ≡ (r1- r2) (mod m) (можно и наоборот, тогда a2 – a1 ≡ (r2- r1) (mod m)). Вывод аналогичен предыдущему.

б)Умножая почленно сравнения (1), получим сравнение a1, a2,…, anr1, r2,…, rn (mod m). Отсюда вытекает утверждение, аналогичное утверждению пункта a).

в) Если a1 = a2=…=an, то получим: anrn (mod m). Следовательно, нахождение остатка от деления an на m сводится к нахождению остатка от деления rn на m. Задача упрощается, но при больших n и m может оказаться все же трудоемкой. Остановимся на наиболее употребительных приемах, применяющихся в этом случае.

1) Последовательное возведение в степень сравнения ar (mod m) с последовательной заменой правой части получающегося сравнения абсолютно наименьшими вычетами по модулю m. Перемножение соответствующих сравнений (см. пример 2).

2) Если rm взаимно просты, т.е. (r, m) = 1, то можно воспользоваться теоремой Эйлера (в случае простого m - теоремой Ферма).

По теореме Эйлера: rφ(m) ≡ 1 (mod m). Разделим далее n на φ(m) c остатком: n = φ(m)q+k. Тогда получим:

rn = rφ(m)q+k = rφ(m)q * rkrk (mod m) , и задача отыскания остатка от деления rn на m, таким образом, сводится к нахождению остатка от деления rk на m ( где k< φ(m)), что практически часто уже не вызывает затруднений.

3) Если m=р — число простое, то можно воспользоваться свойствами (и таблицами) индексов.

Имеем: rnx (mod р). Решая это сравнение, находим последовательно n ind r ≡ ind x (mod(p - 1)), х ≡ l (mod р). Наименьший неотрицательный вычет из этого класса чисел по модулю р - искомый остаток, он равен l.

Пример 1. Найдем остаток от деления числа n = (5622 +179 - 346) • 923 на 23.

Находим остатки от деления на 23 чисел: 5622 + 179 -346 = 5455 и 923; получим, соответственно, 4 и 3. Далее, так как 4-3 = 12, то n ≡ 12(mod23). Искомый остаток r = 12.

Пример 2. Найдем остаток от деления числа n = (63157 + 25028) • 926 на 12.

1) Находим остаток r1 от деления числа 63157. Так как 631 s 7 (mod 12), то 63157 s757 (mod 12). Так как 7 и 12 взаимно просты, то можно применить теорему Эйлера: 7 φ(12) ≡1 (mod 12). Но φ(12) = 4 и потому

74≡1 (mod12). Значит, 757 = 74*14 *7 ≡ 7(mod 12).

Следовательно, r1 = 7.

2) Находим остаток r2 от деления 25028 на 12. Так как 250≡ 10 (mod 12), то 25028 ≡ 1028 ≡ 228 * 528(mod 12).

Но по теореме Эйлера 54 ≡ 1 (mod 12) и потому 528 ≡ 1 (mod 12). Теорема Эйлера непосредственно к 228 не применима, так как числа 2 и 12 не являются взаимно простыми. Но 22 ≡ 1 (mod 3), а потому,

226 = (22)13 ≡ 1 (mod 3). Значит, 228 = 226 *22 ≡22(mod l2) (по свойству 11 сравнений). Итак, 1028≡1*4(mod 12). Следовательно r2 =4.

3) Находим остаток r3 от деления числа 926 на 12; r3 = 2. Таким образом, n≡ (7 + 4)* 2 = 22 = 10(mod 12), и искомый остаток r = 10.

Пример 3. Вычислим остаток от деления числа 7161 - 380 на 100.

Здесь (7,100) = 1, (3,100) = 1, φ(100) = 100(1 – 1/2)(l – 1/5) = 40, а потому

7161 - 380=(740)4 *7-(340)2=14*7 - 12≡6(mod100),T.e. остаток равен 6.

Пример 4. Вычислим остаток от деления 2721141 на 135. Имеем: (272,135) = 1, φ(135) = 135(1-1/3)(1-1/5) = 72. Так как 272=2(mod l35) и

1141 = 15*72 + 61,то

2721141 ≡21141 ≡ (272)15 *261 ≡261 (mod 135)

(так как 272 ≡ 1 (mod 135) no теореме Эйлера).

Далее, 61 = 1+32+ 16 + 8 + 4:

2≡2 (mod 135) (*)

22≡4 (mod 135)

24 ≡16 (mod 135) (*)

28≡256 ≡121 ≡-14 (mod 135) (*)

216= 196 ≡-39 (mod 135) (*)

232≡l521≡34(mod 135) (*)

Умножая сравнения (*), получим:

261 ≡2*16* (-14) * (-39) *34 = (2 * 16 *14) * (39 * 34) = 448 • 1326 ≡ 43*111 ≡ 48 (mod 135).

Окончательно имеем: 2721141 ≡261 ≡ 48(mod 135), т.е. искомый остаток равен 48.

Пример 5. Найдем остаток от деления числа 76317 на 29.

Так как 763≡9(mod 29),то76317 ≡917 (mod29). Число 29 простое, и можно поэтому воспользоваться свойствами индексов. Имеем: 917≡x (mod 29); тогда

17 ind 9 ≡ ind х (mod 28), 17 * 10 ≡ ind x(mod 28), ind x≡170 ≡ 2 (mod 28), x ≡ 4 (mod 29), следовательно, искомый остаток r=4.





Дата публикования: 2014-12-08; Прочитано: 2186 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...