ПРЕДИСЛОВИЕ К ТРЕТЬЕМУ ИЗДАНИЮ

При подготовке третьего издания учитывались требования курса «Алгебра и теория чисел».

По сравнению со вторым изданием осуществлены следующие дополнения: введены упражнения на темы «Решение неопределенных уравнений первой степени с двумя неизвестными в целых числах» и «Конечные цепные дроби»; даны различные методы обоснования признаков делимости чисел; увеличено количество упражнений для самостоятельного решения.

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

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

С. Горшенин.

ВВЕДЕНИЕ

Настоящий задачник-практикум является учебным пособием для студентов-заочников математических специальностей педагогических институтов. В пособии студент найдет образцы решения задач и материал для упражнений по всем основным разделам курса «Алгебра и теория чисел».

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

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

Одним из арифметических приложений теории сравнений является нахождение остатка от деления данного числа к на число Z; при выполнении упражнений такого характера в задачнике-практикуме в основном используется сравнение: ~

&=2(mod Z),

где 2—наименьший неотрицательный вычет по модулю /, который и является искомым остатком.

В разделе «Арифметические приложения теории сравнений» рассматриваются упражнения, отвечающие содержанию этого раздела программы. Студент-заочник должен уяснить, что изучением этого раздела не исчер-

пывается круг арифметических приложений теории чисел (отчасти и теории сравнений). Этим же целям служат приложения различных рассматриваемых в теории чисел числовых функций, теоремы Эйлера о сравнениях, малой теории Ферма, системы сравнений с одним неизвестным и др.

По каждому разделу программы в задачнике указана соответствующая литература. В основу положены следующие курсы:

Ш. X. Михелович. Теория чисел, изд. 2, перера- бот. и доп. М., «Высшая школа», 1967.

А. А. Бухштаб. Теория чисел, изд. 2, испр. М., «Просвещение», 1966.

ЧАСТЬ I

ЗАДАЧИ С РЕШЕНИЯМИ.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

КЛАССЫ ПО ДАННОМУ МОДУЛЮ.СРАВНЕНИЯ И КЛАССЫ

Ш. X. Михелович. Теория чисел, стр. 36—60.

А. А. Бухштаб. Теория чисел, стр. 72—99.

Вопросы для самопроверки

Когда два числа а и b сравнимы по модулю т?

Сформулируйте основные свойства сравнений.

В чем заключается условие, необходимое и достаточное для того, чтобы два числа а и b принадлежали к одному классу по данному модулю т"?

Что называется полной системой вычетов по данному модулю пг?

Что называется приведенной системой вычетов по данному модулю т>

Дайте определение функции Эйлера ф(и).

Сформулируйте основные свойства функции Эйлера.

Как читается теорема Эйлера?

Как читается малая теорема Ферма?

Разберите решения следующих примеров.

Пример 1. Даны три числа: 78, 210 и 346. Сравнимы ли они с 27 по модулю 11?

Решение. Вычтем из данных чисел 27. Получим числа 51, 183 и 319. Из этих трех чисел только 319 делится на 11, а поэтому только 346 сравнимо с 27 по модулю 11, т. е.

346=27(mod 11).

Пример 2. Показать, что З121^ 11 (mod 21).

Решение. Известно, что, если

a=6(mod m), то

(а, т) = (6, т).

В данном случае имеем:

(З121, 21) =3,

но (11, 21) =1, следовательно,

З121^ 11 (mod 21).

Пример 3. Дана совокупность чисел (9, 2, 16, 20, 27, 39, 46, 85).

Можно ли рассматривать данную совокупность как полную систему вычетов по модулю 8?

Решение. В соответствии с определением полной системы вычетов по модулю т совокупность соответствующих чисел при делении на т должна давать в остатке числа

0, 1, 2, 3, 4, ..., т— 1.

Легко установить, осуществляя последовательно деление чисел данной совокупности на число 8, что остатки будут равны числам

1, 2, 0, 4, 3, 7, 6, 5,а следовательно, данную совокупность можно рассмат-ривать как полную систему вычетов по модулю 8.

Пример 4. Дана совокупность чисел

(9, 2, 16, 20, 27, 39, 46, 86).

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

Решение. Сравнивая данную последовательность с последовательностью в примере 3, замечаем, что они отличаются только последним числом, и теперь уже два числа (46 и 86) дают в остатке при делении на 8 число 6. Чтобы получить нужную совокупность, надо заменить одно из них, например число 86, любым другим числом, дающим в остатке при делении на 8 число 5 (например, числом 85).

Пример 5. Написать полные системы абсолютно наименьших вычетов по модулям 7 и 8.

Решение. Если модуль т — нечетное число, то в искомой системе вычетов допустимо наибольшее по абсо- .т.— 1

лютнои величине число —^— ; если т — четное число, тоу. Искомыми полными системами абсолютно наименьших вычетов будут системы: (—3, —2, —1, 0, 1, 2,3),

если модуль равен 7, и (—3, —2, —1, 0, 1, 2, 3, 4) или (—4, —3, —2, —1, 0, 1, 2, 3), если модуль равен 8.

Пример 6. Дана полная система вычетов (9, 2, 16, 20, 27, 39, 46, 85) по модулю 8. Выбрать из этих чисел те, которые входят в приведенную систему вычетов по модулю 8.

Решение. В соответствии с определением из данной совокупности следует выбрать все числа, которые взаимно просты с модулем. Поэтому приведенная система вычетов по модулю 8 будет иметь еще вид: (9, 27, 39, 85).

Заметим, что приведенная система вычетов по модулю т содержит <р(т) чисел; ф (8) =4, т. е. искомая система должна содержать четыре числа.

Пример 7. Девятая степень однозначного числа п оканчивается цифрой 7; найти это число.

Решение. Так как девятая степень числа п оканчивается цифрой 7, то остаток от деления числа п9 на 10 должен быть равен 7, что равносильно справедливости сравнения

n9=7(mod 10).

Так как (7, 10) = 1, то (п, 10) = 1. Воспользовавшись теоремой Эйлера, получим:

n4=l (mod 10), где ф(10) =4.

Возведя обе части последнего сравнения в квадрат, придем к сравнению: n8 = l (mod 10). Тогда сравнение п9=7 (mod 10) примет вид:

n=7(mod 10), следовательно, п = 7.

Пример 8. Показать, что

118 + 218 + 318 + 418 + 518 + 618 = _1 (mod 7) .

Решение. Воспользуемся малой теоремой Ферма: если (а, р) =1, то

ap-i = l (mod ру

Числа 1, 2, 3, 4, 5, 6 взаимно просты с числом 7. На основании указанной теоремы

a6=l(mod7),(1)

где а=1, 2, 3, 4, 5, 6.

Сравнение (1) почленно возведем в куб, получим: a18=l(mod7).(2)

Складывая почленно сравнения вида (2) при а=1, 2, 3, 4, 5, 6, имеем:

1i8+2i8+3i8+4i8+5i8+6i8=6=—1 (mod 7).

Замечание. Решение значительно упрощается, если показатель степени есть нечетное число. Пусть требуется показать, что

lu + 2n+3u+4n=0(mod 5).

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

1h+2m+31i + 4h=111+2ii+ (—2)и++ (_l)ii=0(mod 5).

Пр им ер 9. Найти остаток от деления числа 7402 на 101.

Решение. 101 — простое число. Числа 7 и 101 взаимно просты, а поэтому из малой теоремы Ферма следует, что

7100=l(mod 101).

Возведем это сравнение почленно в четвертую степень. Получим:

7400=31 (mod 101).

Кроме того, 72=49 (mod 101). Перемножим эти сравнения:

7402=49 (mod 101).

Из последнего сравнения вытекает, что искомым остатком будет число 49.

Пример 10. Доказать, что кольцо классов по любому простому модулю р не содержит делителей нуля.

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

Пусть а, Ь, 0 — классы по простому модулю р; возьмем равенство

а-Ь = 0,

откуда следует справедливость сравнения а-6=0 (mod р).

Так как р— простое число, то либо aj р, либо b • р, следовательно, соответственно а=0, Ь = 0, и в кольце классов по простому модулю р отсутствуют делители нуля.

Пр имер 11. Найти последние две цифры числа 243402.

Решение. Очевидно, достаточно найти остаток, полученный при делении числа 243402 на 100.

243402^43402(mod 100).

Но (43, 100) =1, а поэтому

43»(100) = l(mod 100), т. е.

4340=l(mod 100).

Возведем последнее сравнение почленно в десятую степень:

43400=l(mod 100).

Возьмем сравнение

432=49(mod 100);

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

43402 г 49 (mod 100).

Следовательно, искомый остаток равен 49.

Пример 12. Показать, что (7312—1) делится на 105.

Решение. Каноническое разложение числа 105 дает:

105=3-5.7.

Замечая, что (73, 3) = (73, 5) = (73,7) =1 и 73 — простое число, применим малую теорему Ферма к числу 73 по модулям 3, 5, 7; получим сравнения:

732=l(mod 3), 734=l(mod 5), 73^1 (mod 7).

Путем возведения обеих частей сравнений в соответствующие степени, получим сравнения:

7312=l(mod 3), 7312=l(mod 5), 73I2=l(mod 7).

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

7312=l(mod 105),

откуда

(7312—1) : 105.

Пример 13. Показать, что число

13176— 1

делится на 89.

Решение. Воспользуемся формулой разложения разности квадратов:

13176—1 = (1388—1)(1388+1).

Если хотя бы один из сомножителей, стоящих в правой части этого равенства, делится на 89, то данное число делится на 89.

Так как 89 — простое число и (13, 89) =1, то на основании малой теоремы Ферма справедливо сравнение: 1388=l(mod 89),

откуда (1388—1) • 89, а следовательно, (13176—1) : 89.

Пример 14. Вывести признак делимости числа N на положительное число d, оканчивающееся единицей.

Решение. Запишем число N в виде

N=10a+b,

где а—количество десятков, b— цифра единиц числа N; положим d = 10^ + 1.

Пусть справедливо сравнение

10а+ 6=0 (mod 106+1),

заметим, что (6, 106 + 1) =1. Умножим обе части сравнения на число к, получим:

10а6+bk=O (mod 106 + 1).

Вычитая из левой части сравнения число 10а6+а, кратное модулю, приходим к сравнению

—a+66=0(mod 106 + 1),

откуда

а—6&=0(mod 10&+1).

Обратно. Пусть справедливо сравнение

а—6fe=0 (mod 10& + 1), откуда

—a+&^=0(mod 10^+1).

Прибавим к левой части сравнения число 10а^+а, кратное модулю, и в результате придем к сравнению 10a^ + b^=0(mod 10^ + 1).

Так как (6, 10^+1) =1, то, разделив обе части последнего сравнения на число к, получим:

10a+6=0(mod 10^ + 1).

Получен следующий признак делимости: для того чтобы число N делилось на число d = 10^ + 1, необходимо и достаточно, чтобы разность между количеством десятков числа N и цифрой единиц числа N, умноженной на число к, делилась на число d.

Заметим, что условие (к, 10А-Ц) = 1 используется лишь при доказательстве обратного положения.

Пример 15. Доказать, что если с • а, с ; Ь, где (а, 6) = 1, то с< ab.

Решение. Будем полагать, что а и b — положительные числа; приходим к сравнениям:

c=0(mod а),c=0(mod 6).

Учитывая, что (а, 6)=1, и тот факт, что если одно и то же сравнение имеет место по нескольким модулям, то оно справедливо по модулю, являющемуся наименьшим общим кратным данных модулей, приходим к сравнению с=0 (mod ab"), откуда

с • ab.

Пример 16. Установить делимость числа 29463 на число 183.

Решение. Разложим 183 на множители:

183=3-61,

при этом (3, 61) =1. Легко установить, что число 29463; 3. 12

Применим последовательно признак делимости на число 61. Получим: 2946—18=2928; 292—48 = 244; но 244 :’61, следовательно, 29463 • 183.

Заметим, что процесс может быть продолжен. Если вновь применим признак делимости на 61, в результате получим 24—24=0, 0 :61.

При м е р 17. Вывести признак делимости числа N на число 19.

Решение. Положим

N=\0a+b.

Пусть справедливо сравнение

10a + 6 = 0(mod 19);

так как (2, 19) =1, то, умножая на 2, получим:

20а+25=0 (mod 19).

Вычитая из левой части число 19 а, кратное модулю, приходим к сравнению

а+2&=0 (mod 19), т. е.

(а+26) ;' 19.

Обратно. Пусть справедливо сравнение a + 26 = 0(mod 19).

Прибавляя к левой части число 19 а, кратное модулю, приходим к сравнению

20а+26 = 0 (mod 19).

Так как (2, 19) = 1, то разделим обе части сравнения на число 2. Получим:

10a+6=0(mod 19), т. е. N ; 19.

Получили следующий признак делимости числа N на 19: число N тогда и только тогда делится на число 19, когда сумма количества десятков данного числа и удвоенной цифры единиц данного числа делится на число 19.

Упражнения

Среди чисел 216, 134, 214, 303, 21 найти все пары чисел, сравнимых между собой по модулю 5.

Среди чисел 135, 106, 181, 225, 167, 452 найти все пары чисел, сравнимых между собой по модулю 15.

Среди чисел 217, 42, 182, 241 найти все пары чисел, сравнимых между собой по модулю 12.

Даны три числа: 137, 343, 633. Какие из данных чисел сравнимы с числом 13 по модулю 31?

Даны три числа: 217, 201, 186. Какие из них сравнимы с числом И по модулю 19?

Даны три числа: 234, 634, 104. Какие из этих чисел сравнимы с числом 9 по модулю 25?

Показать, что сравнения:

1 l207=6(mod 27),

689 =7 (mod 16),

1325 =5(mod 30),

7101=3(mod 35),

8107=7(mod 14) не имеют места.

Написать полную систему наименьших положительных вычетов по модулям: а) 6, б) 11, в) 9, г) 13, д) 15.

Написать полную систему наименьших неотрицательных вычетов по модулям: а) 5, б) 7, в) 11, г) 12, д) 14.

Написать полную систему абсолютно наименьших вычетов по модулям: а) И, б) 9, в) 7, г) 8, д) 12.

Написать приведенную систему вычетов по модулям:

а) 5, б) 7, в) 9, г) 11, д) 12, е) 14, ж) 15.

Найти наименьшие положительные вычеты:

а) чисел ИЗ, 127, 41, 47, 53 по модулю И, б) чисел 84, 123, 71, 83, 101 по модулю 13, в) чисел 75, 83, 103, 117, 201 по модулю 15, г) чисел 63, 88, 97, 105, 136 по модулю 12, д) чисел 107, 121, 132, 150, 161 по модулю 17.

Найти наименьшие неотрицательные вычеты: а) чисел 115, 131, 57, 48, 83 по модулю 9, б) чисел 82, 127, 73, 89, 107 по модулю И, в) чисел 87, 131, 97, 103, 111 по модулю 12, г) чисел 69, 93, 100, 123, 141 по модулю 13, д) чисел 75, 89, 102, 137, 151 по модулю 15.

Найти абсолютно наименьшие вычеты: а) чисел 108, 123, 201, 75, 83 по модулю 10, б) чисел 97, 138, 61, 87, 151 по модулю 11, в) чисел 81, 102, 94, 107, 203 по модулю 13, г) чисел 57, 115, 138, 69, 107 по модулю 12, д) чисел 41, 87, 105, 13, 127 по модулю 14, е) чисел 77, 91, 138, 121, 101 по модулю 17.

Найти количество натуральных чисел, меньших чисел:

а) 101, б) 131, в) 270, г) 341, д) 600 и взаимно простых с ними.

Найти количество натуральных чисел, не превышающих числа:

а) 103, б) 144, в) 152, г) 160, д) 720 и взаимно простых с ним.

Показать, что:

l16+316+716+OI6=4(mod 10),

P4+514+714+ll14^4(mod 12),

111+2|1+411 + 511 +7I4+8n=0(mod 9),

l17+3I7+517+917+ll17+13I7=0(mod 14),

l13+513+713+ll,3=0(mod 12).

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

числа 111201 на число 1000,

числа 71199 на число 1000,

числа З157 на число 100.

Найти число, составленное тремя цифрами младших разрядов числа З798.

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

а) 1761, б) 1979, в) 7114, г) II203, д) 7302.

Исходя из представления данного числа N в виде N=\0a+b, где а — количество десятков, b— цифра единиц числа N, вывести признаки делимости числа N на числа:

а) 7, б) 13, в) 39, г) 59.

Используя соответствующие признаки делимости, установить делимость

числа 9633 на число 39,

числа 8918 на число 7,

числа 29148 на число 7,

числа 7493 на число 59,

числа 9633 на число 13.

СРАВНЕНИЯ С НЕИЗВЕСТНОЙ ВЕЛИЧИНОЙ

Ш. X. Михелович. Теория чисел, стр. 61—68, 82— 86,87—94, 98—115.

А. А. Бухштаб. Теория чисел, стр. 106—114, 120— 123, 126—131, 135—139.

Вопросы для самопроверки

Дано сравнение ax=b (mod m). При каких условиях оно имеет единственное решение, не имеет решений, имеет а>1 решений?

Какие вы знаете методы решения сравнений первой степени?

Напишите формулы решения сравнения

ax=b(mod m), где (а, т) =1.

Почему сравнение /:(x)=0(mod m) имеет не больше чем т решений?

Почему решения сравнения f (х) =0 (mod m) достаточно искать среди чисел 0, 1, 2, ..., т—1?

Дайте определение квадратичного вычета и невычета по данному модулю.

Сформулируйте закон взаимности.

Перечислите свойства символа Лежандра.

В чем заключается необходимое и достаточное условие того, чтобы сравнение f(x) =0(mod р )имело мак.- симальное число решений?

Сформулируйте критерий Эйлера для квадратичных вычетов и квадратичных невычетов.

Дано сравнение f(x) =0(mod р), где ^х^ — многочлен степени п^р. Как понизить степень этого сравнения, не нарушая эквивалентности сравнения?

При каких условиях сравнение f(x)=0(mod р) удовлетворяется тождественно?

При каких условиях многочлен n-й степени может быть разложен по простому модулю на п различных линейных множителей?

Разберите решения следующих примеров.

Пример 1. Решить сравнения:

5х=2 (mod 8);

7х=2 (mod 13).

Решение, а) Так как (5, 8)=1, то сравнение имеет единственное решение. Найдем его с помощью формулы

x^ba^W-1 (mod m).

ТогдаТогдах=2-5 ft8)-1 (mod 8),x=2-53=250=2(mod 8).

Тогда

Тогда

Ответ: x=2(mod 8).

Так как (7, 13) = 1, то сравнение

7x=2(mod 13),

имеет единственное решение.

Решим это сравнение методом проб, основанным на свойстве полной системы вычетов, заставляя х в форме 7х пробегать последовательно значения 0, 1, 2, ..., 12.

Устанавливаем, что значения х, равные 0, 1, 2, 3, не удовлетворяют данному сравнению. При х=4 имеем:

(7-4—2) : 13,

а следовательно, х=4 есть решение данного сравнения. Так как сравнение имеет единственное решение, то процесс нахождения решения закончен. Сравнению удовлетворяет целый класс чисел по данному модулю; следовательно, решение сравнения получаем в виде:

x=4(mod 13).

Замечание. Отметим, что метод решения сравнения, основанный на применении теоремы Эйлера и малой теоремы Ферма, нельзя отнести к рациональным методам решения сравнений.

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

5x=2(mod8).

Прибавим к правой части сравнения число 8, равное модулю, получим:

5x^10 (mod 8);

деля обе части сравнения на число 5, взаимно простое с модулем 8, приходим к результату:

x=2(mod 8).

7x=2(mod 13).

Прибавим к правой части число 26=13-2, имеем:

7№28(mod 13).

Так как (7, 13) =1, то после деления обеих частей сравнения на 7 получаем:

№4(mod 13).

Пример 2. Решить сравнение 115х=85 (mod 355).

Решение. Так как (115, 355) =5 и 85 делится на 5, то данное сравнение имеет 5 решений.

Сокращаем обе части сравнения и модуль на 5:

23x=17(mod 71).

Полученное сравнение имеет единственное решение:

х=10 (mod 71),

так как

23№230(mod 71).

Следовательно, данное сравнение имеет следующие решения:

№10 (mod 355),

х=81 (mod 355),

№152 (mod 355), х=223 (mod 355), №294 (mod 355).

Пример 3. Найти числа, которые при делении на 7, 13, 17 дают в остатке соответственно 4, 9 и 1.

Решение. Искомые числа должны удовлетворить системе сравнений:

’ x=4(mod 7),(1)

x=9(mod 13),(2)

I х==1 (mod 17).(3)

Так как модули сравнений попарно взаимно просты, то эта система имеет единственное решение по модулю М = 7-13-17.

Первое сравнение имеет единственное решение:

x=7f+4.

Подставим в сравнение (2) вместо х выражение 7^+4. Получим:

7/+4=9(mod 13),7^ 5 (mod 13).

Так как (7, 13) =1, то последнее сравнение имеет единственное решение ^10(mod 13), т. е. ^=10+13и. Откуда x=7(10+13u)+4=91и+74.

Найдем те значения и, при которых х будет удовлетворять и сравнению (3).

Имеем: 91u+74=l(mod 17) или 6u=12 (mod 17). Откуда u=2(mod 17), следовательно, и = 2 + 17 к. Итак, х=91 (2 + 176) +74=256 + 15476 или х = 256 (mod 1547).

Пример 4. Решить систему сравнений:

3x=5(mod 7),2x=3(mod 5),3x=3(mod 9).

Решение. Так как модули данных сравнений попарно взаимно простые числа, то данная система имеет решение по модулю, являющемуся произведением данных модулей, т. е. по модулю 315. Обращаясь к коэффициентам при неизвестном и соответствующим модулям, для первого сравнения имеем (3, 7) =1, для второго (2, 5) =1, для третьего (3, 9) =3 и, таким образом, первое и второе сравнения имеют единственное решение, третье сравнение— 3 решения. Легко установить, что решение данной системы сводится к решению трех систем:

Г x=4(mod 7), 1 x=4(mod 5), I х=1 (mod 9);Г x=4(mod 7), 1 x=4(mod 5), I х=1 (mod 9);( x=4(mod 7), I x=4(mod 5), I x=4(mod 9);( x=4(mod 7), I x=4(mod 5), I x=4(mod 9);x=4(mod 7), x=4(mod 5), x=7(mod 9).x=4(mod 7), x=4(mod 5), x=7(mod 9).

Г x=4(mod 7), 1 x=4(mod 5), I х=1 (mod 9);

Г x=4(mod 7), 1 x=4(mod 5), I х=1 (mod 9);

( x=4(mod 7), I x=4(mod 5), I x=4(mod 9);

( x=4(mod 7), I x=4(mod 5), I x=4(mod 9);

x=4(mod 7), x=4(mod 5), x=7(mod 9).

x=4(mod 7), x=4(mod 5), x=7(mod 9).

Далее можно найти все решения данной системы, решая каждую из полученных трех систем сравнений (см. решение предыдущего примера). Получим нижеследующие решения:

x=4(mod 315), х= 109 (mod 315), x=214(mod 315).

Решение данной системы может быть осуществлено значительно проще, а именно: решая первое и второе из данных сравнений, получим:

x=4(mod 7), x=4(mod 5).

Замечая, что левые и правые части сравнений одинаковы, воспользуемся свойством: если сравнение имеет место по нескольким модулям, то это сравнение имеет место по модулю, являющемуся наименьшим общим кратным дан-

ных модулей, т. е. система двух рассматриваемых сравнений равносильна сравнению

x=4(mod 35).

Далее можно, найдя решение третьего сравнения х=1 (mod 9), x=4(mod 9), х=7(mod 9), перейти к нижеследующим системам:

f x=4(mod 35), Г x=4(mod 35), f x=4(mod 35), t x=l(mod9); ( x=4(mod9); ( x=7(mod9).

Решение каждой из этих систем не вызывает затруднений. Заметим, что система сравнений

f x=4(mod 35), ( x=4(mod 9) сразу дает решение

x=4(mod 315).

Можно поступить иначе: к выше полученному решению первых двух сравнений в виде

x=4(mod 35), присоединим третье из данных сравнений 3x=3(mod 9)

и, заметив, что искомое решение данной системы должно быть получено по модулю 315, последовательно будем иметь:

х=356+4, 3 (356+4) =3 (mod 9), 1056=0 (mod 9),66=0 (mod 9).

Последнее сравнение имеет три решения по модулю 9, а именно:

6=0 (mod 9), 6=3 (mod 9), 6=6 (mod 9).

Получаем

х=35-9«+4 = 315и+4,х=35(9м+3) +4=315и+109,x=35(9u+6) +4=315и+214,или соответственно

x=4(mod 315), х= 109(mod 315), x=214(mod 315).

Остановимся еще на одном приеме решения системы сравнений.

При м е р 5. Решить систему сравнений:

( №2(mod 15),( x=7(mod 25).

Решение. Заметим, что данные модули, т. е. числа 15 и 25, не являются взаимно простыми. В этом случае следует сначала убедиться в существовании решений.

Если дана система сравнений:

{

№C](mod mi), №C2(mod m2),

где (mb т2) =а>1, то эта система будет иметь решение при условии:

cI=c2(mod а).

Обращаясь к данной системе сравнений, имеем: (15, 25) =5, 2=7 (mod 5), т. е. данная система совместна.

Из первого сравнения получаем:

х= 15/+2;

подставив это значение х во второе сравнение, приходим к сравнению

15/+2 = 7(mod 25), т. е.

15/=5 (mod 25).

После сокращения обеих частей сравнения и модуля на

5 получим:

3/=1 (mod 5),3/^6 (mod 5),/=2(mod 5),/=56+2;

теперь нахождение решения данной системы сравнений не вызывает затруднений:

х=15/+2= 15(56+2) +2 = 756+32,x=32(mod 75).

Найденное решение является единственным, что вытекает из единственности решения каждого из сравнений данной системы.

Правильность полученного решения может быть легко проверена его подстановкой в каждое из сравнений данной системы.

Замечание. Рассмотрим прием решения, который, на наш взгляд, является рациональным в целом ряде случаев.

Дана система сравнений:

/ axx=bx (mod т^,...

( a2x^62(mod m2),^'

где (ть /п2) = (Qi, m^ = (#2, m2) = 1. Эту систему заменим эквивалентной ей системой:

f x=Ci(mod mi),(2)

(x=c2(mod т^,

где первое и второе из сравнений системы (2) являются соответственно решениями первого и второго сравнений системы (1).

От системы (2) перейдем к системе

( m2x=m2ci(mod mrm2),/34

( m1x=mic2(mod m!-m2).^

Покажем эквивалентность системы сравнений (2) и системы сравнений (3).

Пусть Xi— любое решение системы сравнений (2) по модулю тх-т2. Тогда справедлива следующая система сравнений:

Г x^c^mod mi), t Xisc2(mod m2), которая после умножения обеих частей сравнений и модулей соответственно на т2 и mi приводит к справедливым сравнениям:

( m2Xi = m2Ci (mod тх-т2^,

(miXi = miC2(mod mi-m2),

откуда Xi — решение системы сравнений (3) по модулю трт2. Обратно, если х2 — любое решение системы сравнений (3) по модулю тх-т2, то справедлива следующая система сравнений:

( m2x2=m2Ci (mod mi-m2),\ mxx2=mxc2(mod mx-m2).

Следовательно,

Г x2=Ci(mod mi), ( x2=c2(mod m2)

и х2— решение системы сравнений (2) по модулю mi m2.

Таким образом, системы сравнений (2) и (3) эквивалентны, а так как система сравнений (2) имеет единственное решение по модулю mi-m2, то и система сравнений (3) тоже имеет единственное решение.

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

Пример. Решить систему сравнений:

( 3x=5(mod7), ( 2x=l (mod 5).

Решение: Так как (3, 7) = (2, 5)=1, то каждое из сравнений имеет единственное решение; (7, 5) = 1 и, следовательно, данная система имеет единственное решение по модулю 35.

От данной системы переходим к системе сравнений (15x=25(mod 35), 1 14x=7(mod 35)

и, вычитая из первого сравнения второе, получаем искомое решение:

x=18(mod 35).

Применим рассмотренный прием к некоторым решенным выше упражнениям.

Пример. Решить систему сравнений:

( 3x=5(mod 7), { 2х=3 (mod 5), I 3х=3 (mod 9).

Решение. Как установлено выше, система совместна и имеет три решения по модулю 315. Получаем систему:

( 135x=225(mod 315),I 126x^189 (mod 315),I 105x=105(mod 315).

Первые два сравнения дают

9x=36(mod 315).

Умножая обе части сравнения на 11, где (11, 315) = 1, имеем:

99x^396 (mod 315).

Вычитая полученное сравнение из сравнения

105x=105(mod 315),

приходим к сравнению:

6№24(mod 315),

а так как (2, 315) =1, то получаем:

3x^12 (mod 315).

Искомые решения:

x=4(mod 315), х= 109(mod 315), x=214(mod 315).

Пример. Решить систему сравнений:

( x=2(mod 15),( х=7 (mod 25).

Решение. Выше установлено, что данная система имеет единственное решение по модулю 75.

Переходим к системе сравнений:

f 5х=10 (mod 75),

( Зх=21 (mod 75),

откуда

2x53—11 (mod 75),2х=64 (mod 75),

так как (2, 75) = 1, то

x=32(mod 75)

является искомым решением.

Пример 6. Решить сравнение 17x=7(mod 30).

Решение. Модулем сравнения является составное число 30, каноническим разложением которого будет: 30=2*3’5. Следовательно, решение данного сравнения можно свести к решению системы:

17x=7(mod 2), 17x=7(mod 3),(1)

17х=7 (mod 5).

Система сравнений (1) эквивалентна следующей системе:

( х=1 (mod 2), | 2х=1 (mod 3), ( х=1 (mod 5).

Решение последней системы предлагаем найти читателю. Решением будет №11 (mod 30). Рекомендуем читателю решить данное сравнение, не сводя его к системе сравнений.

Пример 7. С помощью критерия Эйлера среди чисел 3, 5, 7 и 9 найти квадратичные вычеты по модулю 13.

Решение. Замечаем, что каждое из данных чисел взаимно просто с модулем, а поэтому критерий Эйлера применим.

Как известно, если (а, р) =1 и а 2=1 (mod р^ то

а — квадратичный вычет по модулю р.

В данном примере имеем:

36= (27)2 = 1 (mod 13);

5б= (25)3= (—1) 3=—1 (mod 13);

76= (49) 3= (—3) 3 =—1 (mod 13);

96=(—4)6=163=33=l(mod 13).

Итак, числа 3 и 9 являются квадратичными вычетами, а 5 и 7 — квадратичными невычетами по модулю 13.

Пример 8. Показать, что нечетное число, взаимно простое с числом 10, возведенное в тридцатую степень, может оканчиваться лишь цифрами 1 и 9.

Решение. Если х — искомое число, то решение сведется к нахождению числа а в качестве наименьшего неотрицательного вычета по модулю 10 в сравнении x30=a(mod 10),

где (х, 10) =1 (по условию задачи), (а, 10) =1 (по свойству сравнений).

Так как (х, 10) =1, ф (10) =4, то на основании теоремы Эйлера справедливо сравнение

х4=1 (mod 10).

Возведя обе части сравнения в седьмую степень, получим сравнение:

x28=l(mod 10).

На основании последнего сравнения и сравнения x30=a(mod 10) приходим к сравнению x2=a(mod 10), где (а, 10) = 1.

Остается найти квадратичные вычеты по модулю 10, которыми являются числа 1, 9, в чем можно убедиться, проверив, что из сравнений

х2=1 (mod 10), x2=9(mod 10), x2=3(mod 10), x2=7(mod 10)

только первые два имеют решения соответственно: х=1; 9 (mod 10), х=3; 7 (mod 10).

Пример 9. Решить сравнение: 5х2 + х—4=0 (mod 11).

Решение. Умножим обе части сравнения на число 20, где (20, 11) =1. Получим сравнение:

100х2 + 20х—80=0 (mod 11), или

(10х+1)2=81 (mod И).

Обозначим 10х+1 через z. Итак z2=81 (mod 11), или z2=4 (mod 11).

Решим это сравнение методом проб. Испытывая числа 0, 1, 2, ..., 10, видим, что сравнение имеет решения: z=2 и z=9, т. е. удовлетворяется при г = 2+Ш и г=9 + Ш.

Так как z=10x+l, то х= г^- , т. е. _Ш+1_ Ш+8.

I— 10 ’2 — 10 ’

при /=9 имеем Xi = 10 и при /=2 получаем х2=3.

Следовательно, данное сравнение имеет решения 3 и 10, т. е. ему удовлетворяют целые числа вида: х=3 + Ш, х=10+Ш.

Ответ:x=3(mod И),x=10(mod 11).

Замечание. Придя к необходимости решения сравнения

22 = 81(mod 11), получаем очевидное решение 2=9 (mod 11), а на основании одного из свойств двучленных сравнений получаем второе решение 2=11—9 (mod И), т. е. 2=2 (mod 11). Далее, как указано выше.

Пример 10. С помощью символа Лежандра установить, имеет ли решение сравнение: х2=22 (mod 13).

Решение. Если символ Лежандра^) =1, то сравнение х2 = а (mod р) имеет два решения, а если (“^) = = — 1, то сравнение решений не имеет.

Таким образом, решение сведется к вычислению символа Лежандра (-у|-) • Воспользуемся свойством: если

aa, следовательно,

a

a

„(ab2 \( а \

далее воспользуемся свойством ^—J = \~) , откуда

/ 22 \

Так как ^-pg-j = 1, то сравнение х2=22 (mod 13) имеет два решения.

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

Пример 11. Имеет ли решение сравнение:

x2=19(mod 31)?

Решение. К правой части сравнения прибавим число 62, кратное модулю, получим:

х2=81 (mod 31).

Отсюда х=9 (mod 31) и х=22 (mod 31).

Рассмотрим аналогичный способ решения 10-го примера.

x2=22(mod 13),x2=9(mod 13).

Следовательно, х=3 (mod 13), х=Ю (mod 13).

Пример 12. Решить сравнение:

х7—Зх6 + х5—х3 + 4х2—4x+2=0(mod 5).

Решение. Так как степень сравнения п>р, где р— модуль сравнения, то данное сравнение можно заменить эквивалентным ему сравнением, степень которого меньше модуля сравнения. Для этого многочлен

х7—Зх6+х5—х3 + 4х2—4х+2

разделим на х5—х; в остатке получим многочлен

х2—Зх + 2.

Следовательно, данное сравнение эквивалентно сравнению

х2—3x+2=0(mod 5).

Методом проб легко показать, что это сравнение имеет два решения:

х=1 (mod 5), x=2(mod 5).

Замечание. Сравнение х2—Зх + 2=0 (mod 5) можно представить в виде (х—1)*(х—2)=0 (mod 5), откуда х=1 (mod 5), х=2 (mod 5).

Пример 13. Сравнение 7х4—9х3+8х2 + 10х—6 = =0 (mod И) заменить равносильным ему сравнением со старшим коэффициентом, равным единице.

Решение. Так как старший коэффициент данного сравнения равен 7 и (7, 11) = 1, то находим единственное решение сравнения 7а=1 (mod 11) в виде a=8(modll).

Учитывая, что (8, 11) =1, умножим обе части исходного сравнения на число 8, не меняя модуля сравнения, и получим

56х4—72х3 + 64х2 + 80х—48=0(mod 11).

После ряда упрощений приходим к сравнению х4 + 5х3—2х2+3х—4=0 (mod 11), которое равносильно данному.

Этот же пример может быть решен иначе. Заменив коэффициенты данного сравнения числами, сравнимыми с ними по модулю 11, но меньшими по абсолютной величине, получим:

—4х4 + 2х3—Зх2—х +5=0 (mod И).

Умножим обе части сравнения на —3, не меняя модуля, так как число —3 взаимно просто с модулем, что вытекает из следующих соотношений: —3s8(mod 11), (8, 11) = 1. Получим сравнение:

12х4—6х3 + 9х2+3х—15=0 (mod 11), равносильное данному.

После упрощения приходим к сравнению х4+5х3—2х2+3х—4=0 (mod 11).

Пример 14. Разложить многочлен f (х) =х4+7х3+х—9 на множители по модулю 13.

Решение. Рассмотрим сравнение: х4+7х3+х—9s0(mod 13).

Легко заметить, что оно имеет решение х=1 (mod 13), а поэтому справедливо тождественное сравнение х4+7х3+х—9s (х—1) (х3 + 8х2 + + 8х+9) (mod 13).

Далее рассмотрим сравнение x3 + 8x2 + 8x+9=0(mod 13).

Оно также имеет решение xsl (mod 13), а поэтому х4+7х3+х—9s(х—I)2 (х2+9х+17) (mod 13), или

х4+7х3+х—9s(х—1)2(х2—4х+4) (mod 13).

Следовательно, искомое разложение имеет вид: х4+7х3 + х—9s (х—1)2(х—2)2(mod 13).

Пример 15. Разложить многочлен f(x) =х4—4х2 + х+2 на множители по модулю 7.

Решение. Рассмотрим сравнение х4—4x2+x + 2s0(mod 7).

Легко установить, что это сравнение имеет нижеследующие решения:

xsl (mod 7), xs—2 (mod 7).

получим:

(х—1)(х + 2) (х2—х—1)^0 (mod 7).

Остается либо попытаться найти решения сравнения

х2—х—1=0 (mod 7), либо установить, что последнее сравнение не имеет решений.

Можно было бы, например, пойти по пути проверки значений полной системы вычетов по модулю 7, применяя схему Горнера.

Мы выберем другой путь и прежде всего выясним, имеет это сравнение решения или нет.

Преобразуем сравнение

х2—х—1=0(mod 7).

Последовательно получим:

х2 + 6х—l=0(mod 7),(x + 3)2=3(mod 7).

Положим x + 3 = z, откуда

22=3(mod 7).

Применяя свойства символа Лежандра, получим: (”7*)= — (“т)~ — ("3”) = — и соответственно сравнение х2—х—1=0 (mod 7) не имеет решений.

Окончательно получаем следующее разложение данного многочлена

(х—1) (х+2) (х2—х—1) =0(mod 7).

Пр им ер 16. Выяснить, имеет ли сравнение

Зх3—x2 + 4x + l=0(mod 7) три решения.

Решение. Данное сравнение имеет три решения, если при делении х7—х на левую часть сравнения получим остаток, коэффициенты которого кратны модулю. Предварительно данное сравнение заменим эквивалентным ему сравнением со старшим коэффициентом, равным единице (см. решение примера 13). Получим сравнение х3 + 2х2—х—2=0(mod 7).

Остается найти остаток от деления х7—хнах3 + 2х2—х—2 и убедиться, что коэффициенты остатка кратны модулю.

Замечание. В отдельных случаях удается не только ответить на поставленный вопрос, но одновременно найти и решения сравнения. Так в данном примере имеем:

х3 + 2х2—х—2=0(mod 7), х(х2—1) +2(х2—1) =0(mod 7), (х2—1) (x + 2)=0(mod 7), (х—l)(x+l)(x+2)=0(mod 7), следовательно, х=1 (mod 7), х=—1 (mod 7), х= =—2 (mod 7) —решения данного сравнения.

Пример 17. Найти однозначное положительное число, 27-я степень которого оканчивается цифрой 7.

Решение. Если обозначим искомое число через х, то для нахождения его потребуется решить сравнение x27=7(mod 10), где (7, 10) =1.

По одному из свойств сравнения a=6(mod m), (6, m) = (а, т), отсюда (х, 10) = 1. Применив теорему Эйлера, получим сравнение

х4=1 (mod 10),так как ф (10) = 4. Возведем обе части последнего сравне-ния в 6-ю степень, после чего придем к сравнениюх24=1 (mod 10).

Тогда сравнение

x27=7(mod 10)

можно преобразовать следующим образом: x27=x24-x3=x3(mod 10), x3=7(mod 10).

Так как (х, 10) = 1, то, проверяя подстановкой в последнее сравнение числа 1, 3, 5, 7, 9, находим единственное решение х=3 (mod 10). Следовательно, 327=7 (mod 10).

Пример 18. Решить сравнение

х2=1 (mod 16).

Решение. Используем метод проб, подвергая проверке числа, взаимно простые с модулем, так как (1, 16) =1, т. е. числа 1, 3, 5, 7, 9, 11, 13, 15. Искомые решения:

х=1 (mod 16), x=7(mod 16), x=9(mod 16),x=15(mod 16).

Это подтверждает положение, что если модуль — составное число, то сравнение степени п по этому модулю может иметь более га решений.

Пример 19. Показать, что если а — нечетное число, то для того чтобы сравнение

x2=a(mod 8)

имело решения, необходимо и достаточно выполнение условия:

а=1 (mod 8).

Решение. Условие необходимости.

Пусть x=x0(mod 8)

есть решение данного сравнения, тогда х* ^a(mod 8),

так как (а, 8) =1, то %о—нечетное число, общий вид которого 4й±1. Легко видеть, что

(46±1)2=1 (mod 8).

откуда а= 1 (mod 8).

Условие достаточности. Если а=1 (mod 8), то данное сравнение равносильно сравнению х2=1 (mod 8),

которому удовлетворяет любое нечетное число, и данное сравнение имеет решения.

Пример 20. Показать, что произведение двух квадратичных вычетов по простому модулю есть квадратич- 32

ный вычет по тому же модулю, а произведение квадратичного вычета на невычет есть квадратичный невычет по тому же простому модулю.

Решение. Если а и b— квадратичные вычеты по модулю Р) то на основании критерия Эйлера:

р—i

а 2 = 1 (mod р), р-1

b 2 = l(modp).

Перемножая эти сравнения, имеем:

р—i

(а-b)2 = l(modp)

и ab— квадратичный вычет по модулю р. Во втором случае

р-1

^ab^ 2 =—l(modp)

и ab— квадратичный невычет по модулю р.

Пример 21. Доказать, что для символа Лежандра справедливо свойство

(f") = ^У-

Решение. На основании одного из свойств символа Лежандра справедливо:

(^M = (fM^Mv)'--^b

= k=q, в числителе символа= k=q, в числителе символаОстается положить а=Ь=с= считая количество сомножителей

= k=q, в числителе символа

= k=q, в числителе символа

Лежандра равным п.

УпражненияРешить сравнения:2х=3 (mod 5);3x=4(mod 7);7х=10 (mod 11);12x=7(mod 13);7x^11 (mod 15);5x=3(mod 17);3x=5(mod 11);9x=2(mod 14);УпражненияРешить сравнения:2х=3 (mod 5);3x=4(mod 7);7х=10 (mod 11);12x=7(mod 13);7x^11 (mod 15);5x=3(mod 17);3x=5(mod 11);9x=2(mod 14);10x=15(mod 25);9х=12 (mod 21);28x=40(mod 44);м) 24х=14 (mod 26);н) 21x=33(mod 45);о) 30x^18(mod 102);п) 21x=35(mod 77).10x=15(mod 25);9х=12 (mod 21);28x=40(mod 44);м) 24х=14 (mod 26);н) 21x=33(mod 45);о) 30x^18(mod 102);п) 21x=35(mod 77).

Упражнения

Решить сравнения:

2х=3 (mod 5);

3x=4(mod 7);

7х=10 (mod 11);

12x=7(mod 13);

7x^11 (mod 15);

5x=3(mod 17);

3x=5(mod 11);

9x=2(mod 14);

Упражнения

Решить сравнения:

2х=3 (mod 5);

3x=4(mod 7);

7х=10 (mod 11);

12x=7(mod 13);

7x^11 (mod 15);

5x=3(mod 17);

3x=5(mod 11);

9x=2(mod 14);

10x=15(mod 25);

9х=12 (mod 21);

28x=40(mod 44);

м) 24х=14 (mod 26);

н) 21x=33(mod 45);

о) 30x^18(mod 102);

п) 21x=35(mod 77).

10x=15(mod 25);

9х=12 (mod 21);

28x=40(mod 44);

м) 24х=14 (mod 26);

н) 21x=33(mod 45);

о) 30x^18(mod 102);

п) 21x=35(mod 77).

2. Решить системы сравнений:

а) .

x=3(mod 11), x=5(mod 7);

Д) •

7x=10(mod 11), 12x^7 (mod 13),

б) 1

x=6(mod 7),

7x=ll (mod 15);

I x=2(mod 13);

' x=13 (mod 16),

В) ]

[ x=3(mod 17), ( 3x=6(mod 9);

e) ■

x=3(mod 10), . x=9(mod 14);

r x=7(mod 11),

[ x=4(mod 15),

г) 1

x=3(mod 10),

ж) 1

x=l (mod 12),

( x=2(mod 3);

( x=7 (mod 14).

Найти числа, которые при делении на 13, 5 и 12 дают соответственно в остатке 5, 1 и 7.

Найти числа, которые при делении на 7, 11 и 13 дают соответственно в остатке 3, 2 и 5.

Найти числа, которые при делении на 7, И и 17 дают соответственно в остатке 3, 5 и 13.

С помощью критерия Эйлера установить, какие из чисел 3, 5, 7, 8 являются квадратичными вычетами по модулю 13.

С помощью критерия Эйлера установить, какие из чисел 5, 6, 7, 8 являются квадратичными невычетами по модулю 11.

С помощью критерия Эйлера установить, имеют ли решения сравнения:

x2=3(mod 7);г) x2=5(mod 7);

x2=5(mod 11);д) x2=7(mod 11);

x2=6(mod 13); е) x2=12(mod 13).

С помощью символа Лежандра установить, имеют ли решения сравнения:

x2=404(mod 523); е) x2=33(mod 179);

x2=99(mod 601); ж) x2=65(mod 193);

x2=219(mod 383); з) x2=26(mod 241);

x2=47(mod 73); и) x2=30(mod 269);

x2 = 231(mod 101); к) x2=42(mod 251).

Простейшим способом найти решения сравнений:

x2=20(mod 101);

x2=6(mod 47);

x2=7(mod 59);

x2=12(mod 23);

x2=7(mod 31).

Заменить данные сравнения равносильными им сравнениями, степени которых ниже р, где р— модуль:

л-8—3х7+2х6+3х4—2х2—l=0(mod 5);

х13—х3+х—3=0 (mod 11);

х8—2х7+3х6+х5—2х2—х—3=0(mod 5);

х9—Зх4+2х3—х+3=0 (mod 7);

х‘°+3х5—4х3+х2—3=0 (mod 7);

х14—х12+3х5—6х2+х + 1 =ty(mod 11).

Решить следующие сравнения:

х8—х®+х5—х4 + 2х2—x+3=0(mod 5);

х9—х3+х—5=0(mod7);

х8—х4+2х—3=0 (mod 5);

х12+2хн—2х—1=0(mod 11);

х14—4х13—x+6=0(mod 13).

Сравнения:

7х5—2х4+бх3—х2+Зх—2=0 (mod 11);

Их3—6х2 + 2х—5=0 (mod 15);

2х5—4х4+3х3—2x+3=0(mod 13);

Зх6—2х5+3х3+2х2—3=0 (mod 7);

5х4—Зх3+2х2—x+5=0(mod 11)

заменить равносильными им сравнениями со старшими коэффициентами, равными единице.

Разложить на множители:

многочлен х3—8х2—х+3 по модулю 11,

многочлен х4—Зх2—х+4 по модулю 7,

многочлен х4—4х3+4х—1 по модулю 7,

многочлен х4+6х3—Зх2+х+2 по модулю 13, д) многочлен х3+2 по модулю 5.

Имеет ли сравнение

х3+Зх—1=0 (mod 5), три различных решения?

Имеет ли сравнение

х4—5х2—3=0 (mod 7)

четыре различных решения?

Имеет ли сравнение

x2+3=0(mod 7)

два различных решения?

§ 3. СТЕПЕННЫЕ ВЫЧЕТЫ

Ш. X. Михелович. Теория чисел, стр. 125—146.

А. А. Бухштаб. Теория чисел, стр. 139—167.

Вопросы для самопроверки

Дайте определение показателя, которому принадлежит число а по модулю т.

На основании какой теоремы можно утверждать, что всякое число а, взаимно простое с модулем т, принадлежит тому или иному показателю?

Сколько существует различных показателей, которым могут принадлежать числа по модулю /п?

Дайте определение первообразного корня по данному модулю т.

Какому показателю принадлежит число а—первообразный корень по простому модулю т?

Сколько существует первообразных корней по простому модулю р?

Сформулируйте признак первообразного корня по простому модулю р.

Для какого вида чисел существуют первообразные корни по составному модулю?

Дайте определение индекса числа по простому модулю.

Сформулируйте основные свойства индексов.

Разберите решения следующих примеров:

Пример 1. Какому показателю принадлежит число 5 по модулю 12?

Решение. Должны быть выполнены следующие требования:

число, принадлежащее показателю, должно быть взаимно простым с модулем;

искомый показатель надо искать среди делителей числа <р(иг), где т— модуль;

искомый показатель должен быть наименьшим из положительных показателей, удовлетворяющих сравнению az==l (mod m), где а — испытуемое число.

В данном случае имеем:

(5, 12)=1; ?(12) = 12- (1^ (11-)=4;

делителями 4 являются числа 1, 2, 4; получим:

5=5(mod 12), 52=l(mod 12), следовательно, число 5 принадлежит показателю 2 по модулю 12.

При мер 2. Какому показателю принадлежит число 4 по модулю 12?

Решение. В данном случае нарушено одно из требований определения; числа 4 и 12 не являются взаимно простыми, а следовательно, сама постановка вопроса является ошибочной.

Пример 3. Зная, что число 2 есть первообразный корень по модулю 37, показать справедливость сравнения 218=62(mod 37).

Решение. На основании малой теоремы Ферма справедливо сравнение

236=l(mod 37), или

(218+1)(218—l)=0(mod 37), откуда

(218+1) (218— 1) : 37.

Так как 2 — первообразный корень по данному модулю, то

(218— 1) не : 37

и справедливо сравнение:

218+ 1=0 (mod 37),2i8=—l(mod 37).

Прибавляя к правой части сравнения число 37, равное модулю, имеем:

218=36(mod 37),218=62(mod 37).

Прим ер 4. Найти наименьший первообразный корень по модулю 7.

Решение. Для нахождения наименьшего первообразного корня по простому модулю р необходимо и достаточно:

найти все различные простые делители числа р—1 (обозначим их р\, р^ .... рк);

последовательно проверить числа, взаимно простые с модулем, начиная с числа 1; первое из чисел, которое не удовлетворяет ни одному из сравнений:

р-1р-1

q P1 = 1 (modpY ..., q Pk = 1 (modp)

будет искомым первообразным корнем.

Имеем 7—1 =6 = 2-3; таким образом, q будет первообразным корнем, если не имеет место ни одно из сравнений:

?3=l(mod 7), ?2=l(mod 7).

Так как

12=1 (mod 7).

то число 1 не является первообразным корнем по модулю 7;*

22=4 (mod 7), 23=1 (mod 7), и число 2 не является первообразным корнем по модулю 7;

32=2 (mod 7), 33=—1 (mod 7), следовательно, число 3 — наименьший первообразный корень по модулю 7.

При м е р 5. Показать, что составное число 4 имеет первообразные корни.

Решение. Надо показать, что по крайней мере одно из чисел, взаимно простых с модулем т, принадлежит показателю ф(т).

Возьмем сравнение

аг=\ (mod т), где (а, т) = 1.

Для данного примера имеем: я2=1 (mod 4). Находим ф(4)=2. Так как (3, 4) = 1, то проверяем число 3, получаем 3^3 (mod 4), 32=1 (mod 4), т. е. число 3 —первообразный корень по модулю 4.

Пример 6. Показать, что не существует первообразных корней по модулю 8.

Решение. Представителями классов чисел, взаимно простых с модулем, возьмем числа 1, 3, 5, 7: так как ф(8)=4, то показателями, которым могут принадлежать эти числа, являются делители числа 4, т. е. 1, 2, 4.

Имеем: Р = 1 (mod 8), т. е. 1 принадлежит показателю единица, остальные числа принадлежат показателю 2, так как

32=l(mod 8), 52= (—3)2=1 (mod 8), 72=(—1)2=1 (mod 8)

и первообразных корней по модулю 8 не существует.

Приведем более изящное решение. Любое нечетное число, а только нечетные числа взаимно просты с модулем 8=23, может быть представлено в виде:

а=4и±1;

возводя обе части в квадрат, получим;

откудаТак какоткудаТак какa2 = 24n2±23n+1,a2=l (mod 8).

откуда

Так как

откуда

Так как

ф(8)=4,

то, следовательно, не существует первообразных корней по модулю 8.

Пример 7. Найти наименьший из первообразных корней по модулю 37 и составить таблицу индексов, приняв этот корень за основание индексов; составить таблицу для нахождения числа по данному индексу.

Решение. Находим наименьший первообразный корень по модулю 37 (см. решение примера 4).

Устанавливаем, что искомым корнем является число 2. Это число принимаем за основание индексов. Находим наименьшие положительные вычеты по модулю 37, заставляя х пробегать последовательно значения от 0 до 35. Имеем:

2°=1

28=34

216=9

224= Ю

232 =7

2‘=2

29=31

217=18

223=20

233=14

22=4

210=25

218=36

226 =3

234=28

23=8

2Н = 13

219=35

227=6

235=19

24= 16

212=26

220=33

228=12

25=32

213=15

221=29

229=24

26=27

214=30

222 = 21

230= 11

27=17

215=23

223 =5

231 = 22

Таблица для нахождения по данному числу соответствующего ему индекса

N

0

1

2

3

4

5

6

7

8

9

0

0

1

26

2

23

27

32

3

16

1

24

30

28

11

33

13

4

7

17

35

2

25

22

31

15

29

10

12

6

34

21

3

14

9

5

20

8

19

18

Таблица для нахождения по данному индексу соответствующего ему числа

I

0

1

2

3

4

5

6

7

8

9

0

1

2

4

8

16

32

27

17

34

31

1

25

13

26

15

30

23

9

18

36

35

2

33

29

21

5

10

20

3

6

12

24

3

11

22

7

14

28

19

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

Пример 8. Найти число решений сравнений:

a) xI5=6(mod 37), б) 3x3=2(mod 37).

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

Берем индексы от обеих частей сравнения x15 = 6(mod 37)

и получаем сравнение

15indx=ind 6 (mod 36).

Так как ind 6=27(mod 36), то сравнение принимает вид:

15ind x=27(mod 36).

Это сравнение первой степени относительно ind х, и замечая, что (15, 36) =3 и 27 J 3, устанавливаем, что данное сравнение имеет 3 решения.

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

ind 3+3ind xs ind 2 (mod 36),3ind x=ind 2—ind 3(mod 36);

по таблице индексов находим:

ind 2=1 (mod 36), ind 3 = 26 (mod 36).

После соответствующей замены сравнение принимает вид:

3ind х=1—26 (mod 36),3ind №11 (mod 36).

Так как (3, 36) =3, 11 не ': 3, то это сравнение, а следовательно, и данное сравнение не имеют решений.

Пример 9. С помощью таблицы индексов решить сравнение

13x3=24(mod 37).

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

ind 13+3ind x=ind 24(mod 36).

Из таблицы индексов (первой) для простого числа 37 находим:

ind 13 = 11 (mod 36), ind 24=29(mod 36).

(Таблицы взяты из книги Ш. X. Михелевича. Теория чисел.)

Следовательно, H+3ind №29(mod 36), 3ind №18 (mod 36).

Так как (3, 36) =3 и 18 :" 3, то сравнение имеет три решения; после упрощения имеем: ind x=6(mod 12), откуда ind Xi=6(mod 36), ind x2=18(mod 36), ind x3= =30(mod 36), (см. решение сравнений первой степени);

по таблице индексов (для нахождения числа по данному индексу) находим:

Xi=27(mod 37), x2=36(mod 37), x3=ll(mod 37), являющиеся решениями данного сравнения.

При мер 10. Решить сравнение: 213x=215(mod 29).

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

Зх ind 21 =5ind 21 (mod 28); по таблице индексов находим:

ind 21 = 17 (mod 28) и сравнение принимает вид:

17 (Зх—5)=0(mod 28).

Так как (17, 28) = 1, то приходим к условию (Зх—5) • 28, которое эквивалентно сравнению 3x=5(mod 28), решение которого

х=11 (mod 28).

Рассмотрим другой способ решения. Воспользуемся следующим свойством: если g— первообразный корень по модулю р и

g-fe=g-*(mod р), то

& = Z(mod р—1).

Установив, что 21—первообразный корень по модулю 29, приходим к решению сравнения

3x=5(mod 28), откуда

х=11 (mod 28).

Пример 11. Найти все первообразные корни по модулю 17; записать их в виде наименьших положительных вычетов.

Решение. Задача может быть решена различными приемами. Рассмотрим их.

Можно использовать прием, посредством которого решен пример 4.

Находим наименьший первообразный корень по модулю 17 (см. решение примера 4), который равен 3; заметим, что если число g принадлежит показателю р—1, где р— модуль, то этому же показателю будут принадлежать числа вида gk, если (А, р—1) = 1 и 1<й<р—1. Выписываем числа 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15; среди них взаимно простые с числом 16 числа 3, 5, 7, 9, 11, 13, 15; вычислим остальные первообразные корни в форме наименьших положительных вычетов по модулю 17:

33=10(mod 17),

35 = 32 • 10=5 (mod 17), 37=35-32=5-9=11 (mod 17), 39 = 10-5-3= — 3 = 14(mod 17), 311 = 14-9 = — 3-9 = 7(mod 17), 313=7.9= 12 (mod 17), 3i5=12.9=(—5).g=6(mod 17).

Таким образом, первообразными корнями по модулю 17 являются числа 3, 5, 6, 7, 10, 11, 12, 14.

Пример 12. С помощью таблиц индексов найти показатель, которому принадлежит число 13 по модулю 79.

Решение. (13, 79) = 1, а поэтому искомый показатель должен удовлетворять сравнению 13s = 1 (mod 79).

Применяя свойство индексов, имеем:

б ind 13 = ind 1 (mod 78).

Пользуясь таблицей индексов, находим: ind 13=34(mod 78), ind 1=0 (mod 78), и сравнение принимает вид:

346 = 0 (mod 78),176=0(mod 39);

наименьшее положительное значение 6 = 39, удовлетворяющее этому сравнению, будет являться искомым показателем.

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

Решение. Возьмем сравнение: а8 =1 (mod 7), где (а, 7) = 1. Замечая, что число 1 принадлежит показателю 1, ограничимся значениями

а=2, 3, 4, 5, 6.

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

б ind a=0(mod 6), и надо найти наименьшее положительное б, удовлетворяющее условию

6ind а :. 6.

По таблице индексов находим:

ind 2=2(mod 6), ind 3 = 1 (mod 6),ind 4=4(mod 6), ind 5=5 (mod 6), ind 6=3 (mod 6).

Так, если a = 2, то условие принимает вид: 6-2 ;6, откуда 6=3. Аналогично находим: 1-6 -6, 6 = 6, и число 3 принадлежит показателю 6 (первообразный корень по модулю 7); 46 < 6, 6=3, и число 4 принадлежит показателю 3; 56 • 6, 6=6, и число 5 принадлежит показателю 6 (первообразный корень по модулю 7); 36 • 6, 6=2, и число 6 принадлежит показателю 2 по модулю 7.

Пример 14. Зная, что число 5 есть первообразный корень по модулю 7, найти, каким показателям принадлежат числа 52, 53, 54 по тому же модулю.

Решение. Так как число 5, являясь первообразным корнем по модулю 7, принадлежит показателю 6, то для решения поставленной задачи достаточно найти частное от деления числа 6 на наибольший общий делитель числа 6 и показателя степени испытуемого числа. Таким образом, для числа 52 имеем: ^^ =3, аналогично для числа 53 получим:^g^ =2, наконец, для числаб4—^4j=3.

Следовательно, данные числа принадлежат соответственно показателям 3; 2; 3.

Пример 15. Доказать, что первообразный корень g по простому модулю р есть квадратичный невычет по тому же модулю.

Решение. Из определения первообразного корня следует, что число g принадлежит показателю р— 1 по модулю р.

Напишем сравнение:

gp-i=l(mod р), где р:>2, и, преобразовав сравнение, получим: р—iр—1

(g 2 —0(g 2 +l)=0(mod р), откуда р-1р-1

(g 2 -l)(g 2 +1) -р.

Так как g— первообразный корень, то сравнение р—1 g 2 —l=0(mod р) невозможно и, следовательно, р—1р—1

g 2 +1=0(mod р), g 2 =—l(modp), следовательно, g — квадратичный невычет по модулю р. Пример 16. Число 43 — первообразный корень по модулю 89; показать, что сравнение

x2=43(mod89) не имеет решений.

Решение. На основании предыдущего упражнения устанавливаем, что число 43 — квадратичный невычет по модулю 89, и, следовательно, сравнение x2=43(mod 89) не имеет решений.

Пример 17. Показать, что среди первообразных корней по простому модулю р>2 не может быть полных квадратов.

Решение. Допустим, что это не так и первообразный корень g=k2. Тогда сравнение

x2=^2(mod р)

имеет очевидное решение x=£(mod р),

откуда g=h2— квадратичный вычет по модулю р, т. е. приходим к сравнению

р-1

g 2 = 1 (mod р), что невозможно, так как g — первообразный корень.

Упражнения

Какому показателю принадлежат:

число 2 по модулю 5,д) число 5 по модулю 11,

число 3 по модулю 7,е) число 6 по модулю 13,

число 5 по модулю 8,ж) число 7 по модулю 15,

число 7 по модулю 10,з) число 3 по модулю 17.

Найти все показатели, которым принадлежат числа:

по модулю 7,д)помодулю11,

по модулю 8,е)помодулю12,

по модулю 9,ж)помодулю13,

по модулю 10,з)помодулю15.

Распределить классы чисел по показателям:

а) по модулю 5, в) по модулю 7, д) по модулю 9, б) по модулю 6, г) по модулю 8, е) по модулю 10.

Найти наименьший первообразный корень:

по модулю11,г) по модулю 19,ж)по модулю 41,

по модулю13,д) по модулю 23,з)по модулю 43,

по модулю17,е) по модулю 29,и)по модулю 47.

Составить таблицу индексов:

а) по модулю 11, б) по модулю 19, в) по модулю 29

Решить сравнения:

25x=32(mod 59),

13x=24(mod 53),

12^’ = 17 (mod 47), г) З*2 =23 (mod 29).

Определить число решений сравнений:

a) x15=6(rnod 37),б) х3 =2 (mod 37).

С помощью таблиц индексов решить сравнения:

43x17=65(mod 79),

13x4=17(mod 37),

17x4=19(mod 73), г) 23x3=58(mod 97), д) 2x6=5(mod 31), е) 3x5=16(mod 31),

ж) 7х3=14 (mod 41),з) 2x4=33(mod 43),и) 5x3=38(mod 47).

Найти все первообразные корни:

а) по модулю 13, б) по модулю 19, в) по модулю 23,а) по модулю 13, б) по модулю 19, в) по модулю 23,г) по модулю 29, д) по модулю 31, е) по модулю 41.г) по модулю 29, д) по модулю 31, е) по модулю 41.С помощью таблиц которым принадлежат:а) число 5 по модулю 17, б) число 7 по модулю 19, в) число 11 по модулю 23, г) число 13 по модулю 29, д) число 8 по модулю 31,С помощью таблиц которым принадлежат:а) число 5 по модулю 17, б) число 7 по модулю 19, в) число 11 по модулю 23, г) число 13 по модулю 29, д) число 8 по модулю 31,индексов найти показатели,е) число 10 по модулю 37, ж) число 17 по модулю 41, з) число 19 по модулю 43, и) число 15 по модулю 47, к) число 23 по модулю 53.индексов найти показатели,е) число 10 по модулю 37, ж) число 17 по модулю 41, з) число 19 по модулю 43, и) число 15 по модулю 47, к) число 23 по модулю 53.

а) по модулю 13, б) по модулю 19, в) по модулю 23,

а) по модулю 13, б) по модулю 19, в) по модулю 23,

г) по модулю 29, д) по модулю 31, е) по модулю 41.

г) по модулю 29, д) по модулю 31, е) по модулю 41.

С помощью таблиц которым принадлежат:

а) число 5 по модулю 17, б) число 7 по модулю 19, в) число 11 по модулю 23, г) число 13 по модулю 29, д) число 8 по модулю 31,

С помощью таблиц которым принадлежат:

а) число 5 по модулю 17, б) число 7 по модулю 19, в) число 11 по модулю 23, г) число 13 по модулю 29, д) число 8 по модулю 31,

индексов найти показатели,

е) число 10 по модулю 37, ж) число 17 по модулю 41, з) число 19 по модулю 43, и) число 15 по модулю 47, к) число 23 по модулю 53.

индексов найти показатели,

е) число 10 по модулю 37, ж) число 17 по модулю 41, з) число 19 по модулю 43, и) число 15 по модулю 47, к) число 23 по модулю 53.

§ 4. АРИФМЕТИЧЕСКИЕ ПРИЛОЖЕНИЯ ТЕОРИИ СРАВНЕНИЙ

Ш. X. Михелович Теория чисел, стр. 147—160.

А. А. Бухштаб. Теория чисел, стр. 201—209.

Вопросы для самопроверки

На каких свойствах сравнения основано нахождение остатка при делении на данное число?

Сформулируйте свойства сравнений, на которых основаны выводы признаков делимости.

Чему равна длина периода (число цифр в периоде) чистой периодической дроби?

Сколько цифр между целой частью числа и первым периодом смешанной периодической дроби?

Получено 236-421=99 536. Чем вызвано, что проверка с помощью числа 9 не обнаруживает ошибки, допущенной в результате действия?

Разберите решения следующих примеров:

Прим ер 1. Найти остаток от деления числа 206п+5 на число 9, где п— целое неотрицательное число.

Решение. Замечая, что на основании метода сравнений можно вычитать и прибавлять к любой части срав-

нений числа, кратные модулю (это относится и к основанию степени), рассмотрим два случая, а именно:

п = 0, тогда имеем:

205=25 = 23-22= (—1) -22=5(mod 9),

п#=0, тогда последовательно имеем:

2Q6n+5^26n+5= (23)2n-25= (—1)2п- 5=5(mod 9).

Искомый остаток равен 5.

Пример 2. Показать, что при любом целом неотрицательном и число 3-52n+1+23п+! делится на число 17.

Решение. Как и в предыдущем примере рассмотрим два случая:

если п = 0, то очевидно число 17 делится на 17;

если п#=0, то последовательно имеем:

3 • 52п+1 + 23п+* =3 • 5 • (52)п +23п+' == (—2) (б^^+г3^1 = (—2) (23)” + 23”+*=0(тоб 17),т. е. данное число делится на 17.

Пр и м е р 3. Пользуясь основными свойствами сравнений, найти остаток от деления 125465 на 61.

Решение. Легко заметить, что

125=3(mod 61); 465=38 (mod 61).

Перемножим почленно эти сравнения. Получим, что 125-465=38-3(mod 61), т. е.

125-465=53 (mod 61).

Итак, искомый остаток равен 53.

Прим ер 4. Показать, что число 13176—1 делится на 89.

Решение. 13176—1 = (1388—1)(1388+1); 89 — число простое, а поэтому на основании малой теоремы Ферма 1388=l(mod 89),

т. е. (1388—1) • 89. Следовательно, (13176—1) • 89.

Пр имер 5. Показать, что число 14120—1 делится на 45.

Решение. (14, 45) = 1, а поэтому на основании теоремы Эйлера

14? (45)=l(mod 45), т. е. 1424 = 1 (mod 45), так как ф(45) =24.

Возведем последнее сравнение почленно в пятую степень. Тогда

14120=l(mod 45).

Это значит, что 14120—1 делится на 45.

Пример 6. Найти последние две цифры числа 5100.

Решение. Найти последние две цифры числа — это значит найти остаток, полученный при делении этого числа на 100.

5 юо=2550=б2525 = 2525 = 25 • 62512 ==25- 2512 =25 • 625®=25 • 25®=25 • 6253== 25 • 253 = 252 = 25(mod 100).

Итак, искомый остаток есть 25. Следовательно, последними двумя цифрами числа 5100 будут: 2 (десятки) и 5 (единицы).

Пр и м е р 7. С помощью таблиц индексов найти остаток от деления 1010 на 67.

Решение. Обозначим искомый остаток через г, т. е.

1010=r(mod 67).

Берем индексы от обеих частей сравнения:

lOind 10=ind г (mod 66).

Из первой таблицы индексов для простого числа 67 находим, что ind 10=16(mod 66), следовательно, 160= =ind r(mod 66),или ind r=28(mod 66). Теперь из второй таблицы индексов находим, что

r=23(mod 67).

Итак, искомый, остаток равен 23.

Замечание. Выше дан один из методов обоснования признаков делимости чисел. Рассмотрим второй метод, основанный на свойстве сравнений. Если f(x)=a0+aix+a2x2 +... + anxn

многочлен с целыми коэффициентами, где <zn#0(modm), х=у (mod m), то f(x) ^f(y) (mod m).

Поставим перед собой задачу в процессе обоснования использовать либо сравнение 10fe=l{mod d), либо сравнение 10ft=—l(mod d) (см. ниже), где к — целое поло-

жительное число, d — целое положительное число, о делимости на которое идет речь.

При м е р 8. Установить признаки делимости на число 11.

Решение. Рассмотрим некоторые из признаков.

Данное число N представим в виде

N=ао + щ • 10 + ^2* 102 + #3- 103 + ...,

где О^а^Э, d=ll. Справедливо сравнение 10^—1 (mod И).

Приходим к сравнению

N=a0—ai+a2—а3 + ... (mod 11).

Воспользуемся свойством: если a=b(mod m), то (а, т) = (&, т^ следовательно, если N \ 11, то (а0—«i + «2—#з+—) : Н, и обратно. Полученный признак делимости можно сформулировать в следующей форме: число N делится на число 11 тогда и только тогда, когда разность между суммой цифр числа N, стоящих на нечетных местах, и суммой цифр того же числа, стоящих на четных местах, делится на 11.

Замечая, что 1001 = 11-7-13, представим:

ДГ=^ + Я1-103+я2(103)2Н^^

где 0^a^999, d=ll. Справедливо 103=—l(mod 1001).

Приходим к сравнению

М=а0—ai + a2—a3 + ...(mod 1001).

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

N=a0—ai + a2—a3 + ...(mod 11).

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

[7V—(^о—^1 + ^2—Л3+ ...)] : И.

Известно, что если разность и уменьшаемое делятся на 11, то и вычитаемое делится на 11. А так же, если разность и вычитаемое делятся на 11, то и уменьшаемое делится на 11.

Теперь можно сформулировать соответствующий признак делимости: разбиваем число N на грани справа налево по три цифры в каждой грани; число N делится на число И тогда и только тогда, когда разность между суммой чисел, стоящих в четных гранях, и суммой чисел, стоящих в нечетных гранях, делится на 11.

Заметим, что признаки делимости на 7 и 13 аналогичны признакам делимости на 11. Для доказательства достаточно повторить все рассуждения, заменив число 11 соответственно числами 7 и 13.

Пример 9. Используя понятие числа, принадлежащего показателю, найти длину периода при обращении в 13 десятичную дробь обыкновенной дроби -^- .

Решение. (10, 17) = 1, а поэтому длина периода периодической дроби равна 6, где б есть показатель, которому принадлежит число 10 по модулю 17. Найдем б.

Для этой цели воспользуемся таблицей индексов для простого числа 17. Число 6 должно удовлетворять сравнению

10й =l(mod 17).

Берем индексы от обеих частей сравнения:

6ind 10=ind 1 (mod 16), или

36=0(modl6).

Наименьшее положительное число, удовлетворяющее этому сравнению, будет число 16. Следовательно, 6=16.

Пример 10. Найти длину периода и число цифр между запятой и периодом десятичной дроби, в которую обращается обыкновенная дробь -^q.

Решение. Каноническим разложением числа 220 будет 22-5-11. Так как (11, 10) = 1, то для нахождения длины периода найдем показатель 6, которому принадлежит 10 по модулю 11:

10=—1 (mod 11), 102=l(mod 11).

Следовательно, 6=2.

Число цифр % между запятой и первым периодом равно наибольшему показателю, с которым входят сомножители 2 и 5 в каноническое разложение знаменателя данной дроби.

Следовательно, Х = 2.

Пр им ер 11. Проверить результаты действий с помощью числа 9:

24667+18265=42932;

5433153:4371 = 1243.

Решение, а) Суммы цифр слагаемых соответственно равны 25 и 22; сумма цифр суммы — 20. Легко заметить, что 25+22=20 (mod 9).

Следовательно, в первом примере можно полагать, что сложение выполнено правильно.

Во втором примере суммы цифр делителя и частного соответственно равны 15 и 10; сумма цифр делимого 24. Так как 24=150(mod 9), то можно полагать, что деление выполнено правильно.

Пример 12. Показать, что остаток от деления числа З19-37-1 на 19-37 равен 1.

Решение. Достаточно показать, что справедливо сравнение

319.37-1 =i(mod 19-37).

Преобразуем показатель степени:

19-37—1 = (18 + 1) (36+1)—1 = 18-36 + 54.

Так как (19, 37) = 1, то

Ф (19-37) = ф (19) -ф (37) = 18-36.

На основании теоремы Эйлера

3i8-36 = i (m0d 19-37), где (3, 19-37) =1.

С другой стороны, имеем:

319-37-1 =3 18.36 .354 = 354 (mod 19.37).

На основании малой теоремы Ферма 3I8=l(mod 19), где (3, 19) = 1. Непосредственным вычислением легко установить, что 318=l(mod 37) (см.решение примера 1).

На основании свойства, по которому из сравнимости двух чисел по нескольким модулям вытекает их сравни-

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

318=l(mod 19-37).

Возведя обе части сравнения в третью степень, получим:

354=l(mod 19-37).

Итак,

319-37-1 = 1 (mod 19.37).

Упражнения

Найти остаток от деления числа 485п+3 на 11, где п — любое целое неотрицательное число.

Найти остаток от деления числа 485п+4 на 11, где п — любое целое неотрицательное число.

Показать, что при любом целом неотрицательном

п число 7 - 33n+1—23n+1 делится на 19.

Показать, что при любом целом неотрицательном п число 25-72п+23п+4 делится на 41.

Показать, что при любом целом неотрицательном п число 11 -35n+2- 132n+1 делится на 37.

Найти две цифры младших разрядов чисел:

а) 540, б) 632, в) 813, г) З12, д) 233, е) 420.

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

а) II802, б) 131602, в) 71203, г) 172001, д) 192402 на число 1000.

Вывести и сформулировать признак делимости на число 11, исходя из сравнения

102=l(mod 99);

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

Вывести и сформулировать признак делимости на число 33, исходя из сравнения

102=l(mod 99);

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

Вывести и сформулировать признаки делимости на числа 27 и 37, учитывая, что

999 = 27-37,

и используя сравнение

103=l(mod 999);

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

Используя соответствующий признак делимости, проверить делимость чисел:

3038035, 3138135, 3539635 на число И;

4735731, 4739735 на число 11;

3138135, 4735731 на число 33;

559013, 3038035 и 3138135 на число 13;

3038035 и 3539635 на число 65;

52434, 79974, 111888 на число 27;

11934, 52434, 111888 на число 54;

121878, 141858, 145854 на число 37;

111888, 121878, 145854 на число 111;

90585 и 254925 на число 165.

С помощью таблиц индексов найти остатки от деления:

числа 85-79 на число 97,

числа 53-41-17 на число 59,

числа 89-78 на число 61.

Используя таблицы индексов найти остатки от деления:

числа 1319 на число 31,

числа 29’7 на число 41,

числа 3118 на число 37,

числа 1719 на число 53,

числа 723 на число 59,

числа И37 на число 61,

числа 1932 на число 67.

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

а) со знаменателем 7, б) со знаменателем И, в) со знаменателем 13, г) со знаменателем 23,а) со знаменателем 7, б) со знаменателем И, в) со знаменателем 13, г) со знаменателем 23,д) со знаменателем 29, е) со знаменателем 31, ж) со знаменателем 37, з) со знаменателем 43.д) со знаменателем 29, е) со знаменателем 31, ж) со знаменателем 37, з) со знаменателем 43.

а) со знаменателем 7, б) со знаменателем И, в) со знаменателем 13, г) со знаменателем 23,

а) со знаменателем 7, б) со знаменателем И, в) со знаменателем 13, г) со знаменателем 23,

д) со знаменателем 29, е) со знаменателем 31, ж) со знаменателем 37, з) со знаменателем 43.

д) со знаменателем 29, е) со знаменателем 31, ж) со знаменателем 37, з) со знаменателем 43.

Найти длину периода и количество цифр между запятой и периодом десятичной дроби, в которую обращается обыкновенная несократимая дробь:

а) со знаменателем 35, б) со знаменателем ПО, в) со знаменателем 76, г) со знаменателем 210,

д) со знаменателем 208, е) со знаменателем 620, ж) со знаменателем 85, з) со знаменателем 860.

С помощью числа 9 проверить результат арифметических действий:

а) 24667 + 18265= 42932, д) 4371-1243 = 5433153, б) 141811 + 17128=158932, е) 1042-1011 = 1053462, в) 37918—13207 = 24711,ж) 421767:3429=123,

г) 42932—18265= 24667,з) 115403365:23845=48417.

§ 5. НЕПРЕРЫВНЫЕ ДРОБИ

Ш. X. Михелович. Теория чисел, стр. 69—82, 161—176.

А. А. Бух штаб. Теория чисел, Лгр. 58—66.

Вопросы для самопроверки

Что вы знаете о представлении любого рационального числа непрерывной дробью?

Запишите свойства подходящих дробей.

Запишите формулу решения сравнения ax=6(mod m), где (а, т) = 1, основанного на методе подходящих дробей.

Разберите решения нижеследующих примеров.

53

Пример 1. Разложить рациональное число-gj- в цепную (непрерывную) дробь; составить таблицу ее подходящих дробей, найти подходящую дробь второго порядка.

Решение. Находим элементы (неполные частные):

53 I 21— 42 ~2~_ 21 I И2LM

11 I 10-ю |—

10 I

-_10 Тоо

53

Следовательно, -^- = [2,1,1,10]—разложение данного рационального числа в конечную цепную дробь.

Для ответа на второй вопрос составим таблицу

к

0

1

2

3

ч

2

1

1

10

Рк

1

2

3

5

53

Qk

0

1

1

2

21

В этой таблице к означает порядок подходящей дроби, qu — элемент порядка к; Рк, Qt — соответственно числитель и знаменатель подходящей дроби порядка к. Во втором вертикальном столбце таблицы числа 1 и О постоянны для любой таблицы; в третьем столбце учтено, что Po=qo hQo=1; вычисление осуществляется по формулам: Pk=Pk-vqk+Pk-2, Qk = Qk-iqk—Qk-2.

Из таблицы следует, что

Р2 _ 5

“ 2 •

Пример 2. Разложить рациональное число -^- в цепную дробь; составить таблицу подходящих дробей; найти подходящую дробь четвертого порядка.

Решение. Процесс аналогичен рассмотренному в предыдущем примере. Последовательно получаем:

17 27

27117 "211” 17 10

101 7~ 7 ”

_7|3

6 2

31 1

0

17

Следовательно, -^у = [0, 1, 1, 1, 2, 3]. Далее следует составить таблицу подходящих дробей, после чего легко найти, что

Л _ 5

Q4 - 8 •

Пример 3. Разложить рациональное числору в цепную дробь; составить таблицу подходящих дробей; найти подходящую дробь третьего порядка.

Решение. Предварительно заметим, что в соответствии с определением конечной цепной дроби лишь ?0 может быть любым целым числом, а остальные qt— целые положительные числа.

Найдем элементы соответствующей цепной дроби:

—371 17

-51|Гз~

171 14- 14 —

141 3— 12 —

3 12~ 2 —

2 I 1

О

37

ОткудаОткудаСледовательно, —ру = [ — 3, 1,4, 1,2].

Откуда

Откуда

к

0

1

2

3

4

4k

—3

1

4

1

2

Рк

1

—3

—2

-11

—13

—37

Qk

0

1

1

5

6

17

Составим таблицу:

Р» _13

Оз “6 1

Пример 4. Решить сравнение

23x^17 (mod 71).

Решение. (23, 71) = 1, поэтому сравнение имеет единственное решение.

Используем аппарат цепных дробей. Для этого разложим в цепную дробь число-^-, получим:

-g—[3. И, 2].

Составим таблицу значений числителя рк подходящих дробей:

qn Pk Ebqn Pk Eb3112

qn Pk Eb

qn Pk Eb

33471

1—11

На основании формулы решения сравнений первой степени с одним неизвестным x=£nPn-i6(mod m), имеем:

№1-34-17(mod 71),

или

x==10(mod 71).

Пример 5. Решить сравнение 115x=85(mod 355).

Решение. Так как (115, 355) =5 и 85 делится на 5, то данное сравнение имеет 5 решений.

Сократим обе части сравнения и модуль на 5:

23x^17 (mod 71).

Полученное сравнение имеет единственное решение:

x=10(mod 71)

(см. предыдущий пример).

Следовательно, данное сравнение имеет следующие решения:

x=10(mod 355), х=81 (mod 355), х= 152 (mod 355), х=223 (mod 355), x=294(mod 355).

При м е р 6. Решить неопределенное уравнение

23х+91у=2.

Решение. Так как

(23, 91) =1,

то уравнение имеет решение в целых числах; учитывая, что 23 — целое положительное число, его можно принять за модуль соответствующего сравнения, в результате чего получим

91y=2(mod 23);

прибавляя к левой части сравнения число —92t/, кратное модулю, приходим к сравнению

—у=2 (mod 23), откуда

у=—2 (mod 23), y = 23t—2;

подставив полученное значение у в данное уравнение, после простейших преобразований находим, что

х=8—91/.

Получили общее решение данного уравнения в виде х=8—91/, y=23t—2.

Замечания 1. Так как второй коэффициент, равный 91, — целое положительное число, то можно исходить из сравнения

23x^2 (mod 91);

последовательно имеем:

23x=184(mod 91),<xs8(mod 91),х=91/+8,

23(91/4-8)+91^=2,у=— 2—23/.

Если дано уравнение

ах+Ьу = с,

где (а, Ь) = 1, 6>0, то, решая сравнение

ax=c(mod 6), получаем

x=x0(mod 6),x=bt-Vxo.

Можно найти значение у по формуле

с - аХп.

У = —^ — at.

И, полагая

с — ах0 „ b’

получаем

У=Уо—at.

Пример 7. Разложить дробь -^- на сумму или разность двух дробей соответственно со знаменателями 7 и 11.

Решение. Из условия получаем: х у 58

откуда 11х+7у = 58; так как (11, 7) = 1, то уравнение имеет решение в целых числах. Замечая, что 7 — целое положительное число, приходим к сравнению

llx=58(mod 7)

и последовательно имеем:

4x=2(mod 7),4x=16(mod 7),x=4(mod 7),х=7/+4;

далее по указанной формуле имеем: 58-11-4 м , У =7ИЛ

откуда

у=2—11/.

Достаточно положить / = 0. Получим

х=4, у = 2 и окончательно

5842

77 = 7 + 11 "

Упражнения

Нижеследующие рациональные числа разложить в непрерывные дроби:

. 83 ,, 121. 163,19,23,41

а) 19 ! б) 27; в) 59; г) 37 ; д) 47 ; е) 5д ,

, 37,. 17,37,19 .,83

ж) 61’ 3)1 57’ И)81’ К^47 ’ Л)17 "

Даны непрерывные дроби:

[2, 1, 3,4, 1, 2],г) [0, 1,2, 4, 5],ж) [2,1,3,4, 1, 2],

[0, 3, 1,2, 7],д) [-2,1,2,2,1,5]з) [3,1,4,2, 5],

[3, 1, 1,6, 8],е) [-1,1, 1, 2, 9],и) [4,1,3,2, 5].

Найти соответственно равные им рациональные числа.

Решить сравнения:

а) 97x^11 (mod 41), б) 41x=7(mod 101), в) 81x=14(mod 202), г) 23x=5(mod 71), д) 92x=20(mod 284), е) 11х=1 (mod 567), ж) 243х=271 (mod 317), з) 37x=25(mod 107), и) 486x=542(mod 634), к) lllx=75(mod 321), л) 101x=17(mod 113), м) 505x=85(mod 565), н) 7x=5(mod 72).

Используя метод сравнения, решить нижеследующие уравнения

а) 37x4-110 = 1,б) 673x4-1030=1,в) 52x4-230=1, г) 253x4-10010= 22,а) 37x4-110 = 1,б) 673x4-1030=1,в) 52x4-230=1, г) 253x4-10010= 22,д) 2977x4-14690=13 е) 1414x4-4060=42, ж) 4997x4-40090 =3д) 2977x4-14690=13 е) 1414x4-4060=42, ж) 4997x4-40090 =3

а) 37x4-110 = 1,

б) 673x4-1030=1,

в) 52x4-230=1, г) 253x4-10010= 22,

а) 37x4-110 = 1,

б) 673x4-1030=1,

в) 52x4-230=1, г) 253x4-10010= 22,

д) 2977x4-14690=13 е) 1414x4-4060=42, ж) 4997x4-40090 =3

д) 2977x4-14690=13 е) 1414x4-4060=42, ж) 4997x4-40090 =3

в целых числах.

Разложить дробь -jy на сумму или разность двух дробей соответственно со знаменателями 3 и 5.

19

Разложить дробь -^- на сумму или разность двух дробей соответственно со знаменателями 3 и 7.

3?

Разложить дробь -^у на сумму или разность двух дробей соответственно со знаменателями 5 и И.

12

Разложить дробь -^- на сумму или разность двух дробей соответственно со знаменателями 5 и 7.

Разложить дробь j||- на сумму или разность двух дробей соответственно со знаменателями 11 и 13.

ЧИСЛОВЫЕ ФУНКЦИИ. ПРОСТЫЕ ЧИСЛА.

Ш. X. Михелович. Теория чисел, стр. 49—50, 52—56, 229—232.

А. А. Бухштаб. Теория чисел, стр. 48—51, 92—95, 315—319, 355—358.

Л. Я- Окунев. Краткий курс теории чисел. М., Учпедгиз, 1956, стр. 89—91.

Вопросы для самопроверки

Дайте определение функции, выражающей целую часть действительного числа а, т. е. [а].

Дайте определение функции B(x; рх. Pi,—, PuY

Сформулируйте основные свойства числовой функции Эйлера.

Дайте определение совершенных чисел и напишите соответствующую формулу.

Дайте определение дружественных чисел и напишите соответствующую формулу.

Напишите формулы для вычисления S(n) и т(п).

Дайте определение чисел «близнецов». Приведите примеры.

Сформулируйте проблему Гольдбаха—Эйлера.

Разберите решения примеров, рассмотренных ниже.

Пример 1. Найти число натуральных чисел в интервале от 1 до 103, делящихся на 7.

Решение. Известно, что среди всех натуральных чисел от 1 до т чисел, делящихся на Ь, будет ["4г] •

Следовательно, в данном случае мы должны вычислить значение функции 1^— , т. е. наити целую часть 103 числа ——.

Ответ. 14.

Пример 2. Найти число натуральных чисел от 120 до 315, делящихся на 11.

Решение. В соответствии с указаниями к решению примера 1 найдем число натуральных чисел от 1 до 315, 11Г 315 I ОО

делящихся на 11, получим [-рр] =28, аналогично для fl 19 1

-у =10, и, следовательно,

число натуральных чисел от 120 до 315, делящихся на 11, будет равно

28—10=18.

Пример 3. Найти количество целых положительных чисел, не превосходящих числа 107 и не делящихся ни на одно из простых чисел 3, 5 и 7.

Решение. Возьмем числовую функцию В(х; рь р2, ..., ph) и применим к рассматриваемому упражнению. Получим:

В(107; 3, 5, 7)=[107]-[-^] - [-^] - [-^] +

-L Г 1®11 -L Г 107 1 -L Г1071Г 107 1 =

1 [ 3-5 J + 13-7 1 + L 5-7 JL 3-5-7 J

=107-35-21-15+7+5+ 3-1=50.

Пример 4. Используя свойства функции [х], разложить на простые множители число 30!.

Решение. Искомое разложение, очевидно, имеет следующий вид:

30!=2а* • За« • 5а». 7а* • 11а= • 13*6 • 17"7 • 19а« • 231» • 29а«.

Итак, решение задачи сводится к нахождению показателей, с которыми входят простые числа от 2 до 30 в разложение 30!.

В число 30! множитель 2 входит с показателем

г 30 1 . г 30 1 . г 30 I . г 30 ] осai=|—1 + [—1 +1—1 + Ы=26-

Множитель 3 входит с показателем

Г 30 1 . Г 30 1 , Г 30 1. .

“2=1—1 + [—1 + № = 14-

Множитель 5— с показателем

Г 30 1 . г зо ] „аз = [—J + [25*1 = 7"

Таким же образом легко показать, что множители 7, 11, 13, 17, 19, 23 и 29 входят соответственно с показателями 4, 2, 2, 1, 1, 1, 1.

Итак, искомое разложение имеет вид:

30!=226-314-57-74-112-132-17-19-23-29.

Пример 5. Найти показатель, с которым число 3 содержится в числе 501 251 • 25! '

Решение. Найдем, с каким показателем входит 3 в произведение 50!:

[21] _|_ [21] + [50 ]— 22-

[ 3 1 + L 9 J + [ 27 J 22’

аналогично находим, с каким показателем входит 3 в произведение 25!:

[21] -1- [21]=10L з 1 1 L э J 1 •

Следовательно, показатель, с которым число 3 содер- 50!

жится в числе 25[ 25, -, равен 22—2-10=2.

„п гт30!

Пример 6. Показать, что fQjTTsT Делится на произведение 17-19-23-29.

Решение. Воспользуемся свойством: я[я| ■ делится на произведение Пр, где р— простое число; и</?^2п.

В предложенном примере п = 15,

Пр = 17-19-23-29.

Следовательно, ^j30^ : 17-19-23-29.

Если не пользоваться свойством в окончательном виде, то предложенное упражнение может быть решено ,30!

следующим образом: -^ 15] можно рассматривать как коэффициент С^ при х15 в разложении

(14-х)30, 30!

и, следовательно, ^ , 15|целое положительное число. Так как

30! : 17-19-23-29, 30!

а (15!, 1749-23-29) =1, то частное от деления 15| ^-- на 17* 19-23-29 является целым числом.

Пример 7. Найти число натуральных чисел, не превышающих 450 и имеющих с 450 наибольшим общим делителем число 15.

Решение. Используем свойство функции Эйлера: если d— делитель числа п, то число натуральных чисел, не .превышающих п и имеющих с п общим наибольшим делителем число d, равно ф .

Так как-^-=-^-=30, то ? (-^-) = ф (30), где ф(30) —число натуральных чисел, не превышающих числа 30 и взаимно простых с 30. Для вычисления ф(30) воспользуемся формулой для вычисления функции Эйлера:

^С")^?-1 -рТх 'P\k~X kPi~^ (Pz~^ -(Рь -1),где Pj* -р^ ■ — •р'1^ — каноническое разложение числа п.Так как 30=2-3-5, то ф (30) = (3—1) (5—1) =8.

Пример 8. Проверить для числа п = 8 справедливость формулы 2ф(й)=п, где суммирование распростра- d/n нено на все положительные делители числа п.

Решение. Выпишем все положительные делители числа 8, а именно:

2, 4, 8.

Применяя соответствующие формулы, находим, что ф(1)=1, ф(2)=1, ф(4)=2, ф(8)=4, следовательно, ф(1)+ф(2)+ф(4)+ф(8) = 1+ 1+2+4=8, т. е. данному числу.

Пример 9.Найти сумму и число делителей числа 600.

Решение. Если каноническое разложение данного числа имеет вид а. а» а.

формуле:®b+11Рк -1Рк— 1 ’формуле:®b+11Рк -1Рк— 1 ’то сумма делителей вычисляется по

формуле:

®b+11

Рк -1

Рк— 1 ’

формуле:

®b+11

Рк -1

Рк— 1 ’

а число делителей т(а) по формуле T(a)=(ai+0 (аг+1) ••• (®а+1)-

Для данного примера имеем:

600=23-3-52.

5(600)== I860,

т(600) = (3 + 1) (1 + 1) (2 + 1) =24.

Пример 10. Найти сумму делителей числа 496, отличных от несобственного делителя данного числа.

Решение. Поступая, как при решении предыдущего примера, имеем:

496=24-31,

5(496) = ^ .-|L^L=992.

Несобственный делитель данного числа равен самому числу, т. е. 496, откуда

3 (496) —496=992—496=496.

Число, удовлетворяющее требованию 5(a)—а=а, называется совершенным. Таким образом, число 496 — совершенное число.

Пример 11. Найти сумму делителей чисел 220 и 284, отличных от несобственных делителей данных чисел.

Решение, а) 220=22»541,

S (220) ==з504,

3(220) —220 = 504—220=284;

б) 284=22-71,

S (284) —284=504—284=220.

Если для двух чисел а и b выполняются условия 3(a)—a=b, S(b)—b=a, то такие числа называются дружественными.

Следовательно, 220 и 284 — дружественные числа.

Пример 12. Найти все делители числа 90.

Решение. Возьмем каноническое разложение некоторого числа

Тогда для суммы делителей этого числа получим формулу:

S(a) = (1+Pi+p2 + ••• + А"1)- (1 +Р2+Р2 +"Ь — +Р^)'(1 "bPh + Pfe + — + Pfe6) •

Воспользуемся этой формулой для решения предложенного примера:

90 = 2- 32-5;

S(90) = (1+2) (1+3+32) <1+5);

перемножая почленно, получим все делители данного числа: 1, 2, 3, 6, 9, 18, 5, 10, 15, 30, 45, 90. Легко проверить, все ли делители найдены, воспользовавшись формулой

т(90) =2-3.2 = 12.

Пример 13. Если обозначить через 5й(/п) сумму k - степеней всех делителей числа

m = р^ . q^ •...• Н ,

то справедлива формула:

(см. А. К. Сушкевич. Теория чисел. Харьков, 1954, стр. 25, упражнение 15). На основании этой формулы вычислить 5^(24).

Решение. Так как

24=23-3,«42-1«2-2 ,

S2(24) = -^р • у-/ =85 -10=850.

Пример 14. Найти л(30).

Решение. На основании определения, числовая функция л(х) означает количество простых чисел, не превосходящих действительного числа х>1.

Воспользуемся приемом, известным под названием решета Эратосфена. Выпишем все натуральные числа от 2 до 30, а именно: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, и, вычеркивая все составные числа (процесс известен из курса элементарной математики), сохраняем в этой по-

следовательности только простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Подсчитав количество чисел в этой последовательности, получим

я (30) =10.

Для решения этого примера можно воспользоваться формулой:

л(х)=В(х; рх, р2 Ph)+k—1,

где рь рг, ..., ри — последовательность простых чисел

3, ..., и рк^х (см. Л. Я. Окунев. Краткий курс теории чисел, стр. 122, задача 13). Известно, что если число, не превышающее числа х, есть составное, то наименьший его простой делитель р^]/х; значит, функция В(хх; рх, Ра, •••, рк) дает количество простых чисел последовательности натуральных чисел от [Ух+1] до [х], увеличенное на 1, т. е. включено число единица; присоединяя число 6, уменьшенное на 1, получим указанную формулу.

Применяя формулу к рассматриваемому примеру, получим:

’ (30)=[ЗОН [4 ] - И -141 + [4] + [4]+

+ [4J-h45]+3-1=1°'

Пример 15. Показать, что существует бесконечное множество простых чисел вида Зп—1.

Решение. Все множество натуральных чисел разобьем на три подмножества с общими членами: Зи, Зи+1, Зи + 2 (или Зи—1); среди чисел первого подмножества имеется лишь одно простое число 3, остальные простые числа входят в последние два подмножества. Допустим, что Р— наибольшее простое число вида Зп—1; напишем число

АГ = 3-2.5-8-1Ы7-...-Р—1,

где в произведение включено число 3 и все простые числа вида Зп—Г, очевидно, число N будет вида Зп—1 и, следовательно, N = 3s—1.

Число N не может быть простым, так как N>P, но оно не может иметь простыми делителями число 3 и чис-

ла вида Зл—1; следовательно, все его простые делители вида Зл+1, откуда ^=3^+l, но равенство

3/+1 =3s—1 невозможно ни при каких целых положительных значениях t и s, так как последнее равенство может быть переписано в виде

3 (s—0=2, где левая часть кратна трем, а 2 не • 3. Полученное противоречие доказывает существование бесконечного множества простых чисел вида Зл—1.

Пример 16. Показать, что из справедливости теоремы о представлении всякого нечетного числа, большего 5, в виде суммы трех простых чисел, доказанной академиком И. М. Виноградовым, вытекает справедливость теоремы о представлении четного числа, начиная с 10, в виде суммы четырех простых чисел.

Решение. На основании данной теоремы имеем:

2л—1 =Pi +Р2+Р3, откуда

2л + 2 = 3+р1 +Р2 + рз-

Пример 17. Показать, что тройки чисел вида

Р, р + 2, р + 4

не могут быть простыми.

Решение. Если р = 2, то р + 2 = 4 — составное число; напишем формулу нечетного числа р = 2б+1, тогда р + 2 = 26+3, р+4 = 26+5, где 6 пробегает все множество натуральных чисел. Это множество может быть разбито на три подмножества с общими членами: 6 = 3л, 6=Зл+1, 6 = Зл+2; если 6=3л, то р+2 = 6л+3 и р + 2? 3; если 6=Зл+1, то р=6л+3 и р ;' 3, наконец, если 6 = Зл + 2, то р + 4 = 6л+9 и (р + 4) • 3.

Замечание. Установлено существование троек простых чисел вида р, р + 2, р + 6 и четверок простых чисел вида р, р + 2, р + 6, р+8.

Упражнения

Найти количество натуральных чисел:

в интервале от 1 до 177, делящихся на 5,

в интервале от 1 до 239, делящихся на 11, в) в интервале от 1 до 241, делящихся на 13,

в интервале от 1 до 307, делящихся на 17, д) в интервале от 1 до 347, делящихся на 19.

Найти количество натуральных чисел: а) в интервале от 141 до 257, делящихся на 5, б) в интервале от 80 до 280, делящихся на 7, в) в интервале от 100 до 367, делящихся на 11, г) в интервале от 200 до 507, делящихся на 13, д) в интервале от 220 до 577, делящихся на 19.

Найти количество натуральных чисел:

не превосходящих числа 1317 и не делящихся ни на одно из простых чисел 2, 3, 5;

не превосходящих числа 1420 и не делящихся ни на одно из простых чисел 2,7, 11;

не превосходящих числа 721 и не делящихся ни на одно из простых чисел 3, 11, 13;

не превосходящих числа 423 и не делящихся ни на одно из простых чисел 2, 3, 5, 7;

не превосходящих числа 347 и не делящихся ни на одно из простых чисел 2, 3, 7, 11;

не превосходящих числа 1215 и не делящихся ни на одно из простых чисел 3, 5, 7, 13.

Найти показатель, с которым:

число 3 входит в произведение 28!,

число 7 входит в произведение 521, в) число 5 входит в произведение 50!, г) число 2 входит в произведение 33!, д) число 11 входит в произведение 120!.

Используя свойства функции [х], разложить на простые множители числа: а) 13!, б) 15!, в) 17!, г) 18!, д) 20!, е) 24!, ж) 27!.

Найти показатель, с которым: XО20!

число 2 сдержится в числе 10, 10; ,

число 3 содержится в числе 201.2'бГ’

чс50!"

число 5 содержится в числе 25!-25Г’

Ч-760!

число 7 содержится в числе оП, ™ , ии! • dUI

X1190!

число 11 содержится в числе 45|.451 .

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

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

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

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

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

Проверить справедливость формулы 2ф(с?) = п, djn

где суммирование распространено на все положительные делители числа п, для чисел:

а) 16, б) 20, в) 21, г) 30, д) 40.

Найти сумму и количество делителей чисел:

а) 300, б) 420, в) 480, г) 560, д) 230, е) 290, ж) 620.

Найти сумму, количество делителей и все делители чисел:

а) 12, б) 16, в) 20, г) 40, д) 60.

Вычислить: а) л(40), б) л(60), в) л(90).

Доказать, что существует бесконечное множество простых чисел вида З/г + 1.

Доказать, что существует бесконечное множество простых чисел вида 4п+1.

Доказать, что существует бесконечное множество простых чисел вида 6п—1.

Доказать, что существует бесконечное множество простых чисел вида 4п—1.

Доказать, что существует бесконечное множество простых чисел вида 6^+1.

ЧАСТЬ 11

ДОПОЛНИТЕЛЬНЫЕ ЗАДАЧИДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

КЛАССЫ ПО ДАННОМУ МОДУЛЮ.СРАВНЕНИЯ И КЛАССЫ

Доказать, что если п^З, то ф(п) —четное число.

Известно, что ф(п)=252, каноническое разложение числа п имеет вид п=р“‘ р^г, где ui>l и «2>Г, найти число «.Ответ: 441.

Каноническое разложение числа п содержит лишь простые числа 3, 5 и 11, ф(п) =3600; найти число п. Ответ: 7425.

Доказать, что если т и п— любые целые положительные числа, то по крайней мере одно из них, либо их сумма, либо их разность, делится на число 3.

Доказать, что если числа а и п взаимно просты, ай—Ьс и а—b делятся на п, то й—с делится на п.

Доказать, что о"1—Ьт, где а">Ь, т — целое положительное число, делится на разность а—Ь.

Указание. Предварительно доказать, что числа а и Ь, где а">Ь, при делении на их разность а—b дают одинаковые остатки.

Доказать, что квадрат простого числа р, уменьшенный на единицу, где р отлично от чисел 2 и 3, делится на на 12.

Доказать, что если р— простое число, то Со\ = (-1)6 (mod^).

Указание. Использовать сравнения вида р—k+i=—(&—i) (mod р).

Доказать, что если число 2т—1, где т — целое положительное число, есть число простое, то и m — простое число.

Доказать, что если р— простое число, то (а+6)р=аР + £р(mod р).

Указание. Воспользоваться формулой бинома Ньютона.

Доказать, что если (а, т) — \, то числа

а, 2а, ..., (т—1)а, та

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

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

Показать, что (7312—1) делится на число 105.

Доказать, что если р— простое число, то произведение 2-3-...- (р—3) (р—2) при делении на число р дает в остатке единицу.

Найти остаток от деления числа З301 на число 1000.

Указание. Представить 1000=8-125 и применить теорему Эйлера о сравнении. Ответ: 3.

Показать, что если (а, 42) = 1, то <z18=l(mod 42).

Указание. Представить 42=7-3-2, рассматривая эти числа, как модули.

СРАВНЕНИЯ С НЕИЗВЕСТНОЙ ВЕЛИЧИНОЙ

Показать, что сравнение (т—l)! + l=0(mod т), где т — составное число, не имеет места.

Доказать, что если р — простое число, то (р—2)! = 1 (mod р).

Доказать, что если р — простое число, р = 1 (mod 4), то сравнение х2г—l(mod р) имеет решение.

Указание. Воспользоваться теоремой Вильсона и сравнениями вида р—&=—^(mod р).

Доказать, что если функция f(x) неприводима по модулю р и степень ее выше первой, то сравнение f (х) = =0(mod р) не имеет решений.

Показать, что если модуль есть нечетное число, то сравнение

ax2 + &x+c=0(mod 2^ + 1)

можно свести к сравнению

z2=/(mod 2Aa+<z).

Исследовать и решить сравнение x2=a(mod 4), если а—нечетное число. Ответ: х=1; 3(mod 4).

Исследовать и решить сравнение x2=a(mod 8), если а — четное число.

Показать, что решением сравнения х2=а(mod р), где р = 4т+3, (а, р) = 1, является х = ±ат^г (mod р).

Указание. Следует рассмотреть сравнение аг x2(mod р), а затем возвести обе части сравнения в степень -^^ = 2m 4-1.

Показать, что решением сравнения x2=#(mod р), где р = 8т + 5, (а, р) =1, является либо x=±am+1 (modp), либо x=±22m+1 (mod р).

Показать, что сравнение x2=l (modp6), где р— простое нечетное число, к — натуральное число, имеет два различных решения.

И. Показать, что среди всех чисел, составляющих полную систему наименьших неотрицательных вычетов по модулю т, сравнимы с полными квадратами не более чем *у + 1 чисел, если т— четное число, и не более —2” чисел., если т — нечетное число.

Доказать, что сумма наименьших положительных квадратичных невычетов по простому модулю р>3 кратна р.

Доказать, что произведение чисел а, Ь, ..., с

дает квадратичный вычет или невычет по простому модулю р в зависимости от четности или нечетности количества вычетов среди сомножителей.

Указание. Воспользоваться равенством: p-i р-1р-1р-1

2 =а 2 • Ь2 -...-с2 .

Для каждого простого числа p=l(mod 4) сравнение х2г—1 (mod р) имеет решение; показать справедливость этого положения.

Доказать невозможность равенства

\ Р ) V р ) ’

где (^—знак символа Лежандра, 9=^i(mod р), где р— простое число, большее 2.

Доказать, что

\ Р ) v Р ) ’ где ) —знак символа Лежандра.

Доказать, что если x2 + at/2=0(mod р), (х, ау) = 1, то число —а является квадратичным вычетом по модулю р.

Показать, что

Г 2_\ _г +1, если р=1 (mod 8), p=7(mod 8),

v р ' [ —1, если p=3(mod 8), p=5(mod 8).

СТЕПЕННЫЕ ВЫЧЕТЫ

Доказать, что если число а принадлежит показателю 6 по простому модулю р и (к, 6) =а, то число ак

О

принадлежит показателю -^— по модулю р.

Зная, что числа 12 и 23 принадлежат соответственно показателям 4 и 7 по модулю 29, найти, какому показателю принадлежит число 15 по модулю 29. Ответ: Показателю 28.

Число а принадлежит показателю б по простому модулю р, где 6<р—1. Даны последовательности:

1, а, а2, ..., а*Л(1)

6, ba, ba2, ..., Ьб?8"1,(2)

где (6, р) = 1 и число b несравнимо по модулю р ни с одним из чисел последовательности (1). Показать, что числа последовательностей являются представителями различных классов по модулю р и взаимно просты с р.

Показать, что если (а, р) = 1, где р— простое число, a2ft=l (mod р) и число а принадлежит показателю 26 по модулю р, то ак=—l(mod р).

Указание. Исследовать сравнение (ак—l)(#h + +1) =0(mod р).

Доказать, что если

a4 =l(mod mi), ааг = l(mod m2),..., аак =l(mod т^, то а^ =1 (mod m), где 0—наименьшее общее кратное чисел а\, а^, ..., аь а число т— наименьшее общее кратное чисел mY, т^..., ти.

Доказать, что если число а — первообразный корень простого модуля р, то а\ где (6, р—1) = 1,также является первообразным корнем по модулю р.

Показать, что если р— простое число вида 46+1 и число а — первообразный корень по модулю р, то число р—а также первообразный корень по модулю р.

Зная, что число 2— первообразный корень по модулю 37, показать, что имеет место сравнение 218=36(mod 37).

Показать, что по модулю 36 не существует первообразных корней.

Доказать, что если числа а и b являются первообразными корнями по простому модулю р>2, то произведение а-b не может быть первообразным корнем по модулю р.

Зная, что число 2 — первообразный корень по модулю 131, решить сравнение x3=16(mod 131). Ответ: x=108(mod 131).

Показать, что

ind 1 +ind 2 + ... + ind(p—2) =0(mod p—1).

Зная, что ind319=4(mod 30), indi73=13(mod 30), где числа 3 и 17 являются первообразными корнями по модулю 31, найти indi719. Ответ: indi719=22 (mod 30).

Взяв таблицу индексов при основании, равном 2, для модуля 13 и зная, что ind62=5(mod 12), составить таблицу индексов, приняв за основание первообразный корень 6.

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

Указание. Использовать равенство а^ =l+pN, где N — целое число и б — показатель, которому принадлежит число а по модулю р.

С помощью таблиц индексов найти класс невычетов четвертой степени по модулю 13. Ответ: 1, 3, 9.

Установить, является число 3 вычетом или невычетом пятой степени по модулю 29.

Указание. Исходить из сравнения x”=6z(mod р), где (а, р) = 1; если (п, р—1) =б и а 8 =1 (mod р), то число а вычет степени п по модулю р. Ответ: вычет.

Пользуясь теорией индексов, вывести критерий Эйлера для квадратичных вычетов.

Указание. В качестве исходного сравнения взять сравнение x2=a(mod р), где (а, р)=1, и проиндексировать это сравнение.

Основываясь на теореме: «Если g— первообразный корень по простому модулю р, то g2k и g2k^x соот-

ветственно являются квадратичным вычетом и квадратичным невычетом по модулю р», показать, что сущест- р—1р—\

вует —2— квадратичных вычетов и — невычетов по модулю р.

Указание. Если g—первообразный корень по модулю р, то в качестве приведенной системы вычетов по модулю р, взять числа

g1, g2, g3,g*-1.

АРИФМЕТИЧЕСКИЕ ПРИЛОЖЕНИЯ ТЕОРИИ СРАВНЕНИЙ

Показать, что разность (а+1) (а+2)...(а+п)—п\ всегда делится на а,

Показать, что если (а, 12) = (6, 12) = 1, то число а96—^96 делится на 144.

Показать, что если (а, 8) = (6, 8) = 1, то число а9—ab8-Va8b—Ь9 делится на 8.

Показать, что если (а, 7) = (6, 7) = 1, то число а8Ь6—а6Ь8—а2 + 62 делится на 7.

Доказать, что сумма данного числа и числа, написанного теми же цифрами, но взятыми в обратном порядке, делится на число 11, если количество цифр данного числа четное.

Доказать, что если к любому трехзначному числу приписать справа такое же число, то полученное число будет делиться на числа 7, 14 и 13.

Написать пятизначные числа, средние цифры которых составляют число 809, делящиеся на 55. Ответ: 18095 и 68090.

Показать, что если число а2а1а0 делится на 27 или 37, то число aiaoa2 делится на 27 или 37.

Указание. Воспользоваться сравнением 100а2+ + 10ai+ao=0(mod 27) и свойствами сравнений.

Доказать, что если (а, Ь) = 1 и из двух чисел 11а+ +26 и 18а+56 одно кратно числу 19, то (11а+26, 18а + + 56) = 19.

Найти число 4415 ху, делящееся на 999. Ответ: 441558.

Найти число 2485xyz, делящееся на 1001. Ответ: 2485483.

Найти число вида \ху7\, делящееся на 33.

Найти число хг/3242, делящееся на 198.

Возьмите многозначное число, в любом порядке переставьте его цифры и из большего отнимите меньшее; в полученной разности зачеркните одну цифру и подсчитайте сумму сохранившихся цифр. Как, зная последнюю, установить, какая цифра зачеркнута? Дайте теоретическое обоснование методу.

НЕПРЕРЫВНЫЕ ДРОБИ

Доказать, что при п^2 справедливо

Qn—2^n Рn—^Qn = ( 1) П£п-

На основании свойств подходящих дробей доказать, что уравнение ах+Ьу=\, где (а, 6) = 1, всегда имеет решение в целых числах.

Указание. Воспользоваться равенством -q— = — и свойством

Qn—1 Рn Pn—xQn^ ( l)n—L

На основании существования решения в целых числах уравнения ах + Ьу=\, где (а, Ь) = 1, доказать, что если (а, 6) = 1, с; а, с • Ь, то с ; ab.

На основании существования решения в целых числах уравнения ах + Ьу=\, где (а, &) = 1, доказать, что если (а, с) = 1, (6, с) = 1, то (ab, с) = 1.

Сумма произведений двух целых чисел соответственно на 7 и на 3 равна 41; найти эти числа.

На основании существования решения в целых числах уравнения ах—Ьу=\, где (а, Ь) = 1, показать, что в окружность посредством циркуля и линейки можно вписать правильный двенадцатиугольник.

ЧИСЛОВЫЕ ФУНКЦИИ. ПРОСТЫЕ ЧИСЛА

Среди чисел от 1 до п найти количество чисел, которые делятся на р\ но не делятся на ph+1, где р— простое число и р<п. Ответ:•

L J L ‘ j

Среди чисел от 1 до 41 найти количество чисел, делящихся на 2, но не делящихся на 23.

Указание. Применить функцию [х]. О т в е tj 15.

Найти показатель, с которым число 12 входит в произведение 37!.

Найти показатель, с которым число 24 входит в произведение 50!. Ответ: 12.

Представить произведение всех натуральных чисел от 21 до 40 в виде произведения простых чисел.

Найти, при каком целом положительном значении х уравнение [2,5х]=100 имеет решение. Ответ: х=40.

Доказать, что если п^З, то ф(п) —четное число.

На основании свойств числовой функции Эйлера доказать, что в последовательности натуральных чисел существует бесконечное множество простых чисел.

Указание. Допустив, что р& — наибольшее простое число, воспользоваться равенством п = рх-р2^.гр^

Дано: а) ф(п) =48; п = 2а • 3? • 5? • 7^ ; б) ф(/г) = = 320; 11 = ^ • З3 • 5? . Найти п. Ответ: а) 210, б) 1200.

Проверить справедливость равенства ф(240) = = Ф(16О).

Найти условия, при которых ф(3х)=ф(2х), где х— натуральное число.

Показать невозможность равенства ф(2х)=ф(5х), где х — натуральное число.

Найти т(я3), если т(а) = (а1 + 1)(а2+1)...(ал+1).

Найти т(а3), если a=pi рХ, т(а2) = 15, где р\ и р2— простые числа. Ответ: 28.

Найти количество делителей числа п3, если п= — PV Р°2 Р^ и числ0 я2 имеет 105 различных делителей. Ответ: 280.

Найти наименьшее натуральное число, имеющее восемь положительных делителей. Ответ: 24.

Найти наименьшее натуральное число, имеющее двенадцать положительных делителей. Ответ: 60.

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

S= ^Р\р2-Рк> + (?1?2...?з),

где в правую часть равенства включены все простые числа от 2 до р.

Доказать, что всякое число вида 36—1 либо простое, либо содержит нечетное число простых делителей этого вида.

Указание. Учесть, что все множество простых чисел представимо совокупностями арифметических прогрессий с общими членами Зп, З/г+1, Зп—1.

Доказать, что каждое натуральное число вида 46 + 3 имеет по крайней мере один простой делитель того же вида.

Зная, что существует бесконечное множество простых чисел вида Зп+1, доказать существование бесконечного множества простых чисел вида 66+1.

Указание. Положить п = 26 и п = 26 +1.

Василий Александрович Александров|,

Святослав Михайлович Горшенин

ЗАДАЧ Н И К-П РАКТ И КУМПО ТЕОРИИ ЧИСЕЛ

Редактор Л. М. КотоваТехнический редактор Л. Я. МедведевКорректор Н. М. Данковцева

Сдано в набор 3/XI—1971 г. Подписано к печати 12/IV 1972 г. 84X108V32 Бумага типэгр. № 3. Печ. л. 2,5 Услов. л. 4,2. уч.изд. л. 3,63 Тираж 30 тыс. экз. (Пл.

1972 г.) А07191

Издательство «Просвещение» Комитетапо печати при Совете Министров РСФСР.

Москва, 3-й пр. Марьиной рощи, 41.

Типография № 2 Росглавполиграфпрома,г. Рыбинск, ул. Чкалова, 8. Заказ 3429.Цена 10 коп.

ГЛАВНОЕ УПРАВЛЕНИЕ ВЫСШИХ И СРЕДНИХ ПЕДАГОГИЧЕСКИХ УЧЕБНЫХ ЗАВЕДЕНИИ МИНИСТЕРСТВА ПРОСВЕЩЕНИЯ РС6СР

московскийГОСУДАРСТВЕННЫЙЗАОЧНЫЙПЕДАГОГИЧЕСКИМИНСТИТУТмосковскийГОСУДАРСТВЕННЫЙЗАОЧНЫЙПЕДАГОГИЧЕСКИМИНСТИТУТВ. А. АЛЕКСАНДРОВ С. М. ГОРШЕНИНВ. А. АЛЕКСАНДРОВ С. М. ГОРШЕНИН

московскийГОСУДАРСТВЕННЫЙЗАОЧНЫЙПЕДАГОГИЧЕСКИМИНСТИТУТ

московскийГОСУДАРСТВЕННЫЙЗАОЧНЫЙПЕДАГОГИЧЕСКИМИНСТИТУТ

В. А. АЛЕКСАНДРОВ С. М. ГОРШЕНИН

В. А. АЛЕКСАНДРОВ С. М. ГОРШЕНИН

ЗАДАЧНИК-ПРАКТИКУМ ПО ТЕОРИИ ЧИСЕЛ

ПРОСВЕЩЕНИЕ

1972

ГЛАВНОЕ УПРАВЛЕНИЕ ВЫСШИХ И СРЕДНИХ ПЕДАГОГИЧЕСКИХУЧЕБНЫХ ЗАВЕДЕНИЙ МИНИСТЕРСТВА ПРОСВЕЩЕНИЯ РСФСР

Московский государственный заочный педагогический институт

В. А. АЛЕКСАНДРОВ и С. М. ГОРШЕНИН

ЗАДАЧНИК-ПРАКТИКУМ

ПО ТЕОРИИ ЧИСЕЛ

Для студентов заочных отделенийфизико-математических факультетовпедагогических институтов

ИЗДАНИЕ ТРЕТЬЕ, ПЕРЕРАБОТАННОЕ

ИЗДАТЕЛЬСТВО «ПРОСВЕЩЕНИЕ»Москва — 19 72

Одобрено кафедрой математики Московского государственногозаочного педагогического института

Редактор О. А. Павлович

СОДЕРЖАНИЕ

Предисловие к третьему изданию3

Введение 4

Часть I

Задачи с решениями. Задачи для самостоятельного решения

Классы по данному модулю. Сравнения и классы . . . .6

Сравнения с неизвестной величиной15

Степенные вычеты36

Арифметические приложения теории сравнений47

Непрерывные дроби55

Числовые функции. Простые числа62

Часть II

Дополнительные задачи для самостоятельного решения

Классы по данному модулю. Сравнения и классы . . . 72

Сравнения с неизвестной величиной73

Степенные вычеты75

Арифметические приложения теории сравнений77

Непрерывные дроби78

Числовые функции. Простые числа^*