Integers III - 29 Mar 2011
Sergey Sobolev
Основное чтение -- статья
Вагутен В.Н. Алгоритм Евклида и основная теорема арифметики
-- Квант, 1972, N 6 (есть перевод в Quantum),
дополненная соответствующим материалом из книги Куранта и
Роббинса "Что такое математика" (анг. или рус. изд.).
Стоит разобраться с цепочкой заключений:
(1) алгоритм Евклида даёт представление НОД(a,b) в виде ax+by;
(2) если простое число делит произведение, то оно делит
какой-то из множителей;
(3) разложение на простые множители единственно.
На сайте http://www.csmath.org есть pdf-файл этого задания с
разбором (1) и (2). Это один из вариантов изложения. Затем
можно прочитать про (3), например, по книге А.Шеня "Простые
числа" (она вся стоит внимания).
---------------------------------------------------------------
Задачи
1. Отметьте на числовой оси красным цветом целые числа, которые
при делении на 4 дают остаток 1, а синим цветом -- числа,
которые при делении на 6 дают остаток 3. Как так же описать
числа, удовлетворяющие обоим этим условиям?
2. Двум мастерам приказали просверлить в рейке длиной 3 метра
отверстия на равных расстояниях друг от друга и от концов
рейки: одному мастеру -- на расстоянии 20 см, другому -- 12 см.
Сколько всего отверстий будет проделано в рейке?
3. При каких натуральных n сократима дробь (3n+2)/(5n-2) ?
4. При каких натуральных n будут взаимно просты числа
а) n^2+1 и n+1;
б) n^2+1 и 2n+1 ?
5. Найдите все решения в целых числах уравнения 15x-9y=6.
6. Имеются контейнеры весом 130 кг и 160 кг. Нужно полностью
загрузить ими грузовик грузоподъемностью 3 тонны. Как это можно
сделать? Укажите все решения.
7. Сколькими способами сумму в 1000 тугриков можно набрать
бумажками в 3 и 5 тугриков?
8. Какие суммы можно набрать бумажками в 3 и 10 тугриков?
9. Остап Бендер в городе Фуксе организовал раздачу слонов
населению. На раздачу явилось 28 членов профсоюза и 37 не
членов, причем Остап раздавал слонов поровну всем членам
профсоюза и поровну -- не членам. Оказалось, что существует
лишь один способ такой раздачи (так, чтобы раздать всех
слонов). Какое наибольшее число слонов могло быть у О.Бендера?
10. Сколько решений в положительных целых числах имеет
уравнение ax+by=ab (a и b целые положительные)?
---------------------------------------------------------------
С.Соболев