Q:

If p is a prime divisor of the n-th Fermat number, and k is the multiplicative order of 2 mod p then $k|p-1$

In the question Multiplicative order with Fermat numbers, it is established that if p is a prime divisor of the n-th Fermat number $F_n=2^{2^n}+1$ then the multiplicative order of 2 mod p is $k=2^{n+1}$. The exercise, which is from Gerstein's Introduction to Mathematical Structures and Proofs, goes on to ask for a demonstration that $k|p-1$.
We have $2^k\equiv 1 \pmod{p}$
$2^k = qp+1$ for some integer q
$2^{2^n}+1=tp$ for some integer t.
The text offers little about Fermat numbers except that they are pair-wise relatively prime and that some of them are composite.
For n=6, a prime factor is p=641 and k=128 and $128|(641-1)$, so the relation holds in this case.
Where to go from here?

A:

Since $\gcd(2, p) = 1$ and $p$ is a prime, Fermat's little theorem states
$$2^{p-1} \equiv 1 \pmod{p} \tag{1}\label{eq1A}$$
Given that $k = 2^{n+1}$ is the multiplicative order of $2$ modulo $p$, it must divide any positive power where the result is congruent to $1$ modulo $p$, so this means
$$k \mid p - 1 \tag{2}\label{eq2A}$$
More generally for any coprime $a$ and $n$, Euler's theorem says that
$$a^{\varphi(n)} \equiv 1 \pmod{n} \tag{3}\label{eq3A}$$
where $\varphi(n)$ is Euler's totient function. Thus, the multiplicative order of $a$ modulo $n$ must divide $\varphi(n)$.
For primes $p$, since $\varphi(p) = p - 1$, then Euler' theorem coincides with Fermat's little theorem.

