Рекуррентные соотношения

Подсказка 1:

Какие наблюдения можно сделать, глядя на равенство из условия? Например, aₙ точно делится на n, потому что (n, n² + 1) = 1.

Подсказка 2:

Кстати, нетрудно заметить, что последовательность aₙ = n подходит. Попробуйте доказать, что это единственный ответ.

Подсказка 3:

Вместо того чтобы доказывать, что aₙ = n, можно ввести другую последовательность bₙ, зависящую от членов a. Для удобства можно подобрать такую bₙ, которая равна константе, если aₙ = n.

Подсказка 4:

Можно взять bₙ = (aₙ / n) – 1. То есть мы хотим доказать, что bₙ = 0. Какой вид примет рекуррентное соотношение?

Подсказка 5:

Обратите внимание, n² + 1 взаимно просто с n. На какую максимальную степень n делится bₙ?