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

Кружок 9-11 классов

Теория чисел — Алгоритм Евклида 2

1.

Найти наибольший общий делитель чисел а) 2n + 13 и n + 7; б) 2¹⁰⁰ − 1 и 2¹²⁰ − 1.

2.

При каких целых n сократимы дроби а) \(\dfrac{n^2+2n+4}{n^2+n+3}\); б) \(\dfrac{n^3-n^2-3n}{n^2-n+3}\); в) \(\dfrac{n^4+1}{n^2+n+1}\); г) \(\dfrac{n^3+n+1}{n^2-n+1}\).

3.

Обозначим через F_n n-ое число Фибоначчи, т.е. F₁ = 1, F₂ = 1, а для каждого n ≥ 3 число F_n вычисляется по формуле F_n = F_{n − 1} + F_{n − 2}. Докажите, что (F_n , F_{n − 1}) = 1.

4.

Может ли наибольший общий делитель двух натуральных чисел быть больше их разности?

5.

При каком наименьшем натуральном n каждая из дробей несократима: \(\dfrac{2}{n+3}\), \(\dfrac{3}{n+4}\), ..., \(\dfrac{32}{n+33}\)?

6.

Наибольший общий делитель a и b равен 11. Найдите наибольший общий делитель чисел 85a + 51b и 221a + 136b.

7.

По окружности радиуса R катится колесо радиуса r (R, r — натуральные числа). В колесо вбит гвоздь, который, ударяясь об окружность, оставляет на ней отметки. Сколько всего таких отметок оставит гвоздь? Сколько раз колесо прокатится по окружности, прежде чем гвоздь попадет в уже отмеченную точку?

8.

Если числа a и b взаимно-просты (НОД(a,b) = 1), то для некоторых чисел x и y верно равенство: ax + by = 1. Докажите это утверждение.

9.

Руководство Малого Механико-Математического факультета выпустило в обращение купюры достоинством 65 и 999 мммфников.

a)

Докажите, что этими купюрами можно заплатить любую сумму денег (возможно, со сдачей).

б)

Докажите, что любую сумму большую 1000000 мммфников можно заплатить этими купюрами без сдачи.

10.

В прямоугольнике с целыми сторонами m и n, нарисованном на клетчатой бумаге, проведена диагональ. Через какое число узлов она проходит? На сколько частей эта диагональ делится линиями сетки?

11.

Существует ли в сутках момент, когда часовая, минутная и секундная стрелки правильно идущих часов образуют попарно углы 120 градусов?