the question was to prove:

if m and n are positive integers and gcd(m, n) = d, then gcd(2^{n}- 1, 2^{m}- 1) = 2^{d}- 1.

my approach was the following:

given gdc(m,n) = d, the d|m and d|n also m = dp and n = dq for some integers p and q.

so, (2^{n}- 1, 2^{m}- 1) = (2^{dq}- 1, 2^{dp}- 1)

2^{dq}- 1 = 2^{d}- 1(2^{d(q-1)}+ 2^{d(q-2)}+...+ 2^{d}+ 1) = (2^{d}- 1)(s) for some integer s.

2^{dp}- 1 = 2^{d}- 1(2^{d(p-1)}+ 2^{d(p-2)}+...+ 2^{d}+ 1) = (2^{d}- 1)(t) for some integer t.

so (2^{d}- 1) is a divisor of (2^{n}- 1, 2^{m}- 1), however I do not know how to show that it is the gcd(2^{n}- 1, 2^{m}- 1) or how to show that

gcd(s,t) = 1.

my instructor suggested proof by induction showing true for m + n < s, then true for m + n = s. I can not see how to start the proof

using his suggestion. any help would be appreciated.