Question

(Aritmética: Um critério de divisibilidade por 17)

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

a) Mostre que

     se $a+8b\equiv r~~\mathrm{(mod~}17),$ então $100a+b\equiv (- 2)r~~\mathrm{(mod~}17).$

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.​

Answer 1

a)

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

b) Veja que $5466919 + 1 = 5466920$. 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:

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

$54668 = 100 \cdot 546 + 68\\a = 546\\b = 68\\54668 \equiv -2(546 + 8 \cdot 68)\pmod{17}\\54668 \equiv -2(546)\pmod{17}$

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

Retornando:

$54668 \equiv -2(546)\pmod{17}\\54668 \equiv -2(2)\pmod{17}\\54668 \equiv -4\pmod{17}$

$5466919 \equiv -2(54668) \pmod {17}\\5466919 \equiv -2(-4) \pmod {17}\\5466919 \equiv 8 \pmod {17}$

Se 5466919 deixa resto 8, 5466920 deixa resto 9.

Logo:

$5466919 + 5466920 \equiv 8 + 9 \pmod {17}\\5466919 + 5466920 \equiv 17 \pmod {17}\\5466919 + 5466920 \equiv 0 \pmod {17}$