Question

Найдите остаток от деления 30^99+61^99 на 31.

Answer 1

  Способ 1.   Бином Ньютона  

$\displaystyle 30^{99}+61^{99} = (31-1)^{99}+(62-1)^{99} = \\\\= \underbrace {C^0_{99} \cdot 31^{99} - C^1_{99} \cdot 31^{98} + C^2_{99} \cdot 31^{97} - ... + C^{98}_{99} \cdot 31}_{: \; 31} \,\, - \,\, 1 \,\,\, + \\\\+ \underbrace {C^0_{99} \cdot 62^{99} - C^1_{99} \cdot 62^{98} + C^2_{99} \cdot 62^{97} - ... + C^{98}_{99} \cdot 62}_{: \; 62 \, = \, 2\cdot31} \,\, - \,\, 1$

Применив бином Ньютона, мы обнаружили, что $30^{99}+61^{99}$ - это что-то, делящееся на $31$ и еще минус $2$. То есть искомый остаток - это $29$.

  Способ 2.   Остатки по модулю  

$30^{99}+61^{99} \equiv (-1)^{99} + (-1)^{99} \equiv (-1)+(-1) \equiv 29 \,\,\, \mod 31$

Заметив, что и $31$, и $61$, - это $-1$ по модулю $31$, мы получаем тот же ответ.

Ответ: 29.