ELEMENTOS: 046-Critérios de Divisibilidade

A questão de saber se um número inteiro $[;n;]$ é divisível ou não por um determinado número primo $[;p;]$ é 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 $[;n;]$ é divisível por um primo $[;p;]$ 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 $[;m;]$ .

Definição $[;1;]$ : Dois números $[;a;]$ e $[;b;]$ são congruentes módulo $[;m;]$ quando deixam o mesmo resto $[;0 \leq r < m;]$ quando divididos por $[;m;]$ .

Exemplo: $[;13;]$ e $[;24;]$ são congruentes módulo $[;11;]$ , porque deixam o mesmo resto na divisão por $[;11;]$ .

Simbolicamente, $[;a \equiv b;]$ ( $[;mod;]$ $[;m;]$ ) e lê-se: " $[;a;]$ é congruente a $[;b;]$ módulo $[;m;]$ ".

Quando $[;a;]$ não é congruente a $[;b;]$ módulo $[;m;]$ , escreve-se $[;a \not \equiv b;]$ ( $[;mod;]$ $[;m;]$ ).

De $[;a \equiv b;]$ ( $[;mod;]$ $[;m;]$ ), temos

$[;a=qm+r;]$

$[;b=q^'m+r;]$

Logo, $[;a-b=(q-q^')m;]$ e assim temos a

Definição $[;2;]$ : Dois números $[;a;]$ e $[;b;]$ são congruentes módulo $[;m;]$ quando $[;a-b;]$ for divisível por $[;m;]$ .

Com isso, temos uma outra maneira de dizer que um número é divisível por outro. Se $[;a;]$ é divisível por $[;b;]$ , então $[;a \equiv 0;]$ ( $[;mod;]$ $[;b;]$ ). De fato, pois, conforme a definição $[;2;]$ , $[;a-0;]$ é divisível por $[;b;]$ .

Se $[;a;]$ não for divisível por $[;b;]$ , temos então $[;a \not \equiv 0;]$ ( $[;mod;]$ $[;b;]$ ).

Disto decorre que , como $[;a \equiv b;]$ ( $[;mod;]$ $[;m;]$ ) indica que $[;a-b;]$ é divisível por $[;m;]$ , então $[;a-b \equi 0;]$ ( $[;mod;]$ $[;m;]$ ).

Estas equivalências $[;a \equiv b \Rightarrow a-b \equiv 0;]$ ( $[;mod;]$ $[;m;]$ ) lembram as operações com o sinal de igualdade. E é justamente esta a grande vantagem de se utilizar a relação de congruência ( $[;\equiv;]$ ): 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 $[;a \equiv b;]$ ( $[;mod;]$ $[;m;]$ ) e $[;b \equiv c;]$ ( $[;mod;]$ $[;m;]$ ), então $[;a \equiv c;]$ ( $[;mod;]$ $[;m;]$ )

E relativo as operações de adição algébrica e multiplicação, temos ainda:

Se $[;a \equiv b;]$ ( $[;mod;]$ $[;m;]$ ) e

$[;c \equiv d;]$ ( $[;mod;]$ $[;m;]$ ), então

$[;i);]$ $[;a \pm c \equiv b \pm d;]$ ( $[;mod;]$ $[;m;]$ );

$[;ii);]$ $[;ac \equiv bd;]$ ( $[;mod;]$ $[;m;]$ ).

Exercício resolvido: A divisão de $[;x+5;]$ por $[;7;]$ deixa resto $[;3;]$ . Qual o resto de $[; x;]$ por $[;7;]$ ?

Resolveremos de dois modos.

$[;1^a;]$ Resolução:

$[;x+5=7q+3 \Rightarrow;]$

$[;x=7q+3-5=7q-2 \Rightarrow;]$

$[;x=7q-(7-5) \Rightarrow;]$

$[;x=7(q-1)+5;]$

Resposta: o resto de $[; x;]$ por $[;7;]$ é $[;5;]$ .

$[;2^a;]$ Resolução

$[;\rightarrow;]$ $[;x+5;]$ por $[;7;]$ deixa resto $[;3;]$ ;

$[;\rightarrow;]$ Também $[;3;]$ por $[;7;]$ deixa resto $[;3;]$ .

$[;x+5 \equiv 3;]$ ( $[;mod;]$ $[;7;]$ ) $[;\Rightarrow;]$

$[;x \equiv 3-5 \equiv -2 \equiv 5;]$ ( $[;mod;]$ $[;7;]$ )

Resposta: o resto de $[; x;]$ por $[;7;]$ é $[;5;]$ .

Aqui, uma palavra sobre congruências módulo $[;m;]$ cujo segundo membro é negativo e com valor absoluto ( módulo algébrico ) menor que o módulo $[;m;]$ . Na $[;2^a;]$ resolução, quando temos $[; x \equiv -2;]$ ( $[;mod;]$ $[;7;]$ ), isto quer dizer que na divisão por excesso de $[; x;]$ por $[;7;]$ o resto é $[;-2;]$ . 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 $[;-2+7=5;]$ .

Um exemplo numérico. Na divisão por falta de $[;10;]$ por $[;7;]$ temos o quociente $[;q=1;]$ e resto $[;r=3;]$ . Já na divisão por excesso de $[;10;]$ por $[;7;]$ temos o quociente $[;q+1=2;]$ e resto $[;r^'=-4;]$ . Observem que $[;|r|+|r^'|=|3|+|-4|=7;]$ .

Este fato não tem maiores mistérios porque

$[;qd+r=(q+1)d+r^' \Rightarrow;]$

$[;r-r^'=|r|+|r^'|=(q+1)d-qd=d[(q+1)-q)]=d;]$

$[;\rightarrow;]$ Resumindo, se $[;a \equiv r;]$ ( $[;mod;]$ $[;m;]$ ) com $[;0 \leq |r| < m;]$ , então $[;r;]$ é o resto da divisão ( por falta ou por excesso ) de $[;a;]$ por $[;m;]$ . Quando isto acontece, dizemos que a congruência está reduzida.

No exercício resolvido, utilizamos a propriedade $[;i);]$ . Agora vamos utilizar a $[;ii);]$ para calcularmos o resto da divisão da potência $[;a^k;]$ por $[;m;]$ , se já sabemos o resto de $[;a;]$ por $[;m;]$ .

Seja $[;r_1;]$ o resto de $[;a;]$ por $[;m;]$ . Assim,

$[;a \equiv r_1;]$ ( $[;mod;]$ $[;m;]$ )

E por $[;ii);]$ , obtemos,

$[;a^2 \equiv r_1.r_1 \equi r_2;]$ ( $[;mod;]$ $[;m;]$ )

com $[;0 \leq |r_2| < m;]$

( congruência reduzida )

Continuando,

$[;a^2 \equiv r_2;]$ ( $[;mod;]$ $[;m;]$ )

$[;a \equiv r_1;]$ ( $[;mod;]$ $[;m;]$ )

$[;\Rightarrow a^3 \equi r_2r_1 \equi r_3;]$ ( $[;mod;]$ $[;m;]$ ),

com $[;0 \leq |r_3| < m;]$

( congruência reduzida )

Por indução sobre estes resultados, temos

$[;a^{k-1} \equiv r_{k-1};]$ ( $[;mod;]$ $[;m;]$ )

$[;a \equiv r_1;]$ ( $[;mod;]$ $[;m;]$ )

$[;\Rightarrow a^k=r_{k-1}.r_1 \equi r_ k;]$ ( $[;mod;]$ $[;m;]$ ) ,

com $[;0 \leq |r_k| < m;]$

( congruência reduzida )

Se deixássemos para reduzir a congruência apenas no final, seria como

$[;a^k \equiv r_1^k \ \equiv r_k;]$ ( $[;mod;]$ $[;m;]$ )

Exercício Resolvido: Sabendo que na divisão $[;31/8;]$ temos o resto $[;r_1=7;]$ , calcule o resto da divisão $[;31^4/8;]$ .

Resolução:

$[;31 \equi 7;]$ ( $[;mod;]$ $[;8;]$ ) $[;\Rightarrow;]$

$[;31^2 \equi 7.7 \equiv 49 \equi 1;]$ ( $[;mod;]$ $[;8;]$ ) $[;\Rightarrow;]$

$[;31^3 \equiv 1.7 \equiv 7;]$ ( $[;mod;]$ $[;8;]$ ) $[;\Rightarrow;]$

$[;31^4 \equiv 7.7 \equiv 49 \equiv 1;]$ ( $[;mod;]$ $[;8;]$ )

Resposta: O resto da o resto da divisão $[;31^4/8;]$ é $[;r_4=1;]$ .

Critério Geral de Divisibilidade ( Fórmula Matriz )

Para fins de fatoração, trataremos apenas dos critérios relativo à um divisor primo.

Seja $[;r_i;]$ o resto da divisão de $[;10^i;]$ por $[;p;]$ , de forma que

$[;10=q_1p+r_1;]$ ou $[;10 \equiv r_1;]$ ( $[;mod;]$ $[;p;]$ )

$[;10^2=q_2p+r_2;]$ ou $[;10^2 \equiv r_2;]$ ( $[;mod;]$ $[;p;]$ )

$[;10^3=q_3p+r_3;]$ ou $[;10^3 \equiv r_3;]$ ( $[;mod;]$ $[;p;]$ )

$[;..................................................................;]$

$[;10^i=q_ip+r_i;]$ ou $[;10^i \equiv r_i;]$ ( $[;mod;]$ $[;p;]$ )

$[;..................................................................;]$

Considere o número $[;n;]$ escrito na base decimal $[;n=a_0+a_1.10+a_2.10^2+...+a_k10^k;]$ .

Seja, também, o número $[;t;]$ definido pela igualdade $[;t=a_0+a_1r_1+a_2r_2+...+a_kr_k;]$ .

Portanto,

$[;n-t=a_1(10-r_1)+a_2(10^2-r_2)+...+a_p(10^k-r_k);]$

Como $[;10^i-r_i=q_ip;]$ , o segundo membro é divisível por $[;p;]$ .Assim,

$[;n-t=qp \Rightarrow n \equiv t;]$ ( $[;mod;]$ $[;p;]$ )

ou seja, $[;n;]$ e $[;t;]$ deixam o mesmo resto quando divididos por $[;p;]$ . Este é o fundamento do

$[;\rightarrow;]$ Critério Geral de Divisibilidade: o número $[;n=a_0+a_1.10+a_2.10^2+...+a_k10^k;]$ será divísivel pelo primo $[;p;]$ quando

$[;t=a_0+a_1r_1+a_2r_2+...+a_kr_k;]$

também for. Os $[;a_i;]$ são os dígitos de $[;n;]$ na base $[;10;]$ e cada $[;r_i;]$ é o resto da divisão ( por falta ou excesso ) de $[;10^i;]$ por $[;p;]$ .

$[;\rightarrow;]$ 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 $[;p;]$ , em particular. Relativo ao inteiro $[;n=a_0+a_1.10+a_2.10^2+...+a_k10^k;]$ , vejamos

Divisão por $[;p=2;]$

$[;10^i \equiv 0;]$ ( $[;mod;]$ $[;2;]$ ) para qualquer $[;i;]$ . Temos então $[;r_1=r_2=...=r_k=0;]$ e

$[;t=a_0+0+0+...+0=a_0;]$

$[;>;]$ O número $[;n;]$ será divisível por $[;p=2;]$ quando seu ultimo dígito $[;a_0;]$ for divisível por $[;2;]$ ou seja, quando $[;a_0;]$ for $[;0;]$ , $[;2;]$ , $[;4;]$ , $[;6;]$ ou $[;8;]$ ( terminação em dígito par ).

Divisão por $[;p=3;]$

O resto da divisão de $[;10^1;]$ por $[;p=3;]$ é $[;r_1=1;]$ . Logo,

$[;10^1 \equiv 1;]$ ( $[;mod;]$ $[;3;]$ )

$[;10^2 \equiv 1.1=1;]$ ( $[;mod;]$ $[;3;]$ )

Assim, para qualquer $[;i;]$ , temos $[;10^i \equiv 1;]$ ( $[;mod;]$ $[;3;]$ ). O que resulta em $[;r_1=r_2=...=r_k=1;]$ e

$[;t=a_0+a_1.1+a_2.1+...+a_p.1=a_1+a_2+...a_k;]$

$[;>;]$ O número $[;n;]$ será divisível por $[;p=3;]$ quando a soma dos seus dígitos for divisível por $[;3;]$ .

Divisão por $[;p=5;]$

Um critério com justificativa semelhante ao primo $[;p=2;]$ .

$[;10^i \equiv 0;]$ ( $[;mod;]$ $[;5;]$ ) para qualquer $[;i;]$ . Temos então $[;r_1=r_2=...=r_k=0;]$ e

$[;t=a_0+0+0+...+0=a_0;]$

$[;>;]$ O número $[;n;]$ será divisível por $[;p=5;]$ quando seu ultimo dígito $[;a_0;]$ for divisível por $[;5;]$ ou seja, quando $[;a_0;]$ for $[;0;]$ ou $[;5;]$ .

Divisão por $[;p=7;]$

$[;10^1/7;]$ tem como resto $[;r_1=3;]$ .

$[;10 \equiv 3;]$ ( $[;mod;]$ $[;7;]$ ) $[;\Rightarrow;]$

$[;10^2 \equiv 3.3 \equiv 9 \equiv 2;]$ ( $[;mod;]$ $[;7;]$ ) $[;\Rightarrow;]$

$[;10^3 \equiv 2.3 \equiv 6;]$ ( $[;mod;]$ $[;7;]$ ) $[;\Rightarrow;]$

$[;10^4 \equiv 6.3 \equiv 18 \equiv 4;]$ ( $[;mod;]$ $[;7;]$ ) $[;\Rightarrow;]$

$[;10^5 \equiv 4.3 \equiv 12 \equiv 5;]$ ( $[;mod;]$ $[;7;]$ ) $[;\Rightarrow;]$

$[;10^6 \equiv 5.3 \equiv 15 \equiv 1;]$ ( $[;mod;]$ $[;7;]$ ) $[;\Rightarrow;]$

$[;10^7 \equiv 1.3 \equiv 3;]$

Aqui, o segundo membro da congruência começa a se repetir.

$[;>;]$ O número $[;n;]$ será divisível por $[;p=7;]$ quando

$[;t=a_0 + 3a_1+2a_2+6a_3+4a_4+5a_5+a_6+3a_7+...;]$

for divisível por $[;7;]$ .

Observem que todos os restos positivos por $[;7;]$ estão contidos na série periódica $[;(1,3,2,6,4,5,1,3,...);]$ cujos termos ( com exceção do primeiro ) foram obtidos nas congruências módulo $[;7;]$ com as potências de $[;10;]$ . 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 $[;n=459;]$ é divisível por $[;7;]$ , basta usar os três termos iniciais. Veja:

$[;t=9+3.5+2.4=32;]$ . Como $[;7;]$ não divide $[;t=32;]$ , também não dividirá $[;n=459;]$ .

Outro exemplo: Analisar $[;n=59661;]$ na divisão por $[;7;]$ . Temos, então

$[;t=1+3.6+2.6+6.9+4.5=105;]$ , por sua vez

$[;t^'=5+3.0+2.1=7;]$ , logo, $[;n=59661;]$ é divisível por $[;7;]$ .

$[;\rightarrow;]$ Neste critério, alguns autores preferem pegar as reduções negativas porque algumas possuem um menor módulo ( valor absoluto ). Observem:

$[;10 \equiv 3;]$ ( $[;mod;]$ $[;7;]$ )

$[;10^2 \equiv 2;]$ ( $[;mod;]$ $[;7;]$ )

$[;10^3 \equiv 6 \equiv -1;]$ ( $[;mod;]$ $[;7;]$ )

$[;10^4 \equiv 4 \equiv -3;]$ ( $[;mod;]$ $[;7;]$ )

$[;10^5 \equiv 5 \equiv -2;]$ ( $[;mod;]$ $[;7;]$ )

$[;10^6 \equiv 1;]$ ( $[;mod;]$ $[;7;]$ )

Então a fórmula parâmetro para o critério de $[;p=7;]$ fica

$[;t=a_0+3.a_1+2a_2-a_3-3a_4-2a_5+a_6+3a_7+...;]$

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 $[;p=11;]$ . Prossigamos.

Divisão por $[;p=11;]$

$[;10^1/11;]$ tem como resto $[;r_1=10;]$ .

$[;10 \equiv 10 \equi -1;]$ ( $[;mod;]$ $[;11;]$ )

$[;10^2 \equi (-1)(-1) \equi 1;]$ ( $[;mod;]$ $[;11;]$ )

$[;10^3 \equiv 1.(-1) \equiv -1;]$ ( $[;mod;]$ $[;11;]$ )

etc (alterna de $[;-1;]$ a $[;+1;]$ )

$[;>;]$ O número $[;n;]$ será divisível por $[;p=11;]$ quando

$[;t=a_0-a_1+a_2-a_3+...;]$

for divisível por $[;11;]$ .

Daí aquela regra que diz que um número é divisível por $[;11;]$ 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 $[;11;]$ .

Exercícios Propostos

$[;1);]$ Mostrar que um número é divisível por $[;4;]$ quando seu dígito da unidade somado com o dobro do dígito da dezena resultar em um número divisível por $[;4;]$ . ( verifique isso com por exemplo, $[;32;]$ e $[;38;]$ ).