Se um inteiro n deixa resto r na divisão por m, como determinar o resto de um polinômio P(n) dividido por m?

Substitua n = m q + r e reduza os termos múltiplos de m, o resto é P(r) módulo m.

Explicação:
Se n = m q + r, então \(P(n)=P(mq+r)\). Ao expandir, todos os termos que contêm fator m são múltiplos de m e não alteram o resto na divisão por m, portanto o resto é igual a \(P(r)\) tomado modulo m.

Exemplo:
Se \(m=5\), \(r=2\) e \(P(n)=n^3+2n+4\), substituímos \(n=5q+2\):
\( (5q+2)^3+2(5q+2)+4 =\) termos múltiplos de 5 \(+\; (8+4+4)=16\).
Como \(16=5\cdot3+1\), o resto é 1, que coincide com \(P(2)=2^3+2\cdot2+4=16\equiv1\pmod{5}\).