Question

Find the HCF of 2^120-1 and 2^100-1

Answer 1

There may be more brilliant solution than the following, but here are my thoughts.

We make use of Euclid's algorithm to help us out.
Consider finding the hcf of A=2^(n+x)-1 and B=2^(n)-1.

If we repeated subtract B from A until the difference C is less than B (smaller number), the hcf between A and B is the same as the hcf between B and C.

For example, we would subtract 2^x times B from A, or
C=A-2^xB=2^(n+x)-2^x(2^n-1)=2^(n+x)-2^(n+x)+2^n-1=2^n-1
By the Euclidean algorithm, 
hcf(A,B)=hcf(B,C)=hcf(2^n-1,2^x-1)
If n is a multiple of x, then by repetition, we will end up with
hcf(A,B)=hcf(2^x-1,2^x-1)=2^x-1

For the given example, n=100, x=20, so
HCF(2^120-1, 2^100-1)=2^(120-100)-1=2^20-1=1048575
(since n=6x, a multiple of x).