Очень много делителей

[Ktina]

Доказать, что для каждой пары натуральных чисел $(n, m)$ существует натуральное $k$, такое что $\tau (k^2+m)>n$

[hippie]

$\tau$ это количество делителей? Еле нашёл такую функцию.

Существует бесконечное количество простых чисел $p,$ взаимно простых с $m$ и при этом таких, что найдётся $k,$ такое, что $k^2+m$ кратно $p.$
Действительно, предположим, что таких чисел всего $j.$ Возьмём $P=\prod\limits_{i=1}^j p_i.$ Тогда все простые делители $P^2+m$ взаимно просты и с $P$ и с $m.$ Противоречие.

Из китайской теоремы следует, что если для каждого из (попарно различных) простых чисел $p_i$ найдётся $k_i,$ такое, что $k_i^2+m$ кратно $p_i,$ то найдётся и $k,$ такое, что $k^2+m$ кратно $P=\prod\limits_{i=1}^j p_i.$
При таком $k$ количество делителей $k^2+m$ не меньше чем $2^j,$ т.е. может быть сделано сколь угодно большим.

[Ktina]

hippie в сообщении #570165 писал(а):

$\tau$ это количество делителей? Еле нашёл такую функцию.

Существует бесконечное количество простых чисел $p,$ взаимно простых с $m$ и при этом таких, что найдётся $k,$ такое, что $k^2+m$ кратно $p.$
Действительно, предположим, что таких чисел всего $j.$ Возьмём $P=\prod\limits_{i=1}^j p_i.$ Тогда все простые делители $P^2+m$ взаимно просты и с $P$ и с $m.$ Противоречие.

Из китайской теоремы следует, что если для каждого из (попарно различных) простых чисел $p_i$ найдётся $k_i,$ такое, что $k_i^2+m$ кратно $p_i,$ то найдётся и $k,$ такое, что $k^2+m$ кратно $P=\prod\limits_{i=1}^j p_i.$
При таком $k$ количество делителей $k^2+m$ не меньше чем $2^j,$ т.е. может быть сделано сколь угодно большим.

Я нашла более простое решение, не использующее $CRT$ и доступное семиклассникам.
Покамест не публикую, а врдуг кто додумается.

-- 12.05.2012, 21:40 --

(Оффтоп)

Да, $\tau$ - это количество делителей, я думала, все это знают.

$CRT$ - не кинескоп старого телека, а китайская теорема об остатках.

[ИСН]

CRT вполне доступна семиклассникам. У меня в голове мелькнуло что-то, связанное с теоремой Дирихле о простых числах в арифметической прогрессии (которая действительно чересчур), но hippie от неё элегантно отвязался.

[Ktina]

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

CRT вполне доступна семиклассникам. У меня в голове мелькнуло что-то, связанное с теоремой Дирихле о простых числах в арифметической прогрессии (которая действительно чересчур), но hippie от неё элегантно отвязался.

В таком случае, можно сказать, что моё решение доступно даже пятиклассникам, оно не использует ни одной теоремы.

-- 12.05.2012, 21:55 --

Подожду до завтрашнего вечера.
Если никто не догадается, напишу.

[ИСН]

Ну, извольте. $k=m^{100500}$. Тогда $k^2+m=m(m^{2a-1}+1)$, а это делится на все $m^x+1$, где x...

[Ktina]

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

Ну, извольте. $k=m^{100500}$. Тогда $k^2+m=m(m^{2a-1}+1)$, а это делится на все $m^x+1$, где x...

Ну, Ваше даже проще моего
Моё основывается на ФСУ "сумма кубов делится на сумму".
Подробности будут завтра, а то глаза уже sleepаются.

[ИСН]

Да я понял. Вы вместо моего 100500 берёте (степени тройки плюс 1) пополам.