(Aritmética: Um critério de divisibilidade por 17)
Seja n = 100a + b um número natural, com a, b ∈ ℕ.
a) Mostre que
se [tex]a+8b\equiv r~~\mathrm{(mod~}17),[/tex] então [tex]100a+b\equiv (- 2)r~~\mathrm{(mod~}17).[/tex]
b) A alínea anterior fornece um algoritmo para calcular o resto da divisão de qualquer número natural por 17.
Sem efetuar a soma, calcule o resto da divisão de
5466919 + 5466920
por 17.
Seja n = 100a + b um número natural, com a, b ∈ ℕ.
a) Mostre que
se [tex]a+8b\equiv r~~\mathrm{(mod~}17),[/tex] então [tex]100a+b\equiv (- 2)r~~\mathrm{(mod~}17).[/tex]
b) A alínea anterior fornece um algoritmo para calcular o resto da divisão de qualquer número natural por 17.
Sem efetuar a soma, calcule o resto da divisão de
5466919 + 5466920
por 17.
More Questions From This User See All
Lista de comentários
Verified answer
a)
[tex]a + 8b \equiv r \pmod {17}\\100 (a + 8b)\equiv 100r \pmod {17}\\100a + 50 \cdot 16b\equiv 2 \cdot 50r \pmod {17}\\100a (-1)\cdot (-b)\equiv 2 \cdot (-1r) \pmod {17}\\100a + b \equiv -2r \pmod {17}[/tex]
b) Veja que [tex]5466919 + 1 = 5466920[/tex]. Portanto, o resto do segundo número é somente 1 maior que o do primeiro. Então só calcularei o do primeiro, para poupar esforços:
[tex]5466919 = 100 \cdot 54669 + 19\\a = 54669\\b = 19\\100a + b \equiv -2(a + 8b) \pmod {17}\\5466919 \equiv -2(54669 + 8 \cdot 19) \pmod {17}\\5466919 \equiv -2(54669 + 8 \cdot 2) \pmod {17}\\5466919 \equiv -2(54669 + 16) \pmod {17}\\5466919 \equiv -2(54669 -1) \pmod {17}\\5466919 \equiv -2(54668) \pmod {17}[/tex]
[tex]54668 = 100 \cdot 546 + 68\\a = 546\\b = 68\\54668 \equiv -2(546 + 8 \cdot 68)\pmod{17}\\54668 \equiv -2(546)\pmod{17}[/tex]
[tex]546 = 100 \cdot 5 + 46\\a = 5\\b = 46\\546 \equiv -2(5 + 8 \cdot 46) \pmod {17}\\546 \equiv -2(5 + 8 \cdot 12) \pmod {17}\\546 \equiv -2(5 + 4 \cdot 24) \pmod {17}\\546 \equiv -2(5 + 4 \cdot 7) \pmod {17}\\546 \equiv -2(5 + 28) \pmod {17}\\546 \equiv -2(5 + 11)\pmod {17}\\546 \equiv -2(16)\pmod {17}\\546 \equiv -2(-1)\pmod {17}\\546 \equiv 2\pmod {17}[/tex]
Retornando:
[tex]54668 \equiv -2(546)\pmod{17}\\54668 \equiv -2(2)\pmod{17}\\54668 \equiv -4\pmod{17}[/tex]
[tex]5466919 \equiv -2(54668) \pmod {17}\\5466919 \equiv -2(-4) \pmod {17}\\5466919 \equiv 8 \pmod {17}[/tex]
Se 5466919 deixa resto 8, 5466920 deixa resto 9.
Logo:
[tex]5466919 + 5466920 \equiv 8 + 9 \pmod {17}\\5466919 + 5466920 \equiv 17 \pmod {17}\\5466919 + 5466920 \equiv 0 \pmod {17}[/tex]