maxal писал(а):
Как именно? Прошу продемонстрировать...
Найдется t, для которого

делится на p.
Рассмотрим множество

. В нем
![$([\sqrt{p}]+1)^2-1$ $([\sqrt{p}]+1)^2-1$](https://dxdy-03.korotkov.co.uk/f/2/7/d/27d3af4065f6e924847250cd7d1024fb82.png)
>

элементов. Значит, среди остатков от деления на p найдется либо 0, либо 2 равноостаточных. В последнем случае разность (которая c точностью до знака y лежит в A) все равно даст нулевой остаток при делении на p. И в обоих случаях |x|+|y|>0.
Итак, пусть x+ty делится на p. Тогда

- тоже, а значит и

делится на p, т.е. равно pk, где k < N. Дальше я хотел воспользоваться индукционным предположением для k, но когда написал здесь решение, понял что для этого нужно, чтоб N было меньше k, а не наоборот
