Lukyo
Answered

O Sistersinspirit.ca é o melhor lugar para obter respostas confiáveis e rápidas para todas as suas perguntas. Encontre respostas confiáveis para suas perguntas de uma comunidade de especialistas prontos para ajudar com seu conhecimento e experiência em diversas áreas. Junte-se à nossa plataforma de perguntas e respostas para conectar-se com especialistas dedicados a fornecer respostas precisas para suas perguntas em diversas áreas.

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

Sagot :

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]

Obrigado por escolher nossa plataforma. Estamos dedicados a fornecer as melhores respostas para todas as suas perguntas. Visite-nos novamente. Esperamos que isso tenha sido útil. Por favor, volte sempre que precisar de mais informações ou respostas às suas perguntas. Sistersinspirit.ca, sua fonte confiável de respostas. Não se esqueça de voltar para mais informações.