Tower of 2's!

Let $(a,b)$ represents the greatest common divisor of $a$ and $b$ .

Theorem: $(2^a-1,2^b-1) = 2^{(a,b)}-1$

Assuming the theorem holds, we have $\begin{aligned}(2^{2^{100}-1}-1,2^{2^{105}-1}-1) &=& 2^{(2^{100}-1,2^{105}-1)}-1\nonumber\\ &=& 2^{2^{(100,105)}-1}-1\nonumber\\ &=& 2^{2^5-1}-1 \nonumber\\ &=& 2^{31}-1 \nonumber\\ &=& 2147483647\end{aligned}$ .

And so the last 3 digits are $647$ .

We are left to prove the theorem. We will prove the theorem using this following lemma:

Lemma: $m|n \Rightarrow 2^m-1 | 2^n-1$ (where $m|n$ denotes $n$ is divisible by $m$ )

Proof of lemma: Let $m=nk$ for some $k$ , and then we have $2^n-1 = \sum_{i=0}^{k-1} 2^{m(i+1)}-2^{mi} = \sum_{i=0}^{k-1} 2^{mi}(2^m-1)$ , which proves the lemma.

Now, the theorem can be proven by proving that each term divides the other.

Let $d = (2^a-1, 2^b-1)$ .

Since $(a,b)|a$ and $(a,b)|b$ , then we have $2^{(a,b)}-1 | 2^a-1$ and $2^{(a,b)}-1|2^b-1$ and therefore $2^{(a,b)}-1 | d$

Assume WLOG $a\geq b$ . Then we have $d | 2^a-1 - (2^b-1) = 2^b(2^{a-b}-1)$ . Since $d$ must be odd, $(d,2^b)=1$ and therefore $d|2^{a-b}-1$ . By induction it can be shown that $d|2^{a\%b}-1$ (where $a\%b$ denotes the remainder of $a$ when divided by $b$ ), and so by Euclid Algorithm, we have $d|2^{(a,b)}-1$ .

This completes the proof for the theorem, and hence the answer is $647$

It is obvious that $n^{\gcd(a,b)}-1|n^a-1$ and $n^{\gcd(a,b)}-1|n^b-1$ .

Lemma : $\gcd(n^a-1,n^b-1)= n^{\gcd(a,b)}-1$ .

Proof : Let $\gcd(a,b)= x$

If there is a natural number $y$ such that $y \cdot( n^x-1)|n^a-1$ and $y \cdot( n^x-1)|n^b-1$ . Then we have $n^a \equiv 1 \pmod{y \cdot( n^x-1)} \ldots(i)$

$n^b \equiv 1 \pmod{y \cdot( n^x-1)} \ldots(ii)$

By using Benzout Theorem, there are integers $p,q$ where $\gcd(p,q)=1$ such that $ap+bq=x$ . By $i$ and $ii$ then we have $n^{ap} \equiv 1 \pmod{y \cdot( n^x-1)}$ , and $n^{bq} \equiv 1 \pmod{y \cdot( n^x-1)}$ . Multiply both of them we get $n^{ap+bp} \equiv 1 \pmod{y \cdot( n^x-1)}$ $\Rightarrow n^x \equiv 1 \pmod{y \cdot( n^x-1)}$ , then $n^x-1 \equiv 0 \pmod{y \cdot( n^x-1)}.$ Because $n^x-1 \equiv 0 \pmod{y \cdot( n^x-1)}$ and $y$ is a natural number, then $y=1$ . So $\gcd(n^a-1,n^b-1)= n^{\gcd(a,b)}-1$ .
Back to the problem, by applying the lemma we get $\gcd(2^{2^{100}-1}-1,2^{2^{105}-1}-1)$ $=2^{\gcd(2^{100}-1,2^{105}-1}-1$ $=2^{2^{\gcd(100,105)}-1}-1$ $=2^{2^5-1}-1$ $=2^{31}-1$ $=2147483647.$ So, the answer is $647.$

Using Euclidean Algorithm this formula (forgot the name). $gcd(a^{m}-1,a^{n}-1) = a^{gcd(m,n)}-1$ ... Apply this formula we get...

• $gcd(2^{2^{100}-1}-1,2^{2^{105}-1}-1)$
• $= 2^{gcd(2^{100}-1,2^{105}-1)}-1$
• $= 2^{2^{gcd(100,105)}-1}-1$
• $= 2^{2^{5}-1}-1$
• $=2147483647$ .

Therefore, the last 3 digit is $\boxed{647}$ .

• PS: I'll find the proof of the formula later.

A property exists of the gcd such that $\gcd{\left(2^a-1,2^b-1\right)}=2^{\gcd{\left(a,b\right)}}-1$ . Applying this twice yields the gcd to be

${\gcd\left(2^{2^{100}-1},2^{2^{105}-1}-1\right)}=$ $2^{\gcd\left(2^{100}-1,2^{105}-1\right)}-1=$ $2^{2^{\gcd\left(100,105\right)}-1}-1=$ $2^{2^5-1}-1=$ $2^{31}-1$

Using the exponentiation by squaring method and only considering the last 3 digits of each multiplication, this is computed to be:

$2^{31}-1=$ $2(4^{15})-1=$ $8(16^7)-1=$ $128(256^3)-1=$ $768(536)-1=$ $647$

We have the following theorem: Let a, b, x, y \in \mathbb{N*} then we will have (a^x-1; a^y-1)=a^{(x; y)}-1 \\ (x; y) denotes the greatest common divisor of x and y Applying the previous theorem, we have (2^{2^{100}-1}-1}; 2^{2^{105}-1}-1})=2^{(2^{100}-1; 2^{105}-1)}-1=2^{(100; 105)}-1 The answer is 647

It is well-known that GCD(2^{m} - 1, 2^{n} - 1) = 2^{GCD(m, n)} - 1} (See this for the proof). So

$GCD(2^{2^{100} - 1} , 2^{2^{105} - 1}) = 2^{2^{5} - 1} - 1$ by repeated applications of the fact. So the last three digits is $\boxed{647}$

$GCD(a^n -1, a^m -1) = a^{GCD(n,m)} -1$

So, $GCD(2^{2^{100} -1}-1, 2^{2^{105} -1}-1) = 2^{GCD(2^{100}-1, 2^{105}-1)} -1\\ = 2^{2^{GCD(100, 105) }-1} -1 = 2^{2^{5}-1} -1 = 2^{31} -1$

Now it suffices to find $2^{31} -1 \bmod 1000$ , which is $647$

note that gcd(a^m-1,a^n-1)=a^gcd(m,n)-1,then gcd(2^(2^105-1)-1,2^(2^100-1)-1) = 2^gcd(2^105-1,2^100-1)-1 = 2^(2^gcd(105,100)-1)-1 =2^31-1 note 2^31 = (2^10)^3 2-1 = (24^3) 2-1 = 824*2-1 = 647 (mod 1000)

From the above identity we get $G.C.D.(2^{2^{100}-1}-1,2^{2^{105}-1}-1)$ $=2^{G.C.D(2^{100}-1,2^{105}-1)}-1$ But $G.C.D.(2^{100}-1,2^{105}-1)=2^{G.C.D.(100,105)}-1=2^5-1=31$ So our required G.C.D. is $2^{31}-1$ . Now $2^{31}-1 \equiv 2^{10}.2^{10}.2^{10}.2-1 \equiv 24.24.24.2-1 \equiv 648-1 \equiv 647 (\pmod 1000)$

We use $(x;y)$ to denote the greatest common divisor of x and y.

First we prove that for $a,b,m,n \in \mathbb{N^*}: (a^m - 1; a^n-1)=a^{(m;n)}-1 \ \ \ (*)$

Let $d=(m;n) \Rightarrow a^d -1 | a^m - 1; a^d - 1 | a^n-1$ . Hence $$a^d-1 | (a^m-1;a^n-1)\ \ \ (1)$$ Using Bezout's theorem, there exists $x,y \in N$ such that $xm - yn = d$ . Also, $a^m - 1 | a^{mx}-1 ; a^n - 1 | a^{ny}-1$

$\Rightarrow (a^m-1;a^n-1) | a^{mx}-a^{ny}=a^{ny}(a^d-1)$ . Hence $$(a^m-1;a^n-1) | a^d-1\ \ \ (2)$$ Since it's obvious that $(a^m-1;a^{ny}) = (a^n-1;a^{ny}) =1$ .

From (1) and (2) we have $(a^m-1;a^n-1) = a^d-1$ (QED)

Using (*), it is easy to see that $$(2^{2^{100}-1}-1; 2^{2^{105}-1}-1) = 2^{(2^{100}-1;2^{105}-1)}-1=2^{(100;105)}-1=2^5-1$$ Thus we need to evaluate the last three digits of $2^5-1$ , which is 647.

First we prove the lemma we use twice here, that is $gcd\left(a^m-1,a^n-1\right)=a^{\gcd(m,n)}-1$ It is fairly easy to prove. Let $m>n$ and $m=nq+r$ with $0\leq r<n$ . From Eulidean algorithm, we get $g=gcd\left(a^m-1,a^n-1\right)$ . Then, $g=gcd\left(a^n-1,a^m-a^n\right)=gcd\left(a^n-1,a^{nq}(a^{m-nq}-1)\right)$ . And since $gcd(a^n-1,a^{nq})=1$ , we have $G=gcd\left(a^n-1,a^r-1\right)$ . Now, again repeating the same process we find that, this only ends when we reach the greatest common divisor of $m,n$ . Hence, the claim. Now it is quite straight forward to prove. First, $gcd\left(2^{2^{100}-1}-1,2^{2^{105}-1}-1\right)=2^{\gcd\left(2^{100}-1,2^{105}-1\right)}-1$ Again, $\gcd\left(2^{100}-1,2^{105}-1\right)=2^{\gcd(100,105)}-1=2^5-1=31$ Therefore, $G=2^{31}-1=2147483647$ . So, the final answer is $\boxed{647}$ .

*Lemma: * For all positive integers $m$ and $n$ where $m>n$ , $\gcd (2^m - 1, 2^n - 1 )= \gcd (2^m-1, 2^{m-n}-1 )$
*Proof: * Note that both $2^m-1$ and $2^n-1$ are odd, so $\gcd (2^m-1, 2)= \gcd (2^n-1, 2)= 1$ . We then have: $\begin{array}{lcl} \gcd (2^m-1, 2^n-1) & = \gcd ( 2^n-1, 2^{m-n} ( 2^n - 1 ) ) \\ & = & \gcd (2^m-1, 2^m - 2^{m-n}) \\ & = & \gcd (2^m-1, 2^m -1 - (2^{m-n}-1) ) \\ & = & \gcd (2^m-1, 2^{m-n} - 1 ) \text{ (QED)} \\ \end{array}$

Now, let $m= qn+r$ , where $q, r$ are non-negative integers and $0 \leq r < n$ (Division algorithm). Repeated application of the lemma yields: $\begin{array}{lcl} \gcd (2^m-1, 2^n-1) & = & \gcd (2^{qn+r}-1, 2^n-1) \\ & = & \gcd (2^{qn+r}-1, 2^{(q-1)n+r}-1 ) \\ & = & \gcd (2^{qn+r}-1, 2^{(q-2)n+r}-1 ) \\ & = & \cdots \\ & = & \gcd (2^{qn+r}-1, 2^r-1 ) \end{array}$

Notice that by Euclidean algorithm, $\gcd (qn+r, n) = \gcd (qn+r, r)$ . Thus, if we continue applying this process, we will eventually find out that $\gcd (2^m-1, 2^n-1)= 2^{\gcd (m,n)} -1$ From this result, we find out that: $\gcd (2^{100}-1, 2^{105}-1)= 2^{\gcd (100, 105) - 1 }= 2^5- 1= 31$ $\gcd (2^{2^{100}-1}, 2^{2^{105}-1} ) = (2^{\gcd (2^{100}-1, 2^{105}-1) } - 1= 2^{31}-1$ So, it suffices to find the last three digits of $2^{31}-1$ . We have: $\begin{array}{lcl} 2^{31}-1 & = & 2 \times (1024)^3 - 1 \\ & \equiv & 2 \times 24^3 - 1 \pmod{1000} \\ & \equiv & 2 \times 824- 1 \pmod{1000} \\ & \equiv & 647 \pmod{1000} \end{array}$ We thus conclude our answer is $\boxed{647}$ .

Trivial problem.

It is well known fact that $gcd(a^n-1, a^m-1) = a^k-1$ where $k=gcd(n,m)$

So we know $gcd(2^{100}-1, 2^{105}-1) = 2^5-1 = 31$

So we know $gcd(2^{2^{100}-1}-1, 2^{2^{105}-1}-1) = 2^{31}-1$

And by simple calculation mod $1000$ the answer is $647$

It is easy to show $\text{gcd}(x^a-1, x^b-1)=x^{\text{gcd}(a, b)}-1$ . Applying this, we see the gcd is $2^k-1$ where $k=\text{gcd}(2^{100}-1, 2^{105}-1)$ . But we know this is $2^5-1=31$ , so the answer is $2^{31}-1$ which ends in $\boxed{647}$