MathDB

Given

n

, let

k = k(n)

be the minimal degree of any monic integral polynomial

f(x)=x^k + a_{k-1}x^{k-1}+\ldots+a_0

such that the value of

f(x)

is exactly divisible by

n

for every integer

x.

Find the relationship between

n

and

k(n)

. In particular, find the value of

k(n)

corresponding to

n = 10^6.

Problem Statement