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.$
1. **Understanding the Problem:**
   We need to find the minimal degree \( k = k(n) \) of a monic integral polynomial \( f(x) \) such that \( f(x) \) is divisible by \( n \) for every integer \( x \). The polynomial is given by:
   \[
   f(x) = x^k + a_{k-1}x^{k-1} + \ldots + a_0
   \]
   and we need \( f(x) \equiv 0 \pmod{n} \) for all integers \( x \).

2. **Finite Differences and Factorials:**
   The \( k \)-th finite difference of a polynomial \( f(x) \) of degree \( k \) is constant and equal to \( k! \). This is because the \( k \)-th finite difference of \( x^k \) is \( k! \). Therefore, for \( f(x) \) to be divisible by \( n \) for all \( x \), \( n \) must divide \( k! \).

3. **Constructing the Polynomial:**
   Consider the polynomial:
   \[
   f(x) = x(x-1)(x-2)\cdots(x-k+1) = k! \binom{x}{k}
   \]
   This polynomial is always divisible by \( k! \). If \( n \mid k! \), then \( f(x) \) is divisible by \( n \) for all \( x \).

4. **Finding \( k(n) \):**
   We need to find the smallest \( k \) such that \( n \mid k! \). This can be determined using Legendre's formula, which gives the highest power of a prime \( p \) dividing \( n! \):
   \[
   \nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor
   \]
   For \( n = 10^6 = 2^6 \cdot 5^6 \), we need to find the smallest \( k \) such that \( 2^6 \cdot 5^6 \mid k! \).

5. **Applying Legendre's Formula:**
   - For \( p = 2 \):
     \[
     \nu_2(k!) = \sum_{i=1}^{\infty} \left\lfloor \frac{k}{2^i} \right\rfloor
     \]
     We need \( \nu_2(k!) \geq 6 \).
   - For \( p = 5 \):
     \[
     \nu_5(k!) = \sum_{i=1}^{\infty} \left\lfloor \frac{k}{5^i} \right\rfloor
     \]
     We need \( \nu_5(k!) \geq 6 \).

6. **Calculating \( k \):**
   - For \( p = 2 \):
     \[
     \nu_2(25!) = \left\lfloor \frac{25}{2} \right\rfloor + \left\lfloor \frac{25}{4} \right\rfloor + \left\lfloor \frac{25}{8} \right\rfloor + \left\lfloor \frac{25}{16} \right\rfloor = 12 + 6 + 3 + 1 = 22
     \]
   - For \( p = 5 \):
     \[
     \nu_5(25!) = \left\lfloor \frac{25}{5} \right\rfloor + \left\lfloor \frac{25}{25} \right\rfloor = 5 + 1 = 6
     \]

   Since \( \nu_2(25!) = 22 \geq 6 \) and \( \nu_5(25!) = 6 \geq 6 \), \( 25! \) is divisible by \( 10^6 \).

Therefore, the minimal \( k \) such that \( 10^6 \mid k! \) is \( k = 25 \).

The final answer is \( \boxed{ k(10^6) = 25 } \).