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

Опишите все многочлены $P(x)$ с целочисленными коэффициентами, удовлетворяющие условию: для каждого целого положительного $n$ число $2^n-1$ делится на $P(n)$.

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

Пусть P(n) делится на простое число p, при целых n

(2ⁿ – 1) делится на p

2ⁿ ≡ 1(mod p)

Заметим что P(n+p) тоже делится на p

2^(n+p) ≡ 1(mod p)

2^n * 2^p ≡ 1(mod p)

1 * 2^p ≡ 1(mod p)

2^p ≡ 1(mod p)

По МТФ

2^p ≡ 2(mod p)

2≡1(mod p)

1≡0(mod p)

p=±1

Противоречие, тк p простое

Значит P(n) не делится на p, при целых n

Значит P(n)=±1

Проверкой убеждаемся что оба многочлена удовлетворяют условию

Ответ: P(n)=1 ; P(n)=-1