Re: HSC 2014 4U Marathon - Advanced Level
On the last page you never provrd that if a is relatively prime to b then 2^a -1 is relatively prime to 2^b -1. All u did was prove that if a divides b then 2^a-1 divides 2^b-1.I'll prove the stronger result that
for positive integers a and b. Note that if this is true, then any common factor of your two quantities must also be a common factor of two distinct primes, and hence can only be 1.
The part was proven in the last page of this marathon. I'll show the other direction now.
We can write b=aq+r uniquely, with q,r non-negative integers and
If , then from the result.
So .
But since the LHS is odd, it is coprime to any power of 2. So we get
As the RHS is strictly less than the LHS, this is only possible if the RHS is 0. Ie r=0, which means that as claimed.