For any natural number $m$, we denote by $\phi (m)$ the number of integers $k$ relatively prime to $m$ and satisfying $1 \le k \le m$. Determine all positive integers $n$ such that for every integer $k > n^2$, we have $n | \phi  (nk + 1)$.

(Daniel Harrer)
1. **Define Euler's Totient Function**: For any natural number \( m \), Euler's totient function \( \phi(m) \) counts the number of integers \( k \) that are relatively prime to \( m \) and satisfy \( 1 \le k \le m \).

2. **Identify the Problem**: We need to determine all positive integers \( n \) such that for every integer \( k > n^2 \), \( n \) divides \( \phi(nk + 1) \).

3. **Choose a Prime \( p \)**: Let \( p \) be the smallest prime that does not divide \( n \). This choice is crucial because it allows us to construct large values of \( k \) such that \( nk + 1 \) has a specific form.

4. **Construct \( k \)**: Consider \( k = \frac{p^x - 1}{n} \) for some large \( x \). This ensures \( k \) is an integer because \( p^x - 1 \) is divisible by \( n \).

5. **Evaluate \( \phi(nk + 1) \)**: We have \( nk + 1 = p^x \). Therefore, \( \phi(nk + 1) = \phi(p^x) = p^x - p^{x-1} = p^{x-1}(p - 1) \).

6. **Divisibility Condition**: Since \( n \mid \phi(nk + 1) \), we must have \( n \mid p^{x-1}(p - 1) \). Given that \( p \) does not divide \( n \), it follows that \( n \mid (p - 1) \).

7. **Bound on \( n \)**: This implies \( n \le p - 1 \). Let \( q \) be the largest prime factor of \( n \). If \( p < q \), then \( n \le q - 1 \). Otherwise, by Bertrand's postulate, there exists a prime \( p \) such that \( q < p \le 2q \). Hence, \( n \le 2q \).

8. **Case Analysis**:
   - If \( q \le 3 \), then \( n \) can be \( 1, 2, 3, 4, 5, 6 \).
   - Check each value:
     - \( n = 1 \): Works because \( \phi(nk + 1) = \phi(k + 1) \) is always divisible by 1.
     - \( n = 2 \): Works because \( \phi(2k + 1) \) is even for \( k > 4 \).
     - \( n = 3 \): Does not work because \( \phi(3k + 1) \) is not necessarily divisible by 3.
     - \( n = 4 \): Does not work because \( \phi(4k + 1) \) is not necessarily divisible by 4.
     - \( n = 5 \): Does not work because \( \phi(5k + 1) \) is not necessarily divisible by 5.
     - \( n = 6 \): Does not work because \( \phi(6k + 1) \) is not necessarily divisible by 6.

9. **Conclusion**: The only values of \( n \) that satisfy the condition are \( n = 1 \) and \( n = 2 \).

The final answer is \( \boxed{1, 2} \).