Can we find $n$ such that $p|2^n-1$ for a given prime $p.$

Question

For a given prime $p$ can we find a positive integer $n$ such that $p$ is a divisor of $2^n-1.$
I know, choosing a large $n$ we can do this. But is there any proof for this? I have no idea for start a proof. A hint would be better. Thank you.

Answer 1

As a hint, how many different remainders can you get if you divide $2^n$ by $p$?

Answer 2

This is a simple application of Fermat's little theorem. Let's say the given prime is odd, that is to say, $p \neq 2$, so therefore $\gcd(2, p) = 1$. From Fermat's little theorem, it follows that $n = p - 1$ has the desired property.

Just to be sure, work out three or four examples by hand or on a calculator. I'll do one for you: $p = 13$, so $n = p - 1 = 12$, then we see that $$\frac{2^{12} - 1}{13} = 315.$$