Putnam 1974 A6

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.$