Mostre que o número (2^20) − 1 é divisível por 41.
Soluções para a tarefa
Resposta:
(2^20)-1=1048575
1048575:41=25575
Explicação passo-a-passo:
Resposta:
Explicação passo-a-passo:
Questão de conguência, bom vamos lá. Para ficar mais fácil note que:
2^20 - 1 pode ser expresso como (2^10)² - 1 ou seja é um produto notável, o produto da soma pela diferença, ou seja:
a² - b² = (a + b)*(a - b)
No nosso caso
a = 2^10
b = 1
Assim temos que
(2^10)² - 1 = (2^10 + 1)*(2^10 - 1)
Para que 41 divida 2^20 - 1 ele deve dividir 2^10 + 1 ou 2^10 - 1 se ele dividir uma das parcelas dividira 2^20 - 1
Para 2^10 - 1, temos
2^5 é 32
Logo 2^5 + 9 é divisivel por 41
Representamos da seguinte forma
2^5 ≡ -9 mod11
Elevando ao quadrado ambos os lados temos
(2^5)² ≡ (-9)² mod 41
2^10 ≡ 81 mod 41
Note que 81 é divisil por 41 e tem resto 40
2^10 ≡ 40 mod 41
Retirando 1 de ambos os membros
2^10 - 1 ≡ 40 - 1 mod 41
2^10 - 1 ≡ 39 mod 41
Logo 2^10 quando divisivel por 41 tem resto 39
Para 2^10 + 1, temos:
Analogo ao o anterior
2^5 ≡ -9 mod 41
(2^5)² ≡ (-9)² mod 41
2^10 ≡ 81 mod 41
2^10 ≡ 40 mod 41
2^10 + 1 ≡ 40 + 1 mod 41
2^10 + 1 ≡ 41 mod 41
Note que 41 é divisivel por 41 e tem resto 0, portanto
2^10 + 1 ≡ 0 mod 41
Logo 2^10 + 1 é divisivel por 41, então 2^20 - 1 também é divisivel por 41