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$.
For $a^k \pmod p$, this cycle that you refer to has the name "order". We generally write this as $\text{ord}_p(a)$, that is the minimum $k$ such that $a^k \equiv 1 \pmod p$. (Then the cycle starts back at $a$). There is not really a good way to estimate this well. A weak estimate comes from Fermat's Little Theorem, a stronger one comes from the Euler Totient Function, and the strongest one that I know is the Carmichael function. Wikipedia has information on all of these.
To elaborate on the Carmichael function, if $\gcd(a,b) = 1$, define the Carmicheal value of $b$ as $\lambda(b)$.
Then it is well known (and easily proven) that $a^{\lambda(b)} \equiv 1 \pmod {b}$. Now from prime $p$, define $\lambda(p^k) = \phi(p^k)$ where $\phi$ is the totient function. Let $b = \prod_i p_i^{a_i}$. Then $\lambda(b) = lcm(\phi(p_1^{a_1}), \phi(p_2^{a_2}), \cdots)$.
Best Answer
Let's consider the numbers $-1,a-1,2a-1, \ldots (p-1)a-1$. These must have different remainders $\mod p$, since otherwise $ma \equiv na \mod p \implies p|a(m-n)$, but $p \nmid a$ and $0<|m-n|<p$, so this can't happen.
Therefore, they must leave $p-1$ different remainders $\mod p$. There are $p$ of these numbers, and $p$ possible remainders, so one of these must leave the remainder $0 \mod p$. That value of $x$ solves the equation.