A questão de saber se um número inteiro é divisível ou não por um determinado número primo é de grande importância, pois a fatoração de um inteiro é o "DNA" do mesmo.
Existem os chamados critérios de divisibilidade que permitem saber se um número é divisível por um primo ou outro número qualquer, sem haver, para isto, a necessidade de operar efetivamente esta divisão.
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 : Dois números e são congruentes módulo quando deixam o mesmo resto quando divididos por .
Exemplo: e são congruentes módulo , porque deixam o mesmo resto na divisão por .
Simbolicamente, () e lê-se: " é congruente a módulo ".
Quando não é congruente a módulo , escreve-se ( ).
De ( ), 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 ( ).
Disto decorre que , como () indica que é divisível por , então ( ).
Estas equivalências ( ) 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:
Exercício resolvido: A divisão de por deixa resto . Qual o resto de por ?
Resolveremos de dois modos.
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 ( ).
Disto decorre que , como () indica que é divisível por , então ( ).
Estas equivalências ( ) 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:
se () e (), então ()
E relativo as operações de adição algébrica e multiplicação, temos ainda:
Se () e
(), então
();
().
Exercício resolvido: A divisão de por deixa resto . Qual o resto de por ?
Resolveremos de dois modos.
Resolução:
Resposta: o resto de por é .
Resolução
por deixa resto ;
Também por deixa resto .
( )
( )
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
Resumindo, se ( ) 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.
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 o resto de por . Assim,
( )
( )
E por , obtemos,
( )
com
( congruência reduzida )
( )
( ) ,
com
com
( congruência reduzida )
Continuando,
( )
( )
( ),
com
( ),
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
ou ( )
ou ( )
ou ( )
ou ( )
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
O número será divisível por quando seu ultimo dígito for divisível por ou seja, quando for ou .
Critério Geral de Divisibilidade: o número será divísivel pelo primo quando
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 .
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
Divisão 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 ( terminação em dígito par ).
Divisão por
O resto da divisão de por é . Logo,
O número será divisível por quando a soma dos seus dígitos for divisível por .
( )
( )
Assim, para qualquer , temos ( ). O que resulta em e
Divisão por
Um critério com justificativa semelhante ao primo .
( ) para qualquer . Temos então e
Divisão por
tem como resto .
( )
( )
( )
( )
( )
( )
Aqui, o segundo membro da congruência começa a se repetir.
O número será divisível por quando
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:
. Como não divide , também não dividirá .
Outro exemplo: Analisar na divisão por . Temos, então
, por sua vez
, logo, é divisível por .
Neste critério, alguns autores preferem pegar as reduções negativas porque algumas possuem um menor módulo ( valor absoluto ). Observem:
( )
( )
( )
( )
( )
( )
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
tem como resto .
( )
( )
( )
etc (alterna de a )
O número será divisível por quando
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
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 ).
_*_
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