Остаток от деления простого числа

[Ktina]

а) Остаток от деления простого числа на $n$ может быть только числом Фибоначчи. Найдите все такие $n$ и докажите, что других нет.

б) Остаток от деления простого числа на $k$ может быть только числом, свободным от квадратов. Найдите все такие $k$ и докажите, что других нет.

[Dmitriy40]

а) $n=\{1,2,3,4,6\}$.
б) $k=\{4,6,8,12,18,24,30\}$.

[Ktina]

Dmitriy40
Разве 0 уже стал числом Фибоначчи?

[Dmitriy40]

Ktina
Да, вполне, в зависимости от соглашений: https://en.wikipedia.org/wiki/Fibonacci_number

[Ktina]

Dmitriy40
А почему в пункте б) больше 30 не может быть?

[Dmitriy40]

Ktina в сообщении #1421536 писал(а):

Dmitriy40
А почему в пункте б) больше 30 не может быть?

Потому что будет возникать остаток $25$, который как понимаете не свободен от квадратов. А с увеличением $k$ будут ещё и остатки $49$ и $81$ и $121$ и т.д. Доказывать что для какого-то $k=6m>30$ не существует простых вида $6mt+(2n+1)^2$ лень, проще несколько первых проверить прямо, а дальше положиться на плотность и равномерность простых.

(Программа на PARI/GP это подтверждает)

for(k=2,10^5,forprime(p=2,10^6,if(!issquarefree(p%k),next(2)));print(k))

[Ktina]

Dmitriy40
Большое спасибо!