Problem 3

Let $x$ and $y$ be the least positive exponents with $2^x\equiv-1\pmod p$ and $2^y\equiv1\pmod p$. Write $n=ys+r$ with $0\le r<y$. Since $2^n\equiv-1$ and $2^y\equiv1$, $2^r\equiv-1$; hence $r>0$ and $x\le r<y$. Now write $n=hx+k$ with $0\le k<x$. Then $-1\equiv(-1)^h2^k\pmod p$. If $h$ is even, this says $2^k\equiv-1$, contradicting the minimality of $x$ when $k>0$; if $h$ is odd, it says $2^k\equiv1$, contradicting the minimality of $y$ because $0<k<x<y$. Thus $k=0$, so $x\mid n$. Also $x\le r<y<p$, and the smallest prime divisor $p$ of $n$ forces $x=1$. Therefore $2\equiv-1\pmod p$ and $p=3$.