Областная олимпиада по математике, 2024 год, 11 класс

Натуральные числа $x,y,t$ таковы, что $x^2+257=y^t$ и $2\le t\le 48$. Докажите, что число $t$ — простое. ( А. Васильев )

Комментарий/решение

Если $t$ составное, наименьший простой делитель один из $2,3,5$.Потом разбор случаев и доказывается что $t$-простое.

Кстати, в этой задаче можно было доказать, что если $t \notin \mathbb{P}$, то $2;3;5;7 \mid t$ без идеи, которую использовал автор задачи(да, там не было $7$, но он тут улетает сразу вместо с тройкой при использовании жирара). Это просто написать все не простые числа от $2$ до $48$, и посмотреть на их делители. Дальше получаем требуемое. Дальше у меня не получилось решить не сделав одно и тоже с автором

так ты же просто переформулировал идею автора, не?)

Ну тут необязательно понимать, что если $t \notin \mathbb{P} \Rightarrow \exists k : k \leq \sqrt{t}; k \mid t$

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

Конечно,как будто кто то без перебора решал

Через теорему подбора разобрать все числа от 2 до 48 можно

ты сделал мой день

Допустим t- составное =>

$2,3,5 | t$

1) $t=2k$

$257=y^{2k}-x^2$

$257=(y^k-x)(y^k+x)$

$x=y^k-1 =>y^{2k}-2y^k+258=y^{2k} => 2y^k=258 => 129=y^k$ что не возможно.

2) $t=3k$

По мод 4 понимаем что x-четный отсюда $y^{3k}$ по моду 4 дает 1 и значит $y^k$ дает тоже 1 => $x^2+256=(y^k-1)(y^2k+y^k+1)$

Так как $(y^2k+y^k+1)$ вида 4к+3 отсюда по лемме у него есть делитель вида 4к+3 назовем его p значит по теореме жирара 16 делится на p что не возможно.

3) $t=5k$

По моду 11 это не возможно.

пусть t не простое тогда t делиться на простые p,q где больше q

x^2+257=y^2m тогда 257=(y^m-x)(y^m+x) заметим что тогда y^m+x=257 и y^m-x=1 => 2y^m=258 => y^m=129 => m=1 тогда t=2

теперь мы знаем что t=2m+1.

x^2+257\equiv 2 \pmod {4} при х нечетным тоесть y^t \equiv 2 \pmod {4} ф это не возможно при t хотя бы 2

значит x=2a => x^2+257\equiv 1 \pmod {4} значит y^t \equiv 1 \pmod {4} по скольку t=2m+1 => y\equiv 1 \pmod {4}

теперь докажем что q хотя бы 7

Док-во:

1) q=3 x^2+16^2=y^3-1=(y-1)(y^2+y+1) заметим что (y^2+y+1)\equiv 3 \pmod {4} дальше по теореме жирара получим противоречие

2) q=5 x^2+15^2=y^5-2^5=(y-2\)(y^4+2y^3+4y^2+8y+1) заметим что(y^4+2y^3+4y^2+8y+16) \equiv 3 \pmod {4} то есть какой-то p\equiv 3 \pmod {4} делит 15 и х но тогда очевидно что p=3.