Question

Ultilizando o algoritimo de euclides podemos concluir q o mdc (2¹ºº -1,2²º-1) é :

explique por favor

Answer 1

Pelo Algoritmo do MDC de Euclides, temos que:

 

$\text{mdc}(2^{100}-1, 2^{20}-1)=\text{mdc}(2^{20}-1, 2^{100}-1-(2^{20}-1)\times2^{80}$

 

$=\text{mdc}(2^{20}-1, 2^{80}-1)=\text{mdc}(2^{20}-1, 2^{80}-1-(2^{20}-1)\times2^{60}$

 

$=\text{mdc}(2^{20}-1, 2^{60}-1)=\text{mdc}(2^{20}-1, 2^{60}-1-(2^{20}-1)\times2^{40}$

 

$=\text{mdc}(2^{20}-1, 2^{40}-1)=\text{mdc}(2^{20}-1, 2^{40}-1-(2^{20}-1)\times2^{20}$

 

$=\text{mdc}(2^{20}-1, 2^{20}-1)=\text{mdc}(2^{20}-1, 2^{20}-1-(2^{20}-1)$

 

$=\text{mdc}(2^{20}-1, 0)=2^{20}-1$

 

Logo, chegamos à conclusão de que:

 

$\text{mdc}(2^{100}-1, 2^{20}-1)=2^{20}-1$