Processing math: 36%

Западно-Китайская математическая олимпиада, 2011 год


Найдите все такие пары целых чисел (a,b), что n|(an+bn+1) для всех натуральных n.
посмотреть в олимпиаде

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

пред. Правка 2   2
4 года 4 месяца назад #

Ответ: (a,b)=(0,0),(1,1).

Решение 1: Заметим, что a=0b=0, а также (a,b)=(0,0) подходит под условие. Далее a,b0. Заметим, что

n2na2n+b2n+1.

Поскольку a^n\equiv -b^{n+1}\pmod n\implies -b^{2n+1}\equiv a^{2n}\equiv b^{2n+2}\pmod n

\implies n\mid b^{2n+1}(b+1),

следовательно b+1=0, поскольку существует бесконечно много n таких, что gcd(n,b)=1, откуда n\mid b+1 для достаточно больших n.

Аналогично a+1=0. Значит (a,b)=(-1,-1).

Решение 2: Подставим n=p,2p для всех простых p, тогда из Малой Теоремы Ферма

0\equiv a^{p}+b^{p+1}\equiv a+b^2\pmod p,

0\equiv a^{2p}+b^{2p+1}\equiv a^2+b^3\pmod p.

Тогда a+b^2=a^2+b^3=0, откуда получаем ответы.