Find all natural numbers $n$, such that there exist relatively prime integers $x$ and $y$ and an integer $k > 1$ satisfying the equation $3^n =x^k + y^k$.

[i]A. Kovaldji, V. Senderov[/i]
To find all natural numbers \( n \) such that there exist relatively prime integers \( x \) and \( y \) and an integer \( k > 1 \) satisfying the equation \( 3^n = x^k + y^k \), we proceed as follows:

1. **Determine the parity of \( k \):**
   - If \( k \) is even, then \( 3^n = (x^2)^{k/2} + (y^2)^{k/2} \) is a sum of two squares. However, a power of 3 can only be expressed as a sum of two squares if both squares are divisible by 3, which contradicts the condition that \( x \) and \( y \) are relatively prime. Therefore, \( k \) must be odd.

2. **Consider the equation modulo 3:**
   \[
   0 \equiv 3^n \equiv x^k + y^k \pmod{3}
   \]
   Since \( k \) is odd, \( x^k \equiv x \pmod{3} \) and \( y^k \equiv y \pmod{3} \). Thus,
   \[
   x + y \equiv 0 \pmod{3}
   \]
   This implies \( 3 \mid (x + y) \).

3. **Use the Lifting The Exponent (LTE) lemma:**
   Since \( x \) and \( y \) are relatively prime and \( 3 \mid (x + y) \), we can apply the LTE lemma:
   \[
   n = \nu_3(3^n) = \nu_3(x^k + y^k) = \nu_3(x + y) + \nu_3(k)
   \]
   where \( \nu_3 \) denotes the 3-adic valuation.

4. **Analyze the case when \( 3 \nmid k \):**
   If \( 3 \nmid k \), then \( \nu_3(x^k + y^k) = \nu_3(x + y) \). This implies:
   \[
   n = \nu_3(x + y)
   \]
   Since \( x + y \mid 3^n \), we must have \( x + y = 3^n \). However, this leads to a contradiction because \( x^k + y^k = 3^n \) and \( x + y = 3^n \) cannot both hold unless \( x = y = 1 \), which is not possible for relatively prime integers \( x \) and \( y \).

5. **Consider the case when \( k = 3k_0 \) for some integer \( k_0 \):**
   Let \( X = x^{k_0} \) and \( Y = y^{k_0} \). Then:
   \[
   3^n = X^3 + Y^3
   \]
   Since \( \gcd(X, Y) = 1 \) and \( 3 \mid (X + Y) \), we apply LTE again:
   \[
   n = \nu_3(3^n) = \nu_3(X^3 + Y^3) = \nu_3(X + Y) + 1
   \]
   This implies:
   \[
   \nu_3(X + Y) = n - 1
   \]
   Therefore, \( X + Y = 3^{n-1} \) or \( X + Y = 3^n \).

6. **Analyze the case \( X + Y = 3^{n-1} \):**
   \[
   3 = \frac{X^3 + Y^3}{X + Y} = X^2 - XY + Y^2
   \]
   This implies:
   \[
   3 = (X - \frac{1}{2}Y)^2 + \frac{3}{4}Y^2 \geq \frac{3}{4}Y^2
   \]
   Solving this inequality:
   \[
   Y^2 \leq 4 \implies Y \leq 2
   \]
   Thus, \( Y = 1 \) or \( Y = 2 \).

7. **Solve for \( Y = 1 \) and \( Y = 2 \):**
   - If \( Y = 1 \):
     \[
     3 = X^2 - X + 1 \implies X = 2
     \]
   - If \( Y = 2 \):
     \[
     3 = X^2 - 2X + 4 \implies \text{no positive integer solution for } X
     \]

8. **Verify the solution:**
   For \( X = 2 \) and \( Y = 1 \):
   \[
   3^n = 2^3 + 1^3 = 8 + 1 = 9 \implies n = 2
   \]
   Therefore, \( (x, y) = (2, 1) \) or \( (x, y) = (1, 2) \).

The final answer is \( \boxed{ n = 2 } \).