A questão de saber se um número inteiro
Existem os chamados critérios de divisibilidade que permitem saber se um número
Todos os critérios tradicionais são derivados de uma fórmula matriz comum e o objetivo do presente trabalho é justificar o porque desta matriz funcionar e, ainda, exemplificar com alguns casos particulares.
Inicialmente, uma pequena revisão sobre congruências modulares. Operações de equivalência estão intimamente relacionadas com restos de uma divisão, seja por falta, ou por excesso.
Números congruentes módulo
.
Definição
Exemplo:
Simbolicamente,
Quando
De
( ![mod [;mod;]](http://thewe.net/tex/mod)
), temos
Logo,
e assim temos a
Definição
: Dois números
e
são congruentes módulo
quando
for divisível por
.
Com isso, temos uma outra maneira de dizer que um número é divisível por outro. Se
é divisível por
, então
(
). De fato, pois, conforme a definição
,
é divisível por
.
Se
não for divisível por
, temos então
( ![mod [;mod;]](http://thewe.net/tex/mod)
).
Disto decorre que , como
(![mod [;mod;]](http://thewe.net/tex/mod)
) indica que
é divisível por
, então
(![mod [;mod;]](http://thewe.net/tex/mod)
).
Estas equivalências
(![mod [;mod;]](http://thewe.net/tex/mod)
) lembram as operações com o sinal de igualdade. E é justamente esta a grande vantagem de se utilizar a relação de congruência (
): ela possui propriedades semelhantes da relação de igualdade (
) - ver artigo 048. Vamos mostrar apenas as mais importantes para este artigo.
Temos a propriedade transitiva:
E relativo as operações de adição algébrica e multiplicação, temos ainda:
(![mod [;mod;]](http://thewe.net/tex/mod)
), então
(![mod [;mod;]](http://thewe.net/tex/mod)
);
(![mod [;mod;]](http://thewe.net/tex/mod)
).
Exercício resolvido: A divisão de
por
deixa resto
. Qual o resto de
por
?
Resolveremos de dois modos.
Resolução:
Resolução
por
deixa resto
;
Também
por
deixa resto
.
(
)
(
)
![r-r^'=|r|+|r^'|=(q+1)d-qd=d[(q+1)-q)]=d [;r-r^'=|r|+|r^'|=(q+1)d-qd=d[(q+1)-q)]=d;]](http://thewe.net/tex/r-r%5E%27=%7Cr%7C+%7Cr%5E%27%7C=%28q+1%29d-qd=d[%28q+1%29-q%29]=d)
Resumindo, se
(![mod [;mod;]](http://thewe.net/tex/mod)
) com
, então
é o resto da divisão ( por falta ou por excesso ) de
por
. Quando isto acontece, dizemos que a congruência está reduzida.
Com isso, temos uma outra maneira de dizer que um número é divisível por outro. Se
Se
Disto decorre que , como
Estas equivalências
Temos a propriedade transitiva:
se
(![mod [;mod;]](http://thewe.net/tex/mod)
) e
(![mod [;mod;]](http://thewe.net/tex/mod)
), então
(![mod [;mod;]](http://thewe.net/tex/mod)
)
E relativo as operações de adição algébrica e multiplicação, temos ainda:
Se
(![mod [;mod;]](http://thewe.net/tex/mod)
) e
Exercício resolvido: A divisão de
Resolveremos de dois modos.
Resposta: o resto de
por
é
.
Resposta: o resto de
por
é
.
Aqui, uma palavra sobre congruências módulo
cujo segundo membro é negativo e com valor absoluto ( módulo algébrico ) menor que o módulo
. Na
resolução, quando temos
(
), isto quer dizer que na divisão por excesso de
por
o resto é
. Para transformar um resto em uma divisão por excesso em um resto em uma divisão por falta, basta somar o resto por excesso pelo divisor. De fato, pois
.
Um exemplo numérico. Na divisão por falta de
por
temos o quociente
e resto
. Já na divisão por excesso de
por
temos o quociente
e resto
. Observem que
.
Este fato não tem maiores mistérios porque
No exercício resolvido, utilizamos a propriedade
. Agora vamos utilizar a
para calcularmos o resto da divisão da potência
por
, se já sabemos o resto de
por
.
Seja
com
( congruência reduzida )
Continuando,
com
( congruência reduzida )
Por indução sobre estes resultados, temos
com
( congruência reduzida )
Se deixássemos para reduzir a congruência apenas no final, seria como
Exercício Resolvido: Sabendo que na divisão
temos o resto
, calcule o resto da divisão
.
Resolução:
Resposta: O resto da o resto da divisão
é
.
Critério Geral de Divisibilidade ( Fórmula Matriz )
Para fins de fatoração, trataremos apenas dos critérios relativo à um divisor primo.
Seja
o resto da divisão de
por
, de forma que
Considere o número
escrito na base decimal
.
Seja, também, o número
definido pela igualdade
.
Portanto,
Portanto,
Como
, o segundo membro é divisível por
.Assim,
ou seja,
e
deixam o mesmo resto quando divididos por
. Este é o fundamento do
Critério Geral de Divisibilidade: o número
será divísivel pelo primo
quando
Critérios Específicos de Divisibilidade ou, simplesmente, CRITÉRIOS DE DIVISIBILIDADE, são as adaptações do critério geral pela análise dos casos específicos frente a um divisor primo
, em particular. Relativo ao inteiro
, vejamos
(
) para qualquer
. Temos então
e
O número
será divisível por
quando seu ultimo dígito
for divisível por
ou seja, quando
for
,
,
,
ou
( terminação em dígito par ).
O número
será divisível por
quando a soma dos seus dígitos for divisível por
.
(
) para qualquer
. Temos então
e
O número
será divisível por
quando seu ultimo dígito
for divisível por
ou seja, quando
for
ou
.
tem como resto
.
também for. Os
são os dígitos de
na base
e cada
é o resto da divisão ( por falta ou excesso ) de
por
.
Divisão por ![p=2 [;p=2;]](http://thewe.net/tex/p=2)
Divisão por
O resto da divisão de
por
é
. Logo,
(![mod [;mod;]](http://thewe.net/tex/mod)
)
(![mod [;mod;]](http://thewe.net/tex/mod)
)
Assim, para qualquer
, temos
(![mod [;mod;]](http://thewe.net/tex/mod)
). O que resulta em
e
Divisão por
Um critério com justificativa semelhante ao primo
.
Divisão por
Aqui, o segundo membro da congruência começa a se repetir.
for divisível por
.
Observem que todos os restos positivos por
estão contidos na série periódica
cujos termos ( com exceção do primeiro ) foram obtidos nas congruências módulo
com as potências de
. No entanto, dependendo do número a ser analisado, não será necessário utilizar todos os termos.
Por exemplo, se queremos saber se o número
é divisível por
, basta usar os três termos iniciais. Veja:
Outro exemplo: Analisar
na divisão por
. Temos, então
Então a fórmula parâmetro para o critério de
fica
Eu, particularmente, prefiro o primeiro modo.
No entanto, estas reduções negativas nas congruências são ideais para o critério de divisibilidade para
. Prossigamos.
Divisão por ![p=11 [;p=11;]](http://thewe.net/tex/p=11)
tem como resto
.
(
)
(
)
(
)
O número
será divisível por
quando
Mostrar que um número é divisível por
quando seu dígito da unidade somado com o dobro do dígito da dezena resultar em um número divisível por
. ( verifique isso com por exemplo,
e
).
etc (alterna de
a
)
for divisível por
.
Daí aquela regra que diz que um número é divisível por
quando a soma de seus dígitos de ordem ímpar subtraído pela soma de seus dígitos de ordem par resultar em um número divisível por
.
Exercícios Propostos
_*_
Referência Bibliográfica
Teoria dos Números, de Salahoddim Shokranian, Marcus Soares e Hemar Godinho; Editora UNB, 1999.
O que é a Matemática?, de Richard Courant e Herbert Robbins, Editora Ciência Moderna, 2000.
Nenhum comentário:
Postar um comentário