Prime divisors of 2ᵖ − 1

1. $q$ is odd. From $2^p\equiv1\pmod q$, the order $d$ of $2$ modulo $q$ divides $p$, so $d\in\{1,p\}$. If $d=1$ then $2\equiv1\pmod q$, impossible. So $d=p$. By Fermat's little theorem $2^{q-1}\equiv1$, hence $p\mid q-1$. Since $q-1$ is even and $p$ is odd, $2p\mid q-1$.

2. Suppose $8191$ is composite. Then it has a prime factor $q\le\sqrt{8191}<91$, and by part 1, $q\equiv1\pmod{26}$. The numbers $\equiv1\pmod{26}$ below $91$ are $27,53,79$. Among them $27$ is not prime. Check: $8191=53\cdot154+29$ and $8191=79\cdot103+54$, so neither divides $8191$. Contradiction: $8191$ is prime.

Another check. $2^{11}-1=2047=23\cdot89$, and $23=1+2\cdot11$, $89=1+8\cdot11$ ✓.

Lesson. The multiplicative order of $a$ modulo a prime $q\mid a^p-1$ is $p$, so $q\equiv1\pmod p$.