Таблицы Брадиса

Целые числа 4. Практические задачи

Целые числа 4. Практические задачи

Элементы математики в задачах - Г. А. Мерзон

Задача 13* (китайская теорема об остатках). Пусть числа ах, а2, ..., ап попарно взаимно просты. Тогда для любых b1, b2, ..., Ьп найдется х такое, что

х = bi (mod аі), i = 1,..., п,

причем любые два числа, удовлетворяющие этому условию, сравни­мы по модулю ах...ап.

Задача 14*. Найдите все решения системы сравнений

х = 3 (mod 5) х = 1 (mod 7) х = 4 (mod 9).

Задача 15. Пусть p — простое число. Докажите, что:

а)  Cfc. p при 0 < k < p;

б)  (а + b)p = аp + bp (mod p);

в)   (малая теорема Ферма) ар — а]р.

Задача 16* (теорема Вильсона). Пусть р—простое число, тогда (p — 1)! = — 1 (mod p).

Задача 17. Какими правильными многоугольниками можно замо­стить плоскость?

Задача 18. Докажите, что имеется бесконечное количество простых чисел вида: а) 4п + 3; б*) 4п + 1; в**) ап + b, где НОД(а, b) = 1.

Задача 19*. Найдите количество решений сравнения х2 = 1 (mod п):

а)  при простом п; б) при произвольном п.

Целые числа 4. Практические задачи

листок її / март 2005

Задача 1. Верно ли, что для любого п > 1 выполняется:

а) п3 + 5п: 6; б) 2п3 + 3п2 + 7п і 6; в) п5 — п. 30; г) 22п — 1 і 6;

д)  116п+3 +1. 148?

Задача 2. Дайте определение: а) НОД; б) НОК чисел а1, а2, ..., ап (п > 2).

Определение 1. Наибольшим общим делителем чисел а1, а2..., ап на­зывается наибольшее из таких чисел d, что а1. d, а2. d, ..., ап . d.

Определение 2. Наименьшим общим кратным чисел а1, а2,..., ап называется наименьшее из таких положительных чисел d, что d. аъ

d. a2, •••, d. ап'

Задача 3. Докажите, что для любых а, Ь и с, таких что а ■ Ь ■ с = 0:

а)  НОД(а, Ь, с) = НОД(а, НОД(Ь, с)) = НОД(НОД(а, Ь), с);

б)  НОК(а, Ь,с) = : ИФнод(аЛс)

НОД(а, Ь) ■ НОД(Ь, с) ■ НОД(а, с)

Задача 4. Существует ли число, которое при делении на числа 2, 3,

4, 5 и 6 дает в остатке соответственно: