Difference of powers/factor theorem

Prove that:
If x divides y, then (a^x - 1) divides (a^y - 1) where a,x,y are positive integers and a > 1.

Proof:
We know that a^x - 1 can be written as (a - 1)(1 + a + a^2 ... a^(x-1))
Let
y = kx
Then
a^y - 1 = a^(kx) - 1 = (a^x)^k - 1
Let
u = a^x
then
a^y - 1 = u^k - 1 = (u - 1)(1 + u + u^2 ... u^(k-1)) = (a^x - 1)(...)
H.P.

The result above can be used to prove that:
gcd(a^m - 1, a^n - 1) = a^(gcd(m,n)) - 1

Proof:
Let gcd(m,n) = g
Then using Bezout's identity, there exist x,y such that
mx + ny = g

=> a^g = a^mx.a^ny____________[1]

Also, since g divides m and n
a^g - 1 divides a^m - 1 and a^n - 1
So a^g -1 is a common divisor.
Now we need to prove that it is greatest common divisor.


Let gcd(a^m - 1, a^n - 1) = D
Then
a^m - 1 mod D = 0
=>
a^m = 1 mod D and
a^n = 1 mod D

=>
(a^m)^x = 1 mod D and
(a^n)^y = 1 mod D

=> a^g = 1 mod D using [1]
=> D divides (a^g -1)

So D divides (a^g -1) which is a common divisor of (a^m - 1) and (a^n - 1) while D is their gcd.
GCD can divide a common divisor only if that common divisor is the gcd itself.
H.P.