Number theory problem

[Keter]

Shadow, можно мне объяснить, как мы рассуждаем? По условию $n^2+k-1$ делится на $k^2+n-1$. С чего мы начинаем док-во того, что второе имеет не менее двух простых делителей? С того, что оно, раз так, должно быть не простым. Тогда мы предполагаем, что $k^2+n-1=p$, приходим к тому, что $k(k-1)(k^2+k-1)$ должно делиться на $p$(с этим согласен), но не делится, так как все множители меньше его. Значит, оно составное. Остаётся показать, что оно и не степень простого числа.
Это правильно?

[ИСН]

Как-то так, да.

[Shadow]

Начинаем с того: Пусть $k^2+n-1=L\Rightarrow n=L-(k^2-1)$
Подставляем в первое выражение вместо n:
$\left(L-(k^2-1)\right)^2+k-1$ должно по условии делится на $L$.
$L^2-2L(k^2-1)+(k^2-1)^2+k-1$ должно делится на $L$.

Значит...

[Keter]

Значит, $(k^2-1)^2+k-1$ делится на $L$. А какие случаи, когда оно не делится на $L$?

-- 10.06.2013, 16:57 --

Когда $L$ - простое или когда $L$ - степень простого?

[Shadow]

Keter в сообщении #735025 писал(а):

С чего мы начинаем док-во того, что второе имеет не менее двух простых делителей

Мда, но лучше с этим не начинать, а оставить на потом. Потом, когда докажем, что $L|k(k-1)(k^2+k-1)$ тогда предположим, что $L=p^a$

Keter в сообщении #735036 писал(а):

А какие случаи, когда оно не делится на $L$?

Как раз те случаи, когда $n^2+k-1$ не делится на $k^2+n-1$

[Keter]

$L|k(k-1)(k^2+k-1)$ и как это доказать?
Нам же важно исключить те случаи, когда оно не делится. Разве нет?

-- 10.06.2013, 17:37 --

Как доказать, что $k(k-1)(k^2+k-1)$ не делится на $p^a=k^2+n-1$ ?

-- 10.06.2013, 17:41 --

Shadow в сообщении #735038 писал(а):

Потом, когда докажем, что...

Но ведь из условия $L|k(k-1)(k^2+k-1)$, и это невозможно при $L=p,$ тогда один из множителей должен делиться на $k^2+n-1$, но, как уже сказали, не делиться. А как это обобщить на $L=p^a$?

[Shadow]

Keter, если $n^2+k-1$ делится на $k^2+n-1$, то из этого (обозначив второе за L) следует что $k(k-1)(k^2+k-1)$ делится на L. А первое дано по условие, его не надо доказывать.

[Keter]

Заключение, что нужно доказать, что при $L=p^a, \quad a \in \mathbb{N}$ условие $L|(n^2+k-1)$ не выполняется, правильное?

[Shadow]

Вообще то у нас условие $L|k(k-1)(k^2+k-1)$ (Его можно, если Вам больше нравится, получить и делением $n^2+k-1 \text{ на } n+k^2-1$
Если $L=p^a$, сколько из этих трех множителей могут делится на $p$?

[Keter]

Shadow в сообщении #735079 писал(а):

сколько из этих трех множителей могут делится

Ни один.

Хорошо, мы пришли к тому, что у нас условие $L|k(k-1)(k^2+k-1),$ какой должен быть следующий ход?

[Shadow]

Keter в сообщении #735084 писал(а):

какой должен быть следующий ход?

Пусть $L=p^a$ где p - простое. Из трех множителей, только один может делится на p, потому что они взаимнопростые. А значит он должен делится и на $p^a$, что невозможно, т.к. он меньше $L=p^a$

[Keter]

Shadow, а из этого уже следует, что $k^2+n-1$ имеет не менее двух простых множителей, понял. Спасибо.

[ins-]

Thank you for the problem. I understand Russian and I'm sorry I use English here but my Russian grammar is worst than my English. I don't have any skills in number theory but probably the creator of the problem with the same name as this one will like it.

[Keter]

ins-, good luck in understanding other problems. I want publish here 2-3 problems that have connection with Number theory and will be glad to see you.

[Deggial]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Помогите решить / разобраться (М)»
Перенёс в соответствующий раздел