Проверка кратности

[xyzman]

Необходимо убедиться, что $m^5n-mn^5$ кратно 30 при любых целых m и n.
Помогите наметить ход решения.

[ИСН]

У Вас уже была похожая задача про 42. Тут то же самое.

[AD]

Разлагаем на множители и перебираем возможные остатки от деления их на 2, 3 и 5.

[xyzman]

$m^5n-mn^5=...=mn(m-n)(m+n)(m^2+n^2)$
Не вижу как дальше разложить сумму квадратов, что бы можно было легко проверить.

[Brukvalub]

xyzman в сообщении #187423 писал(а):

Не вижу как дальше разложить сумму квадратов, что бы можно было легко проверить.

Никак не разложить.

[xyzman]

Жаль, т.к. задача явно не нацелена на перебор $(2+3+5)^2$ вариантов

[gris]

Попробуйте доказать по двойной индукции.

[Батороев]

Кто про что, а я - все про Малую теорему Ферма.

$ m^5n-mn^5 = mn(m^4-n^4) $,

Откуда видно, что:
- либо $m$, либо $n$ кратны $3$ ($2, 5$).
- в противном случае, кратно выражение $m^4-n^4$ (на основании того, что при простом $p$
$ a^{k(p-1)}\equiv 1\pmod p$, где $a, k$ - натуральные числа и $a$ и $p$ - взаимнопростые).

[Dandan]

xyzman писал(а):

Жаль, т.к. задача явно не нацелена на перебор $(2+3+5)^2$ вариантов

вообще-то вариантов $2^2+3^2+5^2$, так как вы отдельно проверяете делимость на 2, на 3 и на 5. Это число смело можно делить на 2 за счет симметрии относительно m,n, плюс можно сразу отбросить варианты, когда одно из чисел сравнимо с 0.

[gris]

Кстати, получается несложно, по индукции-то, но не менее муторно, чем остатки анализировать. Вот один из шагов:
$m^5(n+1)-(n+1)^5m=m^5n+m^5-n^5m -m -5nm(n^3+2n^2+2n+1)=(m^5n-n^5m) +(m^5-m)-5nm(n+1)((n-1)(n+2)+3)=(m^5n-n^5m) +(m^5-m)-5m(n-1)n(n+1)(n+2)-15mn(n-1)$
Вся эта конструкция делится на 30.

[xyzman]

Подсказали интересное решение!

Рассмотрим выражение
$(m^5+m)(n^5-n)$.
Оно делится на 30, поскольку второй сомножитель делится на 30, т.к.
$n^5-n=...=n(n-1)(n+1)(n^2+1)$ и это кратно 2 и 3
$(n^2+1)=n^2-4+5=(n^2-4)(mod5)=(n-2)(n+2)(mod5)$, следовательно $n^5-n$ кратно 5 и все это действительно кратно 30.

Преобразуем выражение:
$(m^5 + m)(n^5 - n)=m^5n^5 + mn^5 - m^5n - mn=((mn)^5 - mn) - (m^5n - mn^5)$
Поскольку это выражение делится на 30 и первое слагаемое делится на 30 значит и второе слагаемое делится на 30, что и требовалось. Красиво