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

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

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

1.

Докажите, что если a > b, то НОД(a, b) = НОД(a − b,b).

2.

Найдите НОД(2015, 1001).

3.

Последовательность чисел Фибоначчи задана по следующему правилу: F₁ = F₂ = 1, а все последующие числа определяютсяпо правилу F_n = F_{n − 1} + F_{n − 2}. (Начало бесконечной последовательности Фибоначчи выглядит так: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, и т.д.) Найдите НОД(F₂₀₁₅, F₂₀₁₄).

4.

Докажите, что если a при делении на b дает остаток r, то НОД(a,b) = НОД(r, b).

5.

Найдите НОД(747474, 111).

6.

Найдите НОД\((\underbrace{11\ldots11}_{51}, \underbrace{11\ldots11}_{81})\).

7.

На прямой сидит блоха, и прыгает всякий раз либо на 15 сантиметров вправо, либо на 21 сантиметр влево. В каких точках прямой может побывать эта блоха?

8.

Докажите, что

a)

если m₁ и m₂ линейно представимы через a и b, то m₁ + m₂ и m₁ − m₂ также линейно представимы через a и b;

б)

если m линейно представимо через a и b, то km линейно представимо через a и b для любого целого k;

в)

НОД(a, b) линейно представим через a и b;

г)

число m линейно представимо через a и b тогда и только тогда, когда оно делится на НОД(a, b).

9.

НОД(a, b) = d. Докажите, что НОД(2^a − 1, 2^b − 1) = 2^d − 1.

10.

Найдите НОД(2³⁵ + 1, 2¹⁰⁰ + 1).

11.

В государстве имеют хождение монеты достоинством a и b золотых, где a и b — взаимно простые натуральные числа. Докажите, что

а)

покупатель может заплатить в магазине любую сумму в целое число золотых (возможно, получив сдачу), при условии, что и у покупателя, и у продавца имеется достаточно большой запас монет каждого достоинства.

б)

такими монетами можно набрать (без сдачи) любую сумму, начиная с 2ab золотых.

в)

найдите наибольшее число золотых, которое нельзя набрать такими монетами.

12.

Пусть a и b — взаимно простые натуральные числа. В доме есть лифт с двумя кнопками, одна из которых поднимает лифт на a этажей вверх, а вторая опускает на b этажей вниз, если это возможно (например, на последнем этаже первая кнопка не работает). Докажите, что на этом лифте можно попасть с любого этажа на любой другой, если высота дома не меньше а) 2ab; б) a + b.