sábado, 14 de julho de 2012

Regra de Divisibilidade Utilizando Escalonamento e Aritmética Modular

Adaptado de um trabalho do amigo Fernando Manso, da UFTPR – Campo Mourão

A proposta aqui é a construção de um algoritmo que sirva como regra de divisibilidade por escalonamento, utilizando aritmética modular. (Para saber mais sobre aritmética modular, clique aqui)

Seja j um número que queremos saber se é divisível por m . Definimos um sistema de congruência módulo m:

clip_image006

comclip_image008.

Ora, por que essa limitação? Logo veremos.

Seja k=ai, em representação decimal, tal que i seja o último dígito de . Façamos k=mn, geramos os valores de a como segue no exemplo: Seja m=17;

clip_image022

clip_image024

. E assim por diante, até

clip_image026

Assim, cada valor de m ao ser multiplicado por n gera um valor para k, que por sua vez define o valor de a. Para m=17, o quadro geral fica:

n(i)= 0      1 2   3   4 5 6   7 8 9

a(i)=17(0) 5 10 15 3 8 13 1 6 11

Definidos j e m, escalonamos j conforme segue:

clip_image043

clip_image045

clip_image047

Onde xn é jn desprezado o ultimo dígito.

Esse dígito i irá gerar a conforme definido acima. Esse valor a será utilizado na relação de congruência em n. Se obtivermos, no escalonamento, algum j=0, isto implica que j é divisível por m e são verdadeiras todas as congruências geradas. Caso contrário, j não é divisível por m e as congruências geradas não se verificam.

Ex: j=5984, m=17.

n(i)= 0 1 2 3 4 5 6 7 8 9

a(i)=17(0) 5 10 15 3 8 13 1 6 11

Suponhamos

clip_image059

Então

clip_image061

clip_image063

clip_image065

clip_image067

Poderíamos continuar com o algoritmo, mas agora sabemos que esta relação é óbvia.

Logo, j é divisível por m e são verdadeiras todas as relações de congruência. Assim,

clip_image069

clip_image071

clip_image073

Agora, por que esse método funciona?

Calma: comecemos respondendo à nossa pergunta inicial.

Para n>9, podemos decompor n como

clip_image075

Então, k vira

clip_image077

Agora, ao fazer  ai, teremos

clip_image081

Como tm é sempre divisível por m, podemos eliminar, pois queremos ai menor que m. Ou seja,

clip_image083

Logo, precisamos considerar apenas n de 1 a 9, pois os outros ai se repetem periodicamente.

Assim, para achar a, devemos escalonar k, diminuindo i e dividindo por 10:

clip_image085

Logo, como o único número i que geral ai=0 é 0, teremos que queremos j divisível por m. Assim,

clip_image087

Isso implica que, pela definição,

clip_image089

E, também, que

clip_image091

Mas, segundo a discussão já apresentada, podemos reduzir j, se este é múltiplo de m, a um número da forma algarismo vezes m na hora de escaloná-lo, pois “retiraremos” o algarismo da unidade. Entretanto, como vimos, ao definir xn, este deve ser congruente ao an resultante do escalonamento de jn, pois, pela nossa demonstração, há uma periodicidade na hora de analisar os an.. Logo, só teremos de repetir este processo o quanto quisermos para verificar que j é realmente divisível por m. Se, ao final, tivermos um resultado contraditório, mesmo se as contas intermediárias estiverem corretas, então o nosso início foi incorreto. Logo, j não é divisível por m.

Nenhum comentário:

Postar um comentário

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.

Related Posts Plugin for WordPress, Blogger...