. Calculate the GCD of $a^{p}-1$ and $a^{q}-1$, where $a, p, q$ are integers.
. We use the Euclidean algorithm to find $a^{d}-1$ where $d$ is the GCD of $p$ and $q$. Indeed, if $p=b q+r$

$$
\left(a^{p}-1\right)=\left(a^{q}-1\right)\left(a^{q(b-1)+r}+a^{q(b-2)+r}+\cdots+a^{r}\right)+a^{r}-1
$$