Снова делимость

[xjar1]

Приветствую, в сборнике задач "Элементы математики в задачах" наткнулся на следующую задачу:
Если $a+b+c$ делится на 30, то и $a^5+b^5+c^5$ делится на 30.

У меня есть 2 решения этой задачи, но вероятно они не совпадают с решением автора, т.к. первое решение производится в лоб, и совершенно не олимпиадное, а второе решение использует технику остатков, что вводится в его книге несколько параграфов позднее.

Какой лучший путь решения данной задачи?

Мои попытки:
1. Краткая схема доказательства:

$30 \mid a^5+b^5+c^5 \Leftrightarrow 30 \mid c(c^4-a^4+a^3 b-a^2 b^2 +a b^3 - b^4) \Leftrightarrow 6 \mid c(a^3 b+a^2 b^2+a b^3) \Leftrightarrow 6 \mid a b c (a^2+a b +b^2) \Leftrightarrow 3 \mid a b c (a^2+a b +b^2) \Leftrightarrow 3 \mid a b c (a-b)^2 \Leftrightarrow 3 \mid a b (a^3-a^2 b -a b^2+b^3) $.
На последнем этапе сделана замена $c=30n-a-b$, и выражение сведено к тому, что в нем перед членами с $n$ будет множитель, делящийся на 3, значит мы можем из забыть.

Далее делаем замену $b=a+n$ и снова переобозначим на $a$ и $b$:
$3 \mid a b^2 (2a^2+b^2) \Leftrightarrow 3 \mid a b^2 (b^2-a^2)$
Последнее доказывается тем, что при подстановке вместо $a$ и $b$ чисел вида $3n+k$ мы всегда получим общий множитель 3 в произведении, после упрощения.

2. $x^5=x (\mod 30)$, откуда можно получить требуемое.
Но как получить это равенство на бумажке без калькуляторов и банальных пересчетов? Неужели требуется проверять все числа вплоть до 29? Я напомню, что в данной книге теорема Ферма к данному параграфу предполагается неизвестной.

P.S. Есть ли какие-либо обобщения данной задачи, например на число слагаемых, или степень?

Спасибо

[mihiv]

Можно попробовать проверить по отдельности делимость на 2,3 и 5.

[Cash]

$x^5-x = (x-1)x(x+1)(x^2+1)$

[wrest]

xjar1 в сообщении #1301382 писал(а):

P.S. Есть ли какие-либо обобщения данной задачи, например на число слагаемых, или степень?

Эксель говорит, что вместо $30$ в задачу можно подставить любое число, являющееся произведением множителей $2,3,5$ в степени не выше $1$, т.е. числа $2,3,5,6,10,15,30$

[wrest]

Я бы решал так.
Положим $a+b+c=k$ тогда $a=k-(b+c)$
После подстановки этого в сумму пятых степеней получаем $(k-(b+c))^5+b^5+c^5$
Приравниваем $k=0$ (для того чтобы из суммы сразу удалить слагаемые, которые заведомо делятся на $k$), раскрываем скобки, приводим подобные члены и получаем (попутно для удобства домножаем все слагаемые на минус единицу)
$5(b^4c+2b^3c^2+2b^2c^3+bc^4)$ (1)
Все выражение (1) делится на $5$, докажем что скобка делится на $6$. То что скобка делится на $2$ - очевидно (слагаемые $b^4c$ и $bc^4$ обязательно одной четности, тогда их сумма четная).
Осталось доказать, что скобка делится на $3$.

[EUgeneUS]

wrest
можно переписать так:

$5(b^4c+2b^3c^2+2b^2c^3+bc^4) = 5bc(b+c)((b-c)^2 + 3bc)$
Тогда видно, что для любых целых $c$, $b$ эта штука делится на три. Просто перебором всех вариантов.

UPD: исправил опечатку

[wrest]

EUgeneUS в сообщении #1301454 писал(а):

$5(b^4c+2b^3c^2+2b^2c^3+bc^4) = 5bc(b+c)((b-c)^2 + 3bc)$
Тогда видно, что для любых целых $a$, $b$ эта штука делится на три.

Ну из того что вы написали видно только то, что последнее слагаемое в последней скобке делится на 3 :)

[EUgeneUS]

wrest

1. Если $c$ и-или $b$ делятся на три, то и всё делится на три.
2. Если $c = 3k+1$, а $b = 3n+2$ (или симметричный вариант), то все делится на три.
3. Если $c = 3k+1$, а $b = 3n+1$ (или $c = 3k+2$, а $b = 3n+2$), то все делится на три.

других вариантов нет.

[wrest]

EUgeneUS в сообщении #1301462 писал(а):

других вариантов нет.

Да, просто я подумал вы напишете что-то вроде следующего. Если ненулевые остатки от деления двух чисел на 3 разные, то на 3 делится сумма таких чисел (первая скобка), а если остатки одинаковые одинаковые -- то разность (вторая скобка).

-- 03.04.2018, 18:32 --

xjar1 в сообщении #1301382 писал(а):

P.S. Есть ли какие-либо обобщения данной задачи, например на число слагаемых, или степень?

Число слагаемых любое большее нуля.
Для числа слагаемых больше двух все как для трех: если сумма слагаемых делится на одно из чисел $2,3,5,6,10,15,30$ то и сумма пятых степеней этих слагаемых делится на него же.

[wrest]

xjar1
Тут на соседнем форуме подсказали очень простой путь без бинома Ньютона.

Есть такое свойство пятой степени: при возведении числа в пятую степень последняя цифра сохраняется. Это свойство $5$-q степени, конечно, надо знать или догадаться что оно существует. Из этого немедленно следует одновременная делимость суммы и суммы пятых степеней на $2$ и/или на $5$ (поскольку если последняя цифра числа делится на $2$ или на $5$, то и само число делится на $2$ или на $5$). Причем -- для любого количества слагаемых.

Если какое-то число равно скажем $3k+n$ (т.е. остаток от деления на $3$ равен $n$), то $(3k+n)^5 \mod 3 = n^5 \mod 3$ (это вроде очевидно?), откуда следует, что для $n=1$ остаток будет равен $1$, для $n=2$ остаток будет равен $2^5 \mod 3 = 32 \mod 3 =2$. Таким образом, при возведении числа в $5$ степень остаток от деления на $3$ сохраняется, чем доказана делимость на $3$, причем тоже для любого количества слагаемых.

Помимо $5$ степени, указанными свойствами обладают также $9$-я, $13$-я и т.д., т.е. степени вида $5+4n$ Для всех этих степеней и любого количества слагаемых, если сумма делится на $30$, то и сумма степеней делится на $30$.

[Батороев]

wrest в сообщении #1301783 писал(а):

Есть такое свойство пятой степени: при возведении числа в пятую степень последняя цифра сохраняется. Это свойство $5$-q степени, конечно, надо знать или догадаться что оно существует.

Это свойство вытекает из Малой теоремы Ферма и проявляется во всех системах счисления с простыми (или удвоенными простыми) основаниями.

[wrest]

Батороев в сообщении #1302062 писал(а):

Это свойство вытекает из Малой теоремы Ферма

Да, вытекает. Но если вы посмотрите в первый пост темы, то увидите, что:

xjar1 в сообщении #1301382 писал(а):

в данной книге теорема Ферма к данному параграфу предполагается неизвестной.

[Батороев]

wrest
Так и я о том же - что метод, предложенный Вам на соседнем форуме, использует МТФ.

[wrest]

Батороев в сообщении #1302493 писал(а):

wrest
Так и я о том же - что метод, предложенный Вам на соседнем форуме, использует МТФ.

Сохранение последней цифры при возведении в 5 степень проверяется непосредственно возведением в 5 степень всех чисел от 1 до 9, МТФ тут не нужна. Сохранение остатка от деления на три при возведении в 5 степень проверяется “техникой остатков” (сравнениями), и для этого тоже МТФ не нужна.

[Батороев]

wrest в сообщении #1302518 писал(а):

МТФ тут не нужна

Соглашусь.
Но в пятую степень возводить наверное не обязательно. Например:

Cash в сообщении #1301395 писал(а):

$x^5-x = (x-1)x(x+1)(x^2+1)$

Здесь присутствует произведение трех последовательных целых чисел. Естественно, такое произведение делится на $2$ и на $3$.
Для проверки делимости на $5$ можно расписать: $x^5-x = x(x^2-1)(x^2+1)$ и, рассмотрев окончания квадратов чисел, убедиться, что один из этих трех множителей обязательно делится на $5$.