+0

# Help with Number Theory!

0
63
1

Using the Euclidian Algorithm, calculate

$$gcd(2^{60}-1, 2^{80}-1)$$

Jul 30, 2020

#1
+25543
+2

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}$$

Jul 31, 2020