Deza_Kotova_Sbornik_zadach_po_teorii_chisel

задачu

1.Является ли система чисел {1, -1О, 2, 30, 8} полной системой вычетов

по какому-либо модулю?

2.Является ли система чисел {1, 3, 7, -1, -2} приведенной системой

вычетов по какому-либо модулю?

3.Выпишите по.Лную (приведенную) систему наименьших неотрица­ тельных вычетов по модулю n, n Е {2, 3, ... , 25}.

4.Выпишите полную (приведенную) систему наименьших по абсолют­ ной величине вычетов по модулю n, n Е {2, 3, ... , 25}.

5.Выпишите полную (приведенную) систему наименьших двузначных вычетов по модулю n, n Е {2, 3, ... , 25}.

б. Для каких модулей число чисел в приведенной системе вычетов равно

30?

7.Выпишите полную систему вычетов по модулю n, n Е {2, 3, ... , 25},

спомощью чисел, сравнимых с 3 по модулю 2n + 1.

8.Выпишите полную систему вычетов по модулю n, n Е {2, 3, ... , 25},

спомощью чисел, сравнимых с 6 по модулю 2n - 1, и расположите ее

в порядке возрастания наименьших по абсолютной величине вычетов.

9.Выпишитеприведеннуюсистемувычетовпомодулю n, nE {2,3, ... ,25},

спомощью чисел, делящихся на n - 1.

10.Выпишите приведеннуюсистемувычетовпо модулю n, n Е {2, 3, ... , 25},

спомощью чисел, делящихся на n + 1, и расположите ее в порядке

возрастания наименьших неотрицательных вычетов.

11.Выпишите полнw<> систему вычетов по модулю 28, состоящую из чи­

сел, являющихся значениями линейной формы 7х + 4у.

12.Выпишите полную систему вычетов по модулю 30, состоящую из чи­

сел, являющихся значениями линейной формы 10х +Зу.

13.Выпишите полную систему вычетов по модулю pq, состоящую из

чисел, являющихся значениями линейной формы рх + qy, если

р, q Е {2, 3, 5, 7, 11, 13, 17, 19}, р =/:- q.

14.Для каких модулей приведенная система вычетов в три раза короче

полной?

15.Для каких модулей приведенная система вычетов в пять раз короче полной?

16.Для каких модулей число чисел в приведенной системе вычетов со­ ставляет 2/5 от числа чисел полной системы вычетов?

17. При каких натуральных n имеет место соотношение:

д) 17IПpCBnl = 16/ПCBnl;

18. При каких натуральных n имеет место соотношение:

§15. Малая теорема Ферма

итеорема Эйлера

МШlая теорема Ферма утверждает, что для любого простого р и любого

целого а имеет место сравнение аР =a(modp).

Часто используется и такая формулировка: если р - простое число,

и а - целое число, взаимно простое с р, то аР-1 =l(modp).

Теорема Эйлера утверждает, что длялюбого натурального числа n и любо­

го целого а, взаимно простого с n, имеет место сравнение a'(J(n) =I(mod n),

где rp(n) - функция Эйлера.

Теорема Эйлера является обобщением малой теоремы Ферма и, в свою

очередь, обобщается теоремой Кармайкла.

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

имеет место сравнение aA(n) =l(mod n), где Л(п) - функция Кармайкла:

Л(ра) = rp(pa) для простого р ;;:: 3 и натурального а; Л(2а) = 2а-2 для

Длядоказательства теоремы Эйлерадостаточно рассмотреть приведенную

систему вычетов {х,, х2, ••• , X'(J(n)} по модулю n. Поскольку (а, n) = 1, то система {ах1, ах2, ••• , ax'(J(n)} также образует приведенную систему выче­

=al(J(n) • Х1 • Х2 • ••• • x'(J(n)(mod п) и, сокращая две части полученного срав­

нения на число х1 • х2 ·••• • x'(J(n), взаимно простое с модулем п, мы получим

соотношение a'(J(n) =l(mod n).

Теорема Ферма является частным случаем теоремы Эйлера, поскольку

<р(р) = р - 1 для простого числа р. Доказательство теоремы Кармайкла можно найти, например, в [3].

nрuмеры решенuя задач

б) 501990 в троичной системе счисления; в) 552000 в четверичной системе счисления.

г) 772011 в шестеричной системе счисления.

11.Найдите четыре последние цифры троичной записи числа 28 1000 .

12.Найдите пять последних цифр двоичной записи числа 282000 .

13.Найдите остаток от деления:

16.Найдите наибольший отрицательный вычет числа 28031002 по модулю

275.

17.Найдите наименьшее по абсолютной величине число, с которым

8747606 сравнимо по модулю 43.

18.Найдите абсолютно наименьший вычет числа 30033000 по модулю 297.

19.Найдите последнюю цифру числа:

а) 2048 в двенадцатеричной системе счисления;

б) 2048s в двенадцатеричной системе счисления; в) 1375 в десятичной системе счисления;

г) 137s3 в десятичной системе счисления.

20. Найдите две последние цифры десятичной записи числа:

21. Найдите наибольший отрицательный вычет, с которым сравнимо чис­

ло 201 1313330302252·17 по модулю 233.

22.Для любогь натурального числа n найдите остаток от деления 521"

на 37.

23.Найдите остаток от деления:

24. На какую цифру оканчивается число 77711 - 7771 в десятичной системе

счисления?

1

25.Найдите две последние цифры десятичной записи числа 771". , если

в конструкции участвует 1001 семерка.

2

26. Найдите остаток от деления числа 222." на 7, если в конструкции

участвуют n двоек.

s

27. Найдите остаток от деления числа 55s". на 35, если в конструкции

участвуют n пятерок.

s

28. Найдите остаток от деления числа 55s". на 100, если в конструкции

участвуют n пятерок.

29. При каких т имеет место сравнение:

а) m 5 + 7т + 8 =O(mod 3);

б) (m + l)m + mm+l =O(mod 3);

в) 2m 100 + 3m50 + 4m + 5 =O(mod 20)?

30. Докажите:

а) р ЕР, р > 3 => аР =a(modбp);

б) а= Ь(modp),p ЕР=> аР-1 +аР-2 Ь+аР-3 Ь2 +."+ьР-1 =O(modp).

§16. Линейные сравнения

исистемы сравнений

Пусть /(х) = атхт + ... + а1х + ао - многочлен с целыми коэффи­

циентами, и ат f. O(mod n). Если /(Ь)::: O(mod n) для некоторого Ь Е Z,

то /(х) =O(mod n) для любого х =Ь(mod n). В этом случае говорят, что

класс вычетов Ь0 = {х Е Z: х =Ь(mod n)} является решением сравнения

/(х) =O(mod n), которое называется сравнением степени т по модулю n.

Так, решением сравнения третьей степени 2х3 + 1 =O(mod 5) по мо­

дулю 5 является класс 3 = {х Е Z: х =3(mod 5)}, поскольку 2 · 33 + 1 =

5

=55 =O(mod 5). Кроме того, данное решение будет единствещ~ым, по­

скольку 2 · 03 + 1 f. O(mod 5), 2 · 13 + 1 f. O(mod 5), 2 · 23 + 1 f. O(mod 5), и 2 · 43 + 1f.O(mod5).

Теорема о линейных сравнениях (см. [3]) утверждает, что линейное срав­

нение ах =b(mod п) имеет ровно одно решение, если (а, n) = 1, ровно d

и не имеет решений в остальных случаях.

При этом единственное решение х =a(mod n) для случая (а, n) = 1

может быть найдено различными способами.

Простейший способ - перебор представителей всех классов вычетов

по модулю п до первого «Подходящего» класса. Этот способ применим

лишь для малых п.

Второй способ связан с рассмотрением сравнений ах =Ь(mod n),

вх = Ь + n(mod n), ах =Ь + 2n(mod n), "., ах =Ь + nk(mod n)""

с целью получения в правой части числа Ь + nk, делящегося на а. По­

скольку (а, n) = 1, то числа k и nk + Ь пробегают полную систему вы­

четов по модулю lal одновременно, то есть найдется единственное число k Е {О, 1, ... , lal - l}, такое что nk + Ь =O(mod lal). Следовательно, иско-

= Ь + пk

мое решение принимает вид х --(mod n), где k Е {О, 1, ... , lal-1}.

а

Третий способ основан на теореме Эйлера: поскольку a\?(n) ::: l(mod n), то искомое решение принимает вид х =Ьа1?<п>-1 (тоd n).

- система подходящих дробей для разложениЯ обыкновенной дроби n/a в цепную дробь. Мы подробнее остановимся на этом способе в разделе, посвященном цепным дробям.

Если же (а, n) = d, где d > 1 и dlЬ, то, разделив все три части сравнения ах= Ь(тоd n) на число d, мы получим новое сравнение первой

степени a/dx =Ь/d(mod n/d). Поскольку (a/d, n/d) = 1, то указанное

сравнение имеет единственное решение х =a(mod n/d) по модулю n/d.

НаЙдЯ это решение одним из указанных выше способов, мы запишем d решений первоначального сравнения по модулю п в виде х =а+ т/d ·

k(mod n), где k =О, 1, ... , d - 1.

Китайская теорема об остатках (см. [5]) утверждает, что система

линейных сравнений

{-: c1(modn1) ck(mod nk)

с попарно взаимно простыми модулями n 1 , ••• , nk имеет ровно одно реше­

ние, представляющее собой класс вычетов по модулю N = [n 1, ••• , nk] =

= n1 · ... · nk., которое имеет вид

=1, ... 'k.

Вобщем случае решением системы линейных сравнений

{-: = c1(modn1) ck(mod nk)

является класс вычетов по модулю N = [n1, ... , nk]: х =a(modN).

nрuмеры решенuя задач

1.Решите сравнение llx =5(mod 7) всеми возможными способами.

Решение. Прежде всего перепишем сравнение в виде 4х =-2(mod 7). Поскольку (4, 7) = 1, то сравнение имеет единственное решение -

класс вычетов по модулю 7.