[Aritmética: Teoria dos Números – Números Naturais – Congruência modular – Sistema de numeração decimal – Critérios de divisibilidade]
Seja [tex]n_0=10a_0+b_0[/tex] um número natural cujo algarismo das unidades é [tex]b_0.[/tex]
A partir deste, efetuamos o seguinte processo:
Removemos o algarismo das unidades de [tex]n_0,[/tex] e do número formado pelos algarismos restantes, subtraímos o dobro do algarismo das unidades de [tex]n_0.[/tex] O resultado será um novo número natural [tex]n_1.[/tex]
O processo acima é repetido sempre sobre o último resultado obtido, até que não seja mais possível efetuar a subtração nos naturais.
a) Escreva a sequência dos resultados obtidos a partir do número [tex]n_0=34673.[/tex]
b) Considere que, a partir de um natural [tex]n_0[/tex] desconhecido o processo descrito foi repetido por 47 vezes, e o último resultado obtido foi [tex]n_{47}=17.[/tex] Com essas informações, calcule o resto da divisão de [tex]n_0[/tex] por 7.
a) A sequência dos resultados obtidos a partir do número [tex]n_0=34673[/tex] é: 3461, 344, 26.
b) O resto da divisão de [tex]n_0[/tex] por 7 é 1.
Vamos ver por quê.
Interpretação
Primeiramente, precisamos compreender o algoritmo descrito e tentar traduzi-lo em uma relação algébrica de recorrência.
Nosso ponto de partida é o número [tex]n_0[/tex], cujo algarismo das unidades é representado por [tex]b_0[/tex].
Para encontrarmos o próximo número ([tex]n_1[/tex]), correspondente à primeira iteração ([tex]t=1[/tex]), precisamos remover o algarismo das unidades do número inicial. Em outras palavras, temos que subtraí-lo deste e dividir o resultado por 10. Isto é:
[tex]n_1=\frac{n_0-b_0}{10}[/tex]
Em seguida, subtraímos o dobro do algarismo das unidades original ([tex]b_0[/tex]).
A inequação (condição) acima é necessária para interromper o algoritmo, cujas etapas devem ser repetidas "... até que não seja mais possível efetuar a subtração nos naturais."
Aplicação para 34673 (item A)
Utilizando a fórmula geral definida, fazemos, para [tex]n_0=34673[/tex] e [tex]b_0=3[/tex]:
Como [tex]26 < 21.6=126[/tex], interrompemos a execução do processo e concluímos que os resultados obtidos a partir de 34673 são 3461, 344 e 26.
Resto do número desconhecido (item B)
Aqui, precisaremos fazer algumas análises de congruência.
Comecemos dizendo que o número inicial [tex]n_0[/tex], cujo algarismo das unidades é representado por [tex]b_0[/tex], apresenta resto [tex]r[/tex] na divisão por 7. Isto é:
[tex]n_0\equiv r \:(mod\:7)\:\:\:\:\:\:\:\:\:(ii)[/tex]
De [tex](i)[/tex] sabemos que, para [tex]t = 1[/tex]:
[tex]10n_1=n_0-21b_0[/tex]
Reescrevendo [tex](ii)[/tex] para trazer [tex]n_1[/tex]:
[tex]n_0-21b_0\equiv r-21b_0 \:(mod\:7)[/tex]
[tex]10n_1\equiv r-7.3b_0 \:(mod\:7)[/tex]
[tex]10n_1\equiv r \:(mod\:7)\:\:\:\:\:\:\:(iii)[/tex]
Temos aqui uma relação interessante. O número obtido após a primeira iteração, multiplicado por dez, apresenta o mesmo resto na divisão por 7 que o número original. Vamos ver o que acontece se continuarmos replicando essa lógica.
De [tex](i)[/tex] sabemos que, para [tex]t = 2[/tex]:
[tex]10n_2=n_1-21b_1[/tex]
Reescrevendo [tex](iii)[/tex] para trazer [tex]n_1[/tex]:
[tex]10(10n_2+21b_1)\equiv r\:(mod\:7)[/tex]
[tex]100n_2+210b_1\equiv r\:(mod\:7)[/tex]
[tex]100n_2+7.30b_1\equiv r\:(mod\:7)[/tex]
[tex]100n_2\equiv r\:(mod\:7)[/tex]
Perceba que temos um padrão aqui. A cada iteração [tex]t[/tex]do algoritmo, o resto da divisão por 7 se mantém inalterado quando o último número gerado ([tex]n_t[/tex]) é multiplicado por [tex]10^t[/tex]. Ou seja:
Portanto, pela transitividade das congruências, afirmamos a partir de [tex](ii)[/tex]:
[tex]n_0\equiv 1 \:(mod\:7)[/tex]
Ou seja, o número desconhecido [tex]n_0[/tex] deixa resto 1 na divisão por 7.
Curiosidade
O algoritmo proposto nesta questão costuma ser utilizado como método para detecção de divisibilidade por 7. Veja só:
Suponha que estejamos lidando com um múltiplo de 7 da forma [tex]n_0=7k\:,\:k \in \mathbb{N}[/tex].
Claramente, teremos:
[tex]n_0\equiv 0 \:(mod\:7)[/tex]
Ao fazermos a primeira iteração:
[tex]10n_1=n_0-21b_0[/tex]
[tex]10n_1=7k-21b_0[/tex]
[tex]10n_1=7(k-3b_0)[/tex]
Percebemos que o número resultante também é múltiplo de 7, e esse padrão se repete até o fim da aplicação do processo. Ou seja, o último número obtido, que resulta bem menor e mais simples que os anteriores, também será múltiplo de 7 caso o número inicial (de interesse) seja. Muito útil para determinar a divisibilidade de números grandes e/ou de difícil operacionalização manual.
Lista de comentários
Verified answer
Resposta:
a) A sequência dos resultados obtidos a partir do número [tex]n_0=34673[/tex] é: 3461, 344, 26.
b) O resto da divisão de [tex]n_0[/tex] por 7 é 1.
Vamos ver por quê.
Interpretação
Primeiramente, precisamos compreender o algoritmo descrito e tentar traduzi-lo em uma relação algébrica de recorrência.
Nosso ponto de partida é o número [tex]n_0[/tex], cujo algarismo das unidades é representado por [tex]b_0[/tex].
Para encontrarmos o próximo número ([tex]n_1[/tex]), correspondente à primeira iteração ([tex]t=1[/tex]), precisamos remover o algarismo das unidades do número inicial. Em outras palavras, temos que subtraí-lo deste e dividir o resultado por 10. Isto é:
[tex]n_1=\frac{n_0-b_0}{10}[/tex]
Em seguida, subtraímos o dobro do algarismo das unidades original ([tex]b_0[/tex]).
[tex]n_1=\frac{n_0-b_0}{10}-2b_0[/tex]
Sintetizando:
[tex]n_1=\frac{n_0-21b_0}{10}[/tex]
De forma mais geral:
[tex]n_t=\frac{n_{t-1}-21b_{t-1}}{10} \:,\:t\in \mathbb{N}^*\:,\:n_{t-1}\geq 21b_{t-1}\:\:\:\:\:\:\:\:\:(i)[/tex]
A inequação (condição) acima é necessária para interromper o algoritmo, cujas etapas devem ser repetidas "... até que não seja mais possível efetuar a subtração nos naturais."
Aplicação para 34673 (item A)
Utilizando a fórmula geral definida, fazemos, para [tex]n_0=34673[/tex] e [tex]b_0=3[/tex]:
[tex]n_1=\frac{34673-21.3}{10} =\frac{34673-63}{10} =\frac{34610}{10} =3461\:,\:b_1=1[/tex]
[tex]n_2=\frac{3461-21.1}{10} =\frac{3461-21}{10} =\frac{3440}{10} =344\:,\:b_2=4[/tex]
[tex]n_3=\frac{344-21.4}{10} =\frac{344-84}{10} =\frac{260}{10} =26\:,\:b_3=6[/tex]
Como [tex]26 < 21.6=126[/tex], interrompemos a execução do processo e concluímos que os resultados obtidos a partir de 34673 são 3461, 344 e 26.
Resto do número desconhecido (item B)
Aqui, precisaremos fazer algumas análises de congruência.
Comecemos dizendo que o número inicial [tex]n_0[/tex], cujo algarismo das unidades é representado por [tex]b_0[/tex], apresenta resto [tex]r[/tex] na divisão por 7. Isto é:
[tex]n_0\equiv r \:(mod\:7)\:\:\:\:\:\:\:\:\:(ii)[/tex]
De [tex](i)[/tex] sabemos que, para [tex]t = 1[/tex]:
[tex]10n_1=n_0-21b_0[/tex]
Reescrevendo [tex](ii)[/tex] para trazer [tex]n_1[/tex]:
[tex]n_0-21b_0\equiv r-21b_0 \:(mod\:7)[/tex]
[tex]10n_1\equiv r-7.3b_0 \:(mod\:7)[/tex]
[tex]10n_1\equiv r \:(mod\:7)\:\:\:\:\:\:\:(iii)[/tex]
Temos aqui uma relação interessante. O número obtido após a primeira iteração, multiplicado por dez, apresenta o mesmo resto na divisão por 7 que o número original. Vamos ver o que acontece se continuarmos replicando essa lógica.
De [tex](i)[/tex] sabemos que, para [tex]t = 2[/tex]:
[tex]10n_2=n_1-21b_1[/tex]
Reescrevendo [tex](iii)[/tex] para trazer [tex]n_1[/tex]:
[tex]10(10n_2+21b_1)\equiv r\:(mod\:7)[/tex]
[tex]100n_2+210b_1\equiv r\:(mod\:7)[/tex]
[tex]100n_2+7.30b_1\equiv r\:(mod\:7)[/tex]
[tex]100n_2\equiv r\:(mod\:7)[/tex]
Perceba que temos um padrão aqui. A cada iteração [tex]t[/tex] do algoritmo, o resto da divisão por 7 se mantém inalterado quando o último número gerado ([tex]n_t[/tex]) é multiplicado por [tex]10^t[/tex]. Ou seja:
[tex]10^t.n_t\equiv r\:(mod\:7)\:\:\:\:\:\:\:(iv)[/tex]
Com a congruência geral descrita em [tex](iv)[/tex], podemos aplicar [tex]t=47[/tex] como determinado pela questão e fazer:
[tex]10^{47}.n_{47}\equiv r\:(mod\:7)[/tex]
[tex]10^{47}.17\equiv r\:(mod\:7)[/tex]
[tex][(10^6)^7.10^5].(7.2+3)\equiv r\:(mod\:7)[/tex]
[tex]1^7.10^5.3\equiv r\:(mod\:7)[/tex]
[tex]1.5.3\equiv r\:(mod\:7)[/tex]
[tex]r\equiv 15\:(mod\:7)[/tex]
[tex]r\equiv 1\:(mod\:7)[/tex]
Portanto, pela transitividade das congruências, afirmamos a partir de [tex](ii)[/tex]:
[tex]n_0\equiv 1 \:(mod\:7)[/tex]
Ou seja, o número desconhecido [tex]n_0[/tex] deixa resto 1 na divisão por 7.
Curiosidade
O algoritmo proposto nesta questão costuma ser utilizado como método para detecção de divisibilidade por 7. Veja só:
Suponha que estejamos lidando com um múltiplo de 7 da forma [tex]n_0=7k\:,\:k \in \mathbb{N}[/tex].
Claramente, teremos:
[tex]n_0\equiv 0 \:(mod\:7)[/tex]
Ao fazermos a primeira iteração:
[tex]10n_1=n_0-21b_0[/tex]
[tex]10n_1=7k-21b_0[/tex]
[tex]10n_1=7(k-3b_0)[/tex]
Percebemos que o número resultante também é múltiplo de 7, e esse padrão se repete até o fim da aplicação do processo. Ou seja, o último número obtido, que resulta bem menor e mais simples que os anteriores, também será múltiplo de 7 caso o número inicial (de interesse) seja. Muito útil para determinar a divisibilidade de números grandes e/ou de difícil operacionalização manual.