Задачи по теории чисел

[mr.tumkan]

Региие в целых числах уравнение:

1) $258x-172y=112$

тут можно обе части уравнения разделить на $86$. Получим:

$3x-2y=\frac{56}{43}$

Левая часть -- целое число, правая часть не является целым числом. Таким образом уравнение не имеет решений в целых числах. Верно?

2) Решите в целых числах $209x-513y=76$

А как тут быть, тут уже не сократить ничего.
С чего тут начать? Есть ли какой-то общий подход для решений линейных уравнений с двумя переменными в целых числах? Где о нем можно почитать?

3) Решите в натуральных числах $2^x+7^y=19^z$

Как быть тут? Вижу только способ перебора.

4) Найдите сумму $1\cdot 1!+2\cdot 2!+...+n\cdot n!$

Это не арифметическая и не гометрическая прогрессия.
Как быть, от чего плясать?

[ИСН]

Совокупность этих задач в одном месте подобна книге о топоре, в которой подряд идут примеры, как топором драться, как им бриться, и как из него варить кашу.
1) верно, только обычно это излагают в терминах "что-то делится на 100500, а что-то не делится".
2)

mr.tumkan в сообщении #918424 писал(а):

А как тут быть, тут уже не сократить ничего.

Уверены?
Впрочем, сокращать не надо. (Да и там было не надо.) А надо... как бы сказать-то... Может, сначала попробовать аналогичные уравнения с маленькими числами? Например, $2x-3y=1$.
3) сделайте как-нибудь, потом будет видно.
4) найти первые 5 - 10 таких чисел, посмотреть; вдруг они на что-то похожи?

[nnosipov]

Действительно, ну и винегрет.

mr.tumkan в сообщении #918424 писал(а):

Есть ли какой-то общий подход для решений линейных уравнений с двумя переменными в целых числах? Где о нем можно почитать?

Да, об этом лучше прочитать. Ищите что-нибудь типа "расширенный алгоритм Евклида", "линейная форма наибольшего общего делителя". Правда, эти штуки нужно будет додумать до собственно алгоритма решения уравнений вида $ax+by=c$ в целых числах $x$, $y$, но это уже можно сделать самостоятельно. Ну или сразу искать в готовом виде "линейные диофантовы уравнения с двумя неизвестными".

-- Пн окт 13, 2014 17:18:52 --

mr.tumkan в сообщении #918424 писал(а):

Вижу только способ перебора.

А как тут всё перебрать? Он же как бы бесконечен, этот перебор.

[mr.tumkan]

Спасибо.
2) Действительно, делится на 19
$11x-27y=4$
Но а как дальше?
3) А хоть что-нибудь -- это что?
4) $1+8+18+96+600+4320$
Пока что не вижу закономерности.

[ИСН]

2) Действительно, рассмотрите более простое уравнение: $2x-3y=1$. Есть ли у него целочисленные решения? Какие, сколько, как они описываются?
3) Хоть что-нибудь - это найти перебором маленькие решения или их отсутствие.
4) Не надо таких чисел. Найдите несколько первых сумм.

-- менее минуты назад --

mr.tumkan в сообщении #918443 писал(а):

$1+8+18+96+600+4320$

Откуда это 8, кстати?

[Cash]

3) посмотрите остатки по малым модулям
Например, по модулю $2$ уравнение выглядит как $0^x+1^y=1^z$ - ничего интересного.
Но может что-то содержательное получим по другим модулям?

[B@R5uk]

mr.tumkan в сообщении #918424 писал(а):

4) Найдите сумму $1\cdot 1!+2\cdot 2!+...+n\cdot n!$

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

[iifat]

mr.tumkan в сообщении #918443 писал(а):

Но а как дальше?

nnosipov в сообщении #918434 писал(а):

"расширенный алгоритм Евклида", "линейная форма наибольшего общего делителя"

Как вы думаете, зачем nnosipov это написал?

[nnosipov]

B@R5uk в сообщении #918497 писал(а):

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

Вот это-то зачем? (Тем более что найти такую формулу не удастся.) В тоже время исходная сумма фактически уже найдена Вами.

[B@R5uk]

nnosipov в сообщении #918500 писал(а):

В тоже время исходная сумма фактически уже найдена Вами.

А, точно. Прибавить к искомой сумме один факториал и вся сумма поочерёдно свернётся в один-единственный факториал.

[gefest_md]

mr.tumkan в сообщении #918424 писал(а):

4) Найдите сумму $1\cdot 1!+2\cdot 2!+...+n\cdot n!$
...
Как быть, от чего плясать?

Цитата:

One of the mathematician's most useful tricks is knowing when and how to add zero.

$a_k=k\cdot k! =$

[mr.tumkan]

ИСН в сообщении #918445 писал(а):

2) Действительно, рассмотрите более простое уравнение: $2x-3y=1$. Есть ли у него целочисленные решения? Какие, сколько, как они описываются?

$x=-1-3k, y=-1-2k$
А для второй задачи $209x-513y=76$ понятно теперь. Там получается $x=20-27k, y=8-11k$.
А с третьей и четвертой задачей пока что не ясно.

ИСН в сообщении #918445 писал(а):

3) Хоть что-нибудь - это найти перебором маленькие решения или их отсутствие.

При $z=0,1,2,3$ решений не будет.

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

3) посмотрите остатки по малым модулям
Например, по модулю $2$ уравнение выглядит как $0^x+1^y=1^z$ - ничего интересного.
Но может что-то содержательное получим по другим модулям?

По модулю $5$ выходит что-то интересное $2^x+2^y=4^z$, но как это использовать (хочется взять $x=y=z=1$)?

gefest_md в сообщении #918560 писал(а):

$a_k=k\cdot k! =$

$a_k=k\cdot k! =1\cdot 2\cdot 3\cdot ...\cdot k\cdot k$
Но как это поможет?

ИСН в сообщении #918445 писал(а):

4) Не надо таких чисел. Найдите несколько первых сумм.
$1+8+18+96+600+4320$ Откуда это 8, кстати?

Да, 8 не должно быть.
$S_1=1$
$S_2=1+4=5$
$S_3=5+18=23$
$S_4=23+96=119$
$S_6=119+600=719$
$S_7=719+4320=5039$
$S_8=5039+35280=40319$

Пока вижу только закономерность, что все суммы заканчиваются на $9$, начиная с четвертой.

[Cash]

mr.tumkan в сообщении #918923 писал(а):

По модулю $5$ выходит что-то интересное $2^x+2^y=4^z$, но как это использовать (хочется взять $x=y=z=1$)?

Никак. Другой модуль взять.

[gefest_md]

mr.tumkan в сообщении #918923 писал(а):

gefest_md в сообщении #918560 писал(а):

$a_k=k\cdot k! =$

$a_k=k\cdot k! =1\cdot 2\cdot 3\cdot ...\cdot k\cdot k$
Но как это поможет?

Я имел в виду преобразовать как-то $k\cdot k!$ в разность. Для этого я подсказал прибавить к чему-то некоторое нулевое значение.

[mr.tumkan]

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

mr.tumkan в сообщении #918923 писал(а):

По модулю $5$ выходит что-то интересное $2^x+2^y=4^z$, но как это использовать (хочется взять $x=y=z=1$)?

Никак. Другой модуль взять.

Я просто не понимаю -- что в итоге хочется получить подбором модуля.

-- 14.10.2014, 21:30 --

gefest_md в сообщении #918983 писал(а):

mr.tumkan в сообщении #918923 писал(а):

gefest_md в сообщении #918560 писал(а):

$a_k=k\cdot k! =$

$a_k=k\cdot k! =1\cdot 2\cdot 3\cdot ...\cdot k\cdot k$
Но как это поможет?

Я имел в виду преобразовать как-то $k\cdot k!$ в разность. Для этого я подсказал прибавить к чему-то некоторое нулевое значение.

$a_k=k!k=k!k+k!-k!=k!(k+1)-k!=(k+1)!-k!=$

$a_1+a_2+...+a_n=2!-1!+3!-2!+4!-3!+...+(n+1)!-n!=(n+1)!-1$

Верно?