+26367 Using the Euclidian Algorithm, calculate \(\gcd(2^{60}-1, 2^{80}-1)\)
Formula: \( \boxed{ \gcd(a,b) = \gcd(b,a) \\~\\ \gcd(a,b) = \gcd(a-n*b,b) \\~\\ \gcd(a,a) = a }\)
\(\begin{array}{|rcll|} \hline && \mathbf{\gcd\left( 2^{60}-1,~ 2^{80}-1 \right)} \\ &=& \gcd\left( 2^{80}-1,~ 2^{60}-1 \right) \\ && \begin{array}{|rcll|} \hline 2^{80}-1 &=& 1+2+2^2+2^3+\ldots+2^{79} \\ 2^{60}-1 &=& 1+2+2^2+2^3+\ldots+2^{59} \\ \hline 2^{20}*(2^{60}-1) &=& 2^{20}+2^{21}+\ldots+2^{79} \\ \hline \mathbf{ (2^{80}-1)-2^{20}*(2^{60}-1)} &=& \mathbf{1+2+2^2+2^3+\ldots+2^{19}} \\ \mathbf{ (2^{80}-1)-2^{20}*(2^{60}-1)} &=& \mathbf{2^{20}-1} \\ \hline \end{array} \\ &=& \gcd\left( (2^{80}-1)-2^{20}*(2^{60}-1),~ 2^{60}-1 \right) \\ &=& \mathbf{ \gcd\left( 2^{20}-1,~ 2^{60}-1 \right) } \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline && \mathbf{ \gcd\left( 2^{20}-1,~ 2^{60}-1 \right) } \\ &=& \mathbf{ \gcd\left( 2^{60}-1,~ 2^{20}-1 \right) } \\ && \begin{array}{|rcll|} \hline 2^{60}-1 &=& 1+2+2^2+2^3+\ldots+2^{59} \\ 2^{20}-1 &=& 1+2+2^2+2^3+\ldots+2^{19} \\ \hline 2^{40}*(2^{20}-1) &=& 2^{40}+2^{41}+\ldots+2^{59} \\ \hline \mathbf{ (2^{60}-1)-2^{40}*(2^{20}-1)} &=& \mathbf{1+2+2^2+2^3+\ldots+2^{39}} \\ \mathbf{ (2^{60}-1)-2^{40}*(2^{20}-1)} &=& \mathbf{2^{40}-1} \\ \hline \end{array} \\ &=& \gcd\left( (2^{60}-1)-2^{40}*(2^{20}-1),~ 2^{20}-1 \right) \\ &=& \mathbf{ \gcd\left( 2^{40}-1,~ 2^{20}-1 \right) } \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline && \mathbf{ \gcd\left( 2^{40}-1,~ 2^{20}-1 \right) } \\ && \begin{array}{|rcll|} \hline 2^{40}-1 &=& 1+2+2^2+2^3+\ldots+2^{39} \\ 2^{20}-1 &=& 1+2+2^2+2^3+\ldots+2^{19} \\ \hline 2^{20}*(2^{20}-1) &=& 2^{20}+2^{21}+\ldots+2^{39} \\ \hline \mathbf{ (2^{40}-1)-2^{20}*(2^{20}-1)} &=& \mathbf{1+2+2^2+2^3+\ldots+2^{19}} \\ \mathbf{ (2^{40}-1)-2^{20}*(2^{20}-1)} &=& \mathbf{2^{20}-1} \\ \hline \end{array} \\ &=& \gcd\left( (2^{40}-1)-2^{20}*(2^{20}-1),~ 2^{20}-1 \right) \\ &=& \mathbf{ \gcd\left( 2^{20}-1,~ 2^{20}-1 \right) } \\ &=& 2^{20}-1 \\ &=& \mathbf{1048575} \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline && \mathbf{\gcd\left( 2^{60}-1,~ 2^{80}-1 \right)} \\ &=& \mathbf{ \gcd\left( 2^{60}-1,~ 2^{20}-1 \right) } \\ &=& \mathbf{ \gcd\left( 2^{40}-1,~ 2^{20}-1 \right) } \\ &=& \mathbf{ \gcd\left( 2^{20}-1,~ 2^{20}-1 \right) } \\ &=& \mathbf{2^{20}-1} \\ &=& \mathbf{1048575} \\ \hline \end{array}\)
