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

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

Теория чисел: остатки

1.

Докажите, что среди любых 5 целых чисел найдутся два, разность которых делится на 4.

2.

Найдите наименьшее число, дающее следующие остатки: 1 — при делении на 2, 2 — при делении на 3, 3 — при делении на 4, 4 — при делении на 5, 5 — при делении на 6.

3.

Найдите все числа, при делении которых на 7 в частном получится то же число, что и в остатке.

4.

Изменятся ли частное и остаток, если делимое и делитель увеличить в три раза?

5.

Найдите остаток от деления 99993 + 90995 на 9.

6.

В Галактике 7³⁴³⁵ планет. 8 могущественных держав решили поделить поровну все планеты. Если им это не удастся, то Галактику ждёт война. Сколько ещё планет им надо открыть, чтобы избежать войны?

7.

Известно, что сумма нескольких натуральных чисел делится на 6. Докажите. что сумма кубов этих чисел тоже делится на 6.

8.

Шестизначное число делится на 7. Докажите, что если последнюю его цифру переставить в начало, то полученное число тоже будет делиться на 7.

9.

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

10.

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

11.

Докажите, что 5ⁿ + 1 не делится на 5^m − 1 ни при каких натуральных n и m.