Question: Let $p$ be a prime number $q$ a prime number that divides $2^p -1$.

1. Prove that $p|q-1$
2. Deduce that there are infinitely many prime numbers.

---

1. I think I should use that $a^p \ = \ a\mod p $, because it is the only theorem in my book that has something to do with number theory, but I have no idea how I should apply it here. Please give me a **subtle hint**.
2. I don't see how the second statement would be tue either. Another **subtle hint** would be nice.

Answer: 
(1) If $2$ has order $p$ in $(\mathbb{Z}/q\mathbb{Z})^\*$, the order of $2$ must divide the order of $(\mathbb{Z}/q\mathbb{Z})^\*$ due to Lagrange's theorem;

(2) From $(1)$, any prime $q$ that divides $2^p-1$ satisfies $q\equiv 1\pmod{p}$. In particular, $q>p$.
**Hint for 1.** If $q|2^p-1$, $2^p\equiv1\pmod q$. So $\operatorname{ord}\_q2|p$, which means that $\operatorname{ord}\_q2=1\mbox{ or }p.$ But $\operatorname{ord}\_q2$ cannot be 1. Then use $\operatorname{ord}\_q2|\phi(q)=q-1$.

**p.s.** $\operatorname{ord}\_q2$ is a smallest integer $r\ge0$ such that $2^r\equiv1\pmod q$.

**Hint for 2.** If there exists a maximum prime $p$, if a prime $q$ divides $2^p-1$, $p|q-1$, so $q>p$.