← All solutions

One of the easiest ways of solving this problem is based on the following fact: P( x ) is divisible by D for every integer x ≥ 1 if and only if P( x ) is divisible by D for every integer 1 ≤ x ≤ deg( P) + 1.

Here’s a sketch of the proof of this fact: another way of saying that D divides P( x ) for every x ≥ 1 is to say that D divides P(1) and that D divides P( x + 1) − P( x ) for all x ≥ 1. But Q( x ) := P( x + 1) − P( x ) is a polynomial of strictly smaller degree than P, so by induction, D divides Q( x ) for every x ≥ 1 if and only if D divides Q( x ) for every 1 ≤ x ≤ deg( Q) + 1 ≤ deg( P), so P( x ) is divisible by D for every x ≥ 1 if and only if D divides P(1) and D divides P( x + 1) − P( x ) for every 1 ≤ x ≤ deg( P), which is another way of formulating the statement that we are trying to prove.

When checking if P( x ) is divisible by D, we only need to compute P( x ) mod D, which means that there is no need to use Big Integers.