Задачи на делимость

[lega4]

Посоветуйте книжку с разбором задач на делимость плз. Почитал форум, например здесь topic27390.html - вообще не понял, как заюзали китайскую теорему об остатках. С чего можно начать?

Задача для примера - Докажите, что из любых десяти целых чисел можно выбрать два числа, разность кубов которых делится на 27.
$(a^3-b^3)\vdots 27$

[Someone]

Рассмотрите остатки от деления данных чисел на $9$.

[mitia87]

Или просто выберите 2 числа с одинаковыми остатками при делении на $9$ и распишите разность кубов.

[lega4]

mitia87 спс, опыта в таких задачах вообще нет, вот и не знаю((((
Расписал a и b как 9n+y и 9m+y, где y - остаток и все сошлось - 9 вынеслась за скобку из "разности этих чисел", а тройка - из "неполного квадрата суммы".

А если такая же задача, но надо выбрать из 8 чисел? Там не факт что с одинаковыми остатками попадутся числа... Попробовал представить остатки отрицательными, тогда a=9n+y а b=9m-y, но за скобки тройки тогда не выносятся((((

[ИСН]

Какие остатки от деления на 27 могут давать сами кубы?

[mitia87]

А главное, сколько различных остатков.

[lega4]

ИСН 0, 1, 8, 10, 17, 19, 26 - 7 остатков. Так, погодите, ща подумаю

[mitia87]

так как различных остатков 7, то из 8 выбранных чисел наверняка найдутся ...

[maxmatem]

посмотрите книгу Воробьёв "Теория Делимости"

[lega4]

mitia87 да-да-да, говорю же - пишу Получается, что они (Разность кубов) будут делится даже не на 27, а на 81 Спасибо!

Еще вопрос - как это можно увидеть? Что вот здесь рассматриваем остатки от 9, а здесь - от 27? Как найти что-то такое, за что можно зацепиться (Часто похожие задачи на олимпиадах, вот как во время них суметь понять фишку задачи?)?


maxmatem а можете ссылку дать на книжку? И\или инициалы этого Воробьева. А то погуглил - чет ничего не нашлось, кажется...

[mitia87]

Если вы об олимпиадных задачах, то совет такой: если в условии ни о каких числах не говорится, такие числа редко больше, скажем, 20. А если говорится, то надо выбирать из делителей. Так что перебор и устный счет:
если $a \equiv p (\mod b) \Rightarrow a^m \equiv p^m(\mod b). $

А про 81, почему-то, не понял.

[ИСН]

Да как. Никак. Идти и дёргать за все дверные ручки подряд - а вдруг тут не заперто?

[maxmatem]

это серия популярные лекции по математике, скачать можно на сайте math.ru

[lega4]

Цитата:

А про 81, почему-то, не понял.

Ой, блин, точно. Я же кубы рассматривал, а не числа. Получается $a^3-b^3=27n-27k=27(n-k)$.
Да только 27, не 81