# Proof of integers

• December 9th 2009, 10:40 AM
lawrence.nelson49
Proof of integers
Let a,b and n be positive integers with n ≥ 2. Prove that:

gcd((n^a) - 1, (n^b) - 1)= n^(gcd(a,b)) - 1.

Help please!! I have no idea how to do this!
• December 10th 2009, 02:33 PM
qmech
A starting point might be similar to:
$
x^6-1 = (x^2-1)(x^4+x^2+1)
$

so if n = dk, with d = gcd(n,m)
$
x^n-1 = (x^d-1)(x^{d*(k-1)}+...)
$

and the same for m = dq
$
x^m-1 = (x^d-1)(x^{d*(q-1)}+...)
$