How to prove that $q^r$ and $q^s-1$ are relatively prime? How to prove that $q^r$ and $q^s-1$ are relatively prime? ($q$ is prime or prime power)
 A: We do not need to assume anything about $q$, but we do need to assume that $s\gt 0$.
Let $d\gt 1$ be a divisor of $q^r$. Then some prime $p$ divides $d$, and hence $q$. Then $p$ divides $q^s$. Hence it cannot divide $q^s-1$, else it would divide $1$. 
A: Here's another proof that works for arbitrary $q$, not just prime powers, using only the 'core axiom' of GCD that $\gcd(a,b) = \gcd(a, b+c\times a)$ for any $a\geq 1, b\geq 1, c$:
First, suppose $s\geq r$.  Then $\gcd(q^s-1, q^r) = \gcd(q^r, (q^s-1)-q^{s-r}q^r)$ (using the axiom with $a=q^r, b=q^s-1, c=-q^{s-r}$) $=\gcd(q^r, (q^s-1)-q^s)$ (arithmetic) $=\gcd(q^r, -1) = 1$.  
Likewise, if $s\lt r$, then $\gcd(q^s-1, q^r) = \gcd(q^s-1, q^r-q^{r-s}(q^s-1))$ (using the axiom again, with $a=q^s-1, b=q^r, c=-q^{r-s}$) $= \gcd(q^s-1, q^r-q^r+q^{r-s})$ $= \gcd(q^s-1, q^{r-s})$ (arithetic), and the exponent $r$ has been replaced by $t=r-s$; we can keep 'subtracting $s$' from the other exponent in this way until we get to $\gcd(q^s-1, q^r) = \gcd(q^s-1, q^w)$ for some some $w\leq s$, and then use the first case.
