Integers II - 8 Feb 2011
Sergey Sobolev
Это задание -- продолжение задания "Целые числа I" прошлого
учебного года. На нашем сайте
http://www.csmath.org
на странице задания есть pdf-файл для печати и вскоре в Google
Docs задание будет разложено по папкам учеников.
Из задания "Целые числа I" сделайте то, что не получилось в
прошлом году, и сдайте на проверку. Под рукой должны быть
статьи и книжки, указанные в прошлом году. Основное чтение --
статья
Вагутен В.Н. Алгоритм Евклида и основная теорема арифметики
-- Квант, 1972, N 6
Целью является разобраться с алгоритмом Евклида, он даёт не
только наибольший общий делитель d двух целых чисел a и b, но и
два целых числа x и y для представления d = ax + by.
В следующем задании появится определение простого числа и будет
доказано его основное свойство:
если простое число p делит произведение mn,
то p делит m или p делит n.
После этого будет доказана теорема о существовании и
единственности разложения натурального числа на простые
множители.
---------------------------------------------------------------
Признаки делимости
1. Докажите, что натуральное число при делении на 4 даёт тот же
остаток, что и число, образованное его последними двумя
цифрами.
Подсказка: числа a и b дают одинаковые остатки при делении на m
означает, что разность a-b делится на m.
2. Докажите, что натуральное число при делении на 9 даёт тот же
остаток, что и сумма его цифр.
3. Найдите и докажите признаки делимости на 7 и на 11.
Алгоритм Евклида
1. Найдите, сколько целых точек лежит на отрезке, соединяющем
точки
(а) (0,0) и (28,20);
(б) (0,20) и (28,0);
(в) (-7,15) и (21,-5).
Концы отрезка ему принадлежат.
2. От прямоугольника 324x141 отрезают несколько квадратов со
стороной 141, пока не останется прямоугольник, у которого одна
сторона меньше 141. От полученного прямоугольника снова
отрезают квадраты, стороны которых равны его меньшей стороне,
до тех пор, пока это возможно, и так далее. На какие квадраты
будет разрезан прямоугольник? Укажите количество квадратов
каждого размера.
Определение. Число d называется наибольшим общим делителем
целых чисел a и b, если
(1) d|a, d|b;
(2) d'|a, d'|b ==> d'|d.
(то есть если d делит a и b и всякое другое число, делящее a и
b, делит d).
Примеры. Числа 4 и 6 имеют наибольшие общие делители 2 и -2.
Числа 0 и 0 не имеют наибольшего общего делителя. (Почему?)
Если d_1 и d_2 -- наибольшие общие делители чисел a и b, то
d_1=d_2 или d_1=-d_2 (докажите), поэтому можно условиться, что
наибольший общий делитель положителен.
Обозначение: d=НОД(a,b) или d=GCD(a,b) (от слов Greatest Common
Divisor).
3. Докажите, что НОД(a,b)=НОД(a-b,b) для любых целых чисел a и
b (используйте определение).
4. Найдите с помощью алгоритма Евклида d=НОД(187,136) и его
представление в виде d=187x+136y, где x и y -- некоторые целые
числа.
5. Для a=572, b=121 представьте d=НОД(a,b) в виде d=ax+by, где
x и y -- целые.
6. Найдите НОД(20328,23562) с помощью алгоритма Евклида.
7. Найдите наибольший общий делитель чисел 1111111111 и 111111.
Что изменится, если это запись в двоичной системе счисления?
8. Пусть a и b -- целые числа, причем a\ne 0 или b \ne 0.
Докажите, что наименьшее положительное число вида ax+by, где x
и y целые, есть НОД(a,b).
---------------------------------------------------------------
С.Соболев