Find all pairs of natural numbers $(n, k)$ with the following property:
Given a $k\times k$ array of cells, such that every cell contains one integer, there always exists a path from the left to the right edges such that the sum of the numbers on the path is a multiple of $n$.

Note: A path from the left to the right edge is a sequence of cells of the array $a_1, a_2, ... , a_m$ so that $a_1$ is a cell of the leftmost column, $a_m$ is the cell of the rightmost column, and $a_{i}$, $a_{i+1}$ share an edge for all $i = 1, 2, ... , m -1$.
1. **Understanding the Problem:**
   We need to find all pairs of natural numbers \((n, k)\) such that for any \(k \times k\) array of integers, there exists a path from the left edge to the right edge where the sum of the numbers on the path is a multiple of \(n\).

2. **Initial Observation:**
   We start by considering the case where \(n > k\). If we place the number 1 in every cell of the leftmost column, the sum of any path from the left to the right edge will be at most \(k\). Since \(n > k\), it is impossible for the sum to be a multiple of \(n\). Therefore, \(n \leq k\) must hold for the property to be satisfied.

3. **Verification for \(n \leq k\):**
   We need to show that if \(n \leq k\), then there always exists a path from the left to the right edge such that the sum of the numbers on the path is a multiple of \(n\).

4. **Path Covering \(m \times k\) Rectangle:**
   Consider paths through the uppermost \(r \times k\) rectangles for \(r = 1, 2, \ldots, k\). For each \(r\), let \(S_r\) be the sum of the numbers on the path through the \(r \times k\) rectangle.

5. **Using the Pigeonhole Principle:**
   Since there are \(k\) different sums \(S_1, S_2, \ldots, S_k\) and only \(n\) possible residues modulo \(n\) (0, 1, 2, ..., \(n-1\)), by the Pigeonhole Principle, at least two of these sums must have the same residue modulo \(n\). Let's say \(S_a \equiv S_b \pmod{n}\) for some \(a < b\).

6. **Constructing the Path:**
   The difference between these sums, \(S_b - S_a\), corresponds to the sum of the numbers on the path covering the \((b-a) \times k\) rectangle. Since \(S_a \equiv S_b \pmod{n}\), we have:
   \[
   S_b - S_a \equiv 0 \pmod{n}
   \]
   This means that the sum of the numbers on the path covering the \((b-a) \times k\) rectangle is divisible by \(n\).

7. **Conclusion:**
   Therefore, for any \(k \times k\) array of integers, there always exists a path from the left to the right edge such that the sum of the numbers on the path is a multiple of \(n\) if and only if \(n \leq k\).

The final answer is \( \boxed{ (n, k) } \) is a solution if and only if \(n \leq k\).