Олимпиада Beyond - Задача 2


Можно более подробное решение?
В частности не понял, почему рассмотрев x=1, y=1 получили что p может быть равно только {2, 3, 5, 7, 13}.

1 симпатия

По условию нужно найти р, на
которую делится данное выражение при любых x и y, В том числе при x=1 и y=1. Выражение в этом случае делится только на данный набор простых чисел, поэтому все остальные простые числа под условие задачи не подходят. Дальше доказывается то, что для всех перечисленных простых чисел действительно выполняются нужные условия уже при любых x и y.

3 симпатии

Можете подробнее объяснить все решение?

Смотри, просят найти такие р, при которых какие бы х и у не подставить, выражение будет делиться на это р. То есть, мы можем подставить любые числа и посмотреть их значения, на какие р они делятся. Вот мы и подставили 1 и 1, и поняли, что это р должно делить 8190. Поэтому возможные р сузились до этих пяти значений. Теперь осталось проверить правда ли подходят найденные р, то есть делится ли это выражение на эти р при любых х и у. В решении для этого доказывается x^{13} \equiv x (mod \ p)

Ну вот, меня интересует что дальше x^13=x (mod 1), почему нам достаточно доказать это и зачем мы это делаем

Нам нужно доказать

x^{13} + y^{13} - x - y \equiv 0 \ (mod\ p)

То есть, если x^{13} \equiv x, то аналогично y^{13} \equiv y (mod\ p), поэтому это выражение будет сравнимо с x+y-x-y \equiv 0 (mod\ p). Значит, для любых x и y это число делится на p

1 симпатия

А как мы раскрыли скобки (x+y)^13 так, чтобы получилось x^13 + y^13?

Ойойойой шизаа

Спасибо, это на самом деле прокол в оформлении решения

В общем, после доказательства x^{13}\equiv x, мы можем подставить x+y, то есть (x+y)^{13} \equiv (x+y) \equiv x^{13}+y^{13} (mod\ p). Поэтому сравнение верно

1 симпатия