Задачи на алгоритм Евклида

 2016-11-03 07:00:00      

Назад ко всем статьям

1. Каков наибольший возможный общий делитель чисел 9m + 7n и 3m + 2n, если числа m и n не имеют общих делителей, кроме единицы?

2. Фома и Ерёма нашли на дороге по пачке 11-рублевок. В чайной Фома выпил 3 стакана чая, съел 4 калача и 5 бубликов. Ерёма выпил 9 стаканов чая, съел 1 калач и 4 бублика. Стакан чая, калач и бублик стоят по целому числу рублей. Оказалось, что Фома может расплатиться 11-рублевками без сдачи. Покажите, что это может сделать и Ерёма.

3. Докажите, что дробь (12n+1)/(30n+2) - несократима ни при каком натуральном n.

4. Найдите НОД(2^100 - 1, 2^120 - 1).

5. Найдите НОД(111...111, 11...11) - в записи первого числа 100 единиц, в записи второго - 60.

6. Докажите, что в последовательности чисел Фибоначчи при m >= 2 встречается не менее 4 и не более 5 m-значных чисел.