Prove that if $2^{n-1}-1$, but not $2^h-1$, is divisible by $n$, then $n$ is a prime number. Let $p$ be a prime number and h be a natural number smaller than p. We set $n = ph + 1$. Prove that if $2^{n-1}-1$, but not $2^h-1$, is divisible by $n$, then $n$ is a prime number.
We have $n|2^{ph}-1, n\nmid 2^h-1\implies n|2^{p-1}h+2^{p-2}h+\dots+1$
If $n=l\alpha $ and $l $ is a prime.
We have $2^{n-1}-1\equiv 0\mod l$
So $2^{n-1}-1\equiv 0\mod l$
$2^{n-1}\equiv 1\mod l$
$2^{\alpha -1}\equiv 1\mod l$
$2^{l-\alpha}\equiv 1\mod l$
 A: We're given that
$$2^{n-1} \equiv 1 \pmod{n} \tag{1}\label{eq1A}$$
Let $k$ be the multiplicative order of $2$ modulo $n$, i.e.,
$$\operatorname{ord}_{n}(2) = k \tag{2}\label{eq2A}$$
From \eqref{eq1A}, we get
$$k \mid n - 1 \tag{3}\label{eq3A}$$
since, otherwise, there's integers $j$ and $r$ where $n - 1 = jk + r, \; \; 1 \le r \lt k$, which gives $2^{n-1} \equiv (2^{k})^j(2^r) \equiv 1(2^r) \pmod{n}$, so $2^r \equiv 1 \pmod{n}$, contradicting that $m = k$ is the smallest positive integer where $2^m \equiv 1 \pmod{n}$.
If $k \lt n - 1$, then $n - 1 = ph$ for some prime $p$ and $h = kq$ for some positive integer $q$. Since the provided conditions state this is not allowed, this means that
$$k = n - 1 \tag{4}\label{eq4A}$$
The third paragraph of the Properties section states

As a consequence of Lagrange's theorem, the order of $a \pmod{n}$ always divides $\varphi(n)$.

Note $\varphi(n)$ is Euler's totient function which

... counts the positive integers up to a given integer $n$ that are relatively prime to $n$.

From this, plus \eqref{eq2A} and \eqref{eq4A}, we also get
$$\operatorname{ord}_{n}(2) \mid \varphi(n) \; \; \to \; \; n - 1 \le \varphi(n) \tag{5}\label{eq5A}$$
Since $\varphi(n) \lt n$, plus $\varphi(n) = n - 1$ iff $n$ is prime (since any composite $n$ has less than $n-1$ integers up to $n$ which are relatively prime to $n$), then \eqref{eq5A} shows that $n$ must be prime.
