Деление без остатка алгебраического выражения

[Mike Kazakov]

Здравствуйте,
Пытаюсь доказать следующее утверждение:
$(5^{2n+1}+3^{n+2}\cdot 2^{n-2})\vdots19$, при $n\in N$
Задача из темы "отношение делимости", поэтому предполагаю, что мат. индукция здесь не должна использоваться.
Просидел вчера весь вечер, но так и не постиг с чего начать рассуждать.
Единственная возникшая мысль, например, взять первое слагаемое и пытаться конвертировать его в число с модулем 19 и остатком:
$5^{2n+1}=19q+a$
Второе слагаемое можно выразить, как произведение двух чисел с модулем 19:
$(19b+c)(19d+f)$, с учетом, что остаток произведения равен произведению остатков можно записать для суммарного остатка с учетом делимости на 19:
$(a+cf) \vdots19$
но, как доказать это? Я пробовал сделал таблицу с остаткам, но после $n=10$, числа стали очень большие, в добавок расчетная программа mathcad начала глючить, и какой то закономерности я не увидел. Остатки разные, четные и нечетные. И более того в следующем задании делитель уже будет 133 и про таблицу с остатками там рассуждать будет вообще не реально. Подскажите запутавшемуся человеку правильное направление, люди добрые.

[iifat]

Возможно, стоит начать с выписывания остатков от деления $5^n$ на 19 и медитирования над получившимся рядом.

[bot]

При $n=1$ оно даже и не целое. Ну допустим начиная с двойки. Не делится. С тройки - не делится.... Начиная с 2017 - тоже не делится. Очепятка по всей видимости.
На 7 при чётных $n$ получится.

-- Вс ноя 05, 2017 16:37:18 --

Mike Kazakov в сообщении #1262412 писал(а):

числа стали очень большие

В модулярной арифметике при небольшом модуле больших чисел не бывает.

[Mike Kazakov]

bot в сообщении #1262435 писал(а):

Очепятка по всей видимости.

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

$(5^{2n+1}+3^{n+2}\cdot 2^{n-1})\vdots19$, при $n\in N$

bot в сообщении #1262435 писал(а):

В модулярной арифметике при небольшом модуле больших чисел не бывает.

Тоже как то про это думал.

iifat в сообщении #1262417 писал(а):

Возможно, стоит начать с выписывания остатков от деления $5^n$ на 19 и медитирования над получившимся рядом.

Уже составлял, что mathcad заглючил
В следующем примере у меня будет делитель 133, от такой медитации мозг закипит.

Здесь, что то по хитрее чем рассмотрение "бесконечного" ряда остатков. Как же оно все таки решается ...

[iifat]

Mike Kazakov в сообщении #1262448 писал(а):

Здесь что-то похитрее, чем рассмотрение "бесконечного" ряда остатков

«Похитрее» строится с попроще. Например, с вдумчивого (ах да — именно это важное слово я, каюсь, забыл указать явно) рассмотрения ряда остатков. Никоим, разумеется, образом не бесконечного. Хватит и пары десятков.

[bot]

Mike Kazakov в сообщении #1262448 писал(а):

с опечаткой формула была

Ну тогда всё получается.
Подсказываю: $25\equiv 6\pmod{19}, \,\, 27\equiv 8\pmod{19}, \,\, 30+8\equiv 0\pmod{19}$

[gris]

Бывает, что помогают такие преобразования: $3^{n+2}\cdot 2^{n-1}=27\cdot 3^{n-1}\cdot 2^{n-1}=27\cdot 6^{n-1}=19\cdot 6^{n-1}+8\cdot 6^{n-1}$
С первым слагаемым тоже. А там индукция в глаза лезет.
Проще сразу индукцию задействовать, если дозволяется.

[Mike Kazakov]

Все таки я осилил это задание:

Mike Kazakov в сообщении #1262448 писал(а):

$(5^{2n+1}+3^{n+2}\cdot 2^{n-1})\vdots19$, при $n\in N$

первое слагаемое раскладываем так:
$5^{2n+1}=5\cdot5^{2n}=5\cdot25^n$
с учетом, что $25^n\equiv6^n(\bmod19)$
получаем при рассмотрении остатков, что изначальное первое слагаемое можно записать:
$5^{2n+1}=5\cdot6^n=30\cdot6^{n-1}$

второе слагаемое уже разложил уважаемый gris:

gris в сообщении #1262470 писал(а):

$3^{n+2}\cdot 2^{n-1}=27\cdot 3^{n-1}\cdot 2^{n-1}=27\cdot 6^{n-1}=19\cdot 6^{n-1}+8\cdot 6^{n-1}$

и тогда складывая только остатки получаем:
$30\cdot6^{n-1}+8\cdot 6^{n-1}=38\cdot6^{n-1}$, что как раз делится на цело на 19

Вот как то так сработано, без обширных таблиц с набором остатков и без мат. индукции.
время конечно много потратил пока дошло, не без помощи призрачных намеков посетителей форума.

[bot]

Mike Kazakov в сообщении #1262718 писал(а):

время конечно много потратил пока дошло, не без помощи призрачных намеков посетителей форума

Нет, намёки то были прозрачными, а призрачными, наверно, посетители.