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

Целые числа 2. Алгоритм Евклида

Целые числа 2. Алгоритм Евклида

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

Задача 12. а) Найдите все простые p такие, что p + 2 и p + 4 также простые.

б**) Докажите, что существует бесконечно много таких простых чисел р, что число p + 2 также простое.

Задача 13 (решето Эратосфена). На доске написаны все числа от 2 до 1000. Эратосфен обводит число 2 в кружочек и стирает все числа, отличные от 2, которые делятся на 2. Затем он повторяет этот процесс, а именно обводит в кружочек наименьшее необведенное число и стирает все остальные числа, которые делятся на это число. Процесс заканчивается, когда на доске остаются только обведенные числа. Какие числа останутся на доске? (Их не нужно выписывать.)

Задача 14. Выпишите все простые числа, меньшие 100.

Задача 15. Докажите, что число а — составное, если и только если а делится на какое-нибудь простое число, не превосходящее л/а.

Задача 16. Докажите, что:

а)  любое целое число, большее 1, можно представить в виде про­изведения простых чисел;

б)  каждое целое число x, большее 1, можно представить в виде

а і а2 а

x=pi1 p2 - pа,

где p1 < p2 < — < pn — простые числа, а1, а2,..., аи — положительные целые числа;

в*) (Основная теорема арифметики) если число x представлено двумя способами в таком виде, а точнее

а-i а2 а               b b2 b

x = pi1 p2 - pn = qi -qmm,

то эти разложения совпадают, то есть m = n и при любом 1 ^ i ^ n pi = 4i, аі = bi;

г)  если в этом разложении все аі четны, то x есть точный квадрат, <-> 2 то есть найдется такое целое у, что x = у .

Задача 17. Разложите на простые множители числа 1024, 57, 84, 91, 391, 101, 1000, 1001, 1543.

Целые числа 2. Алгоритм Евклида

листок 8 / декабрь 2004

Соглашение. Все числа в этом листке предполагаются целыми.

Задача 1. Докажите, что для любых а и b = 0 существуют и единствен­ны q и r такие, что: 1) а = qb + r; 2) 0 ^ r < |b|.