You have mentioned ingredients that lead to a proof. As you point out, the number $n$ must be prime, so we can use Fermat's Theorem.
There are a couple of different versions of Fermat's Theorem. Each version is not difficult to derive from the other.
Version 1: If $n$ is prime, then for any integer $a$, we have $a^n \equiv a \pmod n$. This says directly that $n$ divides $a^n-a$, which is exactly what you want to show, in the special case $a=2$.
Version 2: If $n$ is prime, and $n$ does not divide $a$, then $a^{n-1} \equiv 1 \pmod n$.
In your case, $n$ is odd, so if $a=2$, then $n$ does not divide $a$. It follows that $n$ divides $2^{n-1}-1$, and therefore $n$ divides twice this number, which is $2^n-2$.
However, you were given a hint which enables us to bypass Fermat's Theorem. So probably you were expected to argue as follows.
Since $p=2^n-1$, certainly $p$ divides $2^n-1$, so $2^n \equiv 1 \pmod p$. That implies that the order of $2$ in the field $\mathbb{Z}_p$ is a divisor of $n$. But the order of $2$ is exactly $n$, since $n$ is prime, and therefore the only divisors of $n$ are $1$ and $n$.
The order of any element of the field $\mathbb{Z}_p$ divides $p-1$. Since the order of $2$ in this field is $n$, we conclude that $n$ divides $p-1$, that is, $n$ divides $2^n-2$.
Hints:
-- FLT: For any $\;a\in\Bbb Z\;,\;\;a^p\equiv a\pmod p\;$
-- Wilson's Theorem: for any prime $\;p\in\Bbb N\;,\;\;(p-1)!\equiv -1\pmod p\;$
Best Answer
Okay, I'm on a little different wavelength so I'll turn my comment into an answer.. if $n$ is odd the polynomial $x + y$ divides $x^n + y^n$. So letting $x = 2^2, y = 3^2,$ and $n = 35$ you get that $13 = 2^2 + 3^2$ divides $2^{70} + 3^{70}$.