Question

(Aritmética: Outro critério de divisibilidade por 47)

Seja $n=100a+b$ um número natural, com a, b ∈ ℕ.

a) Mostre que se $a+8b\equiv r~~\mathrm{(mod~}47),$ então $100a+b\equiv 6r~~\mathrm{(mod~}47).$

b) A alínea anterior fornece um algoritmo para calcular o resto da divisão de qualquer número natural por 47. Utilizando este algoritmo, calcule resto da divisão de 2750422 por 47.

Obs.: Continuação do conteúdo abordado na tarefa

https://brainly.com.br/tarefa/53094048​

Answer 1

a)

$a + 8b \equiv r \pmod{47}\\100(a + 8b)\equiv 100r \pmod{47}\\100a + 100 \cdot 8b \equiv 100r \pmod{47}\\100a + (47 \cdot 2 + 6) 8b \equiv (47 \cdot 2 + 6) r \pmod{47}\\100a + 47 \cdot 2 \cdot 8b + 6 \cdot 8b \equiv 47 \cdot 2r + 6r\pmod{47}\\100a + 48b \equiv 6r\pmod{47}\\100a + (47 + 1)b\equiv 6r\pmod{47}\\100a + 47b + b \equiv 6r\pmod{47}\\100a + b \equiv 6r\pmod{47}$

b)

$2750422 = 100a + b\\2750422 = 100 \cdot 27504 + 22\\a = 27504\\b = 22$

Então:

$100a + b \equiv 6(a + 8b) \pmod {47}\\2750422 \equiv 6(27504 + 8 \cdot 22) \pmod {47}\\2750422 \equiv 6(27680) \pmod {47}$

27680 também pode ser reescrito:

$27680 = 100a + b\\27680 = 100 \cdot 276 + 80\\a = 276\\b = 80$

Logo:

$100a + b \equiv 6(a + 8b) \pmod {47}\\27680\equiv 6(276+ 8 \cdot 80) \pmod {47}\\27680\equiv 6(916) \pmod {47}$

916 também pode ser reescrito...

$916 = 100 \cdot 9 + 16\\a = 9\\b = 16\\\\916 \equiv 6(9 + 8 \cdot 16) \pmod {47}\\916\equiv 6(137) \pmod {47}\\916\equiv 6(43) \pmod {47}\\916 \equiv 3 \cdot 86 \pmod {47}\\916 \equiv 3 \cdot 39 \pmod {47}\\916 \equiv 117 \pmod {47}\\916 \equiv 23 \pmod {47}$

Retornando:

$27680\equiv 6(916) \pmod {47}\\27680\equiv 6 \cdot 23 \pmod {47}\\27680\equiv 2 \cdot 69 \pmod {47}\\27680\equiv 2 \cdot 22 \pmod {47}\\27680\equiv 44 \pmod {47}$

$2750422 \equiv 6(27680) \pmod {47}\\2750422 \equiv 6 \cdot 44 \pmod {47}\\2750422 \equiv 3 \cdot 88\pmod {47}\\2750422 \equiv 3 \cdot 41 \pmod {47}\\2750422 \equiv 123 \pmod {47}\\2750422 \equiv 29 \pmod {47}$

Portanto, 2750422 é congrente a 29, módulo 47.