МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Руководитель Дмитрий Владимирович Трущин
2014/2015 учебный год

Занятие 16 (7 марта 2015 года). Алгоритм Евклида.

1.
Докажите, что если a > b, то НОД(a, b) = НОД(a − b,b).
2.
Найдите НОД(2015, 1001).
3.
Последовательность чисел Фибоначчи задана по следующему правилу: F1 = F2 = 1, а все последующие числа определяютсяпо правилу Fn = Fn − 1 + Fn − 2. (Начало бесконечной последовательности Фибоначчи выглядит так: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, и т.д.) Найдите НОД(F2015, F2014).
4.
Докажите, что если a при делении на b дает остаток r, то НОД(a,b) = НОД(r, b).
5.
Найдите НОД(747474, 111).
6.
Найдите НОД\((\underbrace{11\ldots11}_{51}, \underbrace{11\ldots11}_{81})\).
7.
На прямой сидит блоха, и прыгает всякий раз либо на 15 сантиметров вправо, либо на 21 сантиметр влево. В каких точках прямой может побывать эта блоха?
Определение. Даны натуральные числа a и b. Назовем число m линейно представимым через a и b, если существуют целые числа x и y, такие, что m = ax + by.
8.
Докажите, что
a)
если m1 и m2 линейно представимы через a и b, то m1 + m2 и m1 − m2 также линейно представимы через a и b;
б)
если m линейно представимо через a и b, то km линейно представимо через a и b для любого целого k;
в)
НОД(a, b) линейно представим через a и b;
г)
число m линейно представимо через a и b тогда и только тогда, когда оно делится на НОД(a, b).
9.
НОД(a, b) = d. Докажите, что НОД(2a − 1, 2b − 1) = 2d − 1.
10.
Найдите НОД(235 + 1, 2100 + 1).
Определение. Если НОД(a, b) = 1, то числа a и b называются взаимно простыми.
11.
В государстве имеют хождение монеты достоинством a и b золотых, где a и b — взаимно простые натуральные числа. Докажите, что
а)
покупатель может заплатить в магазине любую сумму в целое число золотых (возможно, получив сдачу), при условии, что и у покупателя, и у продавца имеется достаточно большой запас монет каждого достоинства.
б)
такими монетами можно набрать (без сдачи) любую сумму, начиная с 2ab золотых.
в)
найдите наибольшее число золотых, которое нельзя набрать такими монетами.
12.
Пусть a и b — взаимно простые натуральные числа. В доме есть лифт с двумя кнопками, одна из которых поднимает лифт на a этажей вверх, а вторая опускает на b этажей вниз, если это возможно (например, на последнем этаже первая кнопка не работает). Докажите, что на этом лифте можно попасть с любого этажа на любой другой, если высота дома не меньше а) 2ab; б) a + b.