# Thread: On GCDs and power's of 2

1. ## On GCDs and power's of 2

This is based on a earlier post on this forum only. Following lemma was used to solve a problem posted earlier - http://www.mathhelpforum.com/math-he...rs-155363.html

$(m,n) =1 \implies (2^m-1,2^n-1) = 1$

My question how do I prove this?

I have made an attempt but am stuck at this -

Given - Let m,n be any +ve integers. If a proposition is true for m and n then following holds true
1. proposition is true for (m+n)
2. proposition is true for (m-n), provided (m-n)>0

Claim - Proposition is true for all
am + bn, provided (am + bn) > 0, where a,b are any intergers (not necessarily >0)

How do I prove my claim? Some sort of induction?

2. Please ignore - I got it.

Here is an outline of my approach

I proved that if $k|2^m-1$ and $k|2^n-1$ => $k|2^{m+n}-1$ and $k|2^{m-n}-1$
Thus $k|2^{am+bn} - 1$ => k|2-1

Thanks

3. Can you please explain why k|2^am+bn - 1 and the next step (=> k|2-1). I already know why k|2^m+n -1 and why k|2^m-n -1 but I don't know what to do next.

4. Hint -

1. If k|2^m+n -1 and k|2^m - 1 then k|2^(2m)+n -1 and so on.....
2. am + bn = 1 so k|2^am+bn - 1 => k|2-1 => k = 1