Thread: 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



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?

Please help

Please ignore - I got it.

Here is an outline of my approach

I proved that if and => and
Thus => k|2-1

Thanks

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.

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