引理 A：

\[\gcd(a,c)=1\implies \gcd(ab,c)=\gcd(b,c) \]

证明略。

引理 B：

\[\gcd(q^a,q^b-1)=1 \]

证明：若 \(\gcd(q^a,q^b-1)\) 中含素因子 \(p\)，则 \(q\equiv 0\pmod{p},q^b-1\equiv -1\pmod{p}\)，然而 \(q^b-1\equiv 0\pmod{p}\)，矛盾，原命题得证。

所以不妨设 \(a<b\)，则：

\[\begin{aligned} &\gcd(q^a-1,q^b-1) \\=&\gcd(q^b-q^a,q^b-1) \\=&\gcd(q^a(q^{b-a}-1),q^b-1) \\=&\gcd(q^{b-a}-1,q^b-1) \\&\dots \\=&\gcd(q^{\gcd(a,b)}-1,q^{\gcd(a,b)}-1) \\=&q^{\gcd(a,b)}-1 \end{aligned}\]