quarta-feira, 30 de abril de 2014

DETALHES DA SEGUNDA REGRA MOURA VELHO

Esta postagem se destina a esclarecer detalhes sobre a segunda regra Moura Velho de divisibilidade por 7 apresentada em vídeo recente.


Mudando-se o que deve ser mudado, esta regra funciona também para a divisibilidade por 11 e 13.


ALGORITMOS

Esta regra funciona mediante a aplicação coordenada de dois algoritmos aos pares de dígitos de N, deslocando-se alternadamente da direita para a esquerda ou vice-versa. O resultado final (RF) é um número de dois dígitos; se 7|RF então 7|N. Ela utiliza o inverso aditivo módulo 7 que corresponde à diferença entre um dado número e o múltiplo de 7 imediatamente superior. A utilização da linguagem comum simplifica a aplicação da regra porque, por exemplo
─ 26 mod 7 ≡ 2 pode ser expresso da seguinte forma: 26 para 28 é igual a 2.


Algoritmo 1: N = abc.def
a’ ≡ ( ─ cd mod 7 + a ) mod 7, cd é eliminado (substituído por zeros) → a’b00ef


Algoritmo 2: N = a’b00ef
e’ ≡ ( ─ a’b mod 7 + e ), a’b também é eliminado (substituído por zeros) 0000e’f
Se 7|e’f (RF) então 7|N


PORQUE FUNCIONA

Algoritmo 1)


─ cd mod 7 ≡ 6cd; 6cd é incluído na casa do milhar resultando numa adição de 6.000 cd; como cd é eliminado, há uma subtração de 1cd; 6.000 cd ─ cd = 5.999 cd
Como 7|5.999, a operação realizada não altera o valor de N em módulo 7. Observar que, como cd é subtraído, dois dígitos nulos devem substituir esses dígitos.


Algoritmo 2)


Restringindo N a N = a’b00e temos que ─ a’b mod 7 ≡ 6a’b mod 7 que é adicionado ao dígito da unidade. Como a’b é eliminado (subtraído) e ocupa a casa do milhar há uma subtração de 1.000 a’b, ou seja, aplicação do algoritmo resulta na seguinte operação: ─ 1.000 a’b + 6a’b = ─ 994 a’b.


Como 7|994, a operação realizada não altera o valor de N em módulo 7, observando que a’b deve ser substituído por zeros.
Conclusão: A aplicação coordenada e repetitiva dos dois algoritmos reduz N a um número de dois dígitos, sem alterar o valor de N em módulo 7. Se 7|RF (resultado final) então 7|N.


COMO FUNCIONA


N = 675.934; ( ─ 59 mod 7 + 6 ) mod 7 ≡ 3; 370034; ( ─ 37 mod 7 + 3 ) mod 7 ≡ 1; 000014; 7|14 e 7|N


Para números maiores, deve ser efetuada a contagem dos pares de N (n), incluindo como par o eventual dígito isolado à esquerda e calcular: n mod 3; se n mod 3 ≡ 1, o procedimento se inicia com a aplicação do segundo algoritmo ao primeiro par de dígitos de N; Se n mod 3 ≡ 0 ou 2, o procedimento se inicia com a aplicação do primeiro algoritmo a partir do segundo par de dígitos de N.


Essa providência é adotada para garantir que N seja sempre reduzido a um número de dois dígitos.


Observação: Os cálculos podem ser efetuados mentalmente com extrema rapidez, sem a utilização de qualquer tipo de anotação. As anotações efetuadas têm a única finalidade de ilustrar a aplicação da regra.


Exemplo:


N = 43.816.248.324 → 4|38|16|24|83|24

A contagem do número de pares (n) incluindo como par o dígito isolado à esquerda é igual a 6.


n = 6; 6 mod 3 ≡ 0

O procedimento se inicia com a aplicação do primeiro algoritmo a partir do segundo par de dígitos.


( ─ 38 mod 7 + 0 ) 
 4; → 440016248324; ( ─ 44 mod 7 + 1 )  6;

→ 000066248324;
( ─ 66 mod 7 + 8 ) mod 7 ≡ 5; → 000000245324;

( ─ 53 mod 7 + 2 ) mod 7 ≡ 5; → 0000540024;

( ─ 54 mod 7 + 2 ) mod 7 ≡ 4; → 44; 7Ɨ44 e 7ƗN


DETERMINAÇÃO DO RESTO

A aplicação desta regra termina sempre no último ou no penúltimo par de dígitos. Se a aplicação terminar no último par de dígitos, para determinar o resto da divisão de N por 7, basta calcular: RF mod 7. Se terminar no penúltimo par, é necessário calcular: 2 . RF mod 7.


No caso de N = 43.816.248.234 a aplicação da regra terminou no último par de dígitos e o resultado final (RF) é igual a 44:

44 mod 7 ≡ 2 que é o resto da divisão de N por 7.


Exemplo adicional:


N = 129.325.634 → 1|29|32|56|34


( ─ 1 mod 7 + 3 ) mod 7 ≡ 2; 029225634;

( ─ 22 mod 7 + 2 ) mod 7 ≡ 1;
19005634; ( ─ 19 mod 7 + 5 ) mod 7 ≡ 0; 00000634;

( ─ 34 mod 7 + 0 ) mod 7 ≡ 1;


00001600; 7Ɨ16 e 7ƗN; 

Determinação do resto = ( 2 . 16 ) mod 7 ≡ 4; a aplicação da regra terminou no penúltimo par de dígitos, razão pela qual o resultado final foi multiplicado por 2 mod 7.
  

DETALHES DA TERCEIRA REGRA MOURA VELHO


Esta postagem se destina a esclarecer detalhes sobre a terceira regra Moura Velho de divisibilidade por 7 apresentada em vídeo.
Mudando-se o que deve ser mudado, esta regra funciona também para a divisibilidade por 13. Ela é uma variação da primeira regra Moura Velho de divisibilidade por 7 apresentada em meu primeiro vídeo (Youtube).

ALGORITMO

N = abc; abcy → 7|cy; S = ab + c + y; se 7|S então 7|N
O dígito "y" é inserido mentalmente depois do dígito "c" com o qual forma um número múltiplo de 7.
Este algoritmo deve ser aplicado repetitivamente a cada uma das classes de N. O inverso aditivo em módulo 7 de cada soma (S) deve ser adicionado ao número formado pelos dois dígitos iniciais da classe seguinte, antes de cada nova aplicação do algoritmo. Se 7|RF (resultado final) então 7|N. Se a classe inicial tiver menos de três dígitos o algoritmo deve ser aplicado parcialmente.

PORQUE FUNCIONA

Em 1 654 Pascal estabeleceu os seguintes multiplicadores em seu critério de divisibilidade por 7: ...31546231546231 que devem ser aplicados repetitivamente aos dígitos de um dado número. O número testado é divisível por 7 se a soma dos produtos obtidos também o for.

Todavia, se 7|N a soma dos produtos também é divisível por 7 se o dígito da unidade for multiplicado por qualquer outro multiplicador, desde que a ordem dos multiplicadores seja mantida. Se 7ƗN então a soma dos produtos será equivalente em módulo 7 ao valor do resto da divisão de N por 7 multiplicado pelo valor do multiplicador utilizado para a unidade. Isto ocorre porque os multiplicadores de Pascal se encontram em progressão geométrica em módulo 7.

De acordo com a tabuada em módulo 7 (assista o vídeo) que criei para desenvolver as regras Moura Velho de divisibilidade por 7 temos que: ab mod 7 ≡ ( 3a + 1b) mod 7 e que c + y ≡ 5c mod 7. Então os multiplicadores utilizados são 3, 1 e 5; e
S = 3a + 1b + 5c.
Então ─ S mod 7 ≡ 4a + 6b + 2c

Em um número maior a classe seguinte é def que submetida à aplicação do algoritmo resulta na seguinte soma de produtos:
S = 3d + 1e + 5f e o resultado da soma dos produtos obtida para ambas as classes é o seguinte: SP = 4a + 6b + 2c + 3d + 1e + 5f

A aplicação repetitiva e cumulativa do algoritmo com a intermediação do inverso aditivo de cada soma obtida resulta na aplicação repetitiva e alternada dos seguintes multiplicadores: ... 15462315462315

Isto significa que se 7|N então 7|SP e se 7ƗN então SP ≡ 5R mod 7 (R = resto)

COMO FUNCIONA

Os cálculos podem ser efetuados mentalmente com extrema rapidez. As anotações foram efetuadas apenas para ilustrar a aplicação da regra.

N = 293.526; 293(5).526(3)
29 + 3 + 5 = 37; ─ 37 mod 7 + 52 +  6 + 3 = 66; 7Ɨ66 e 7ƗN

N = 31.594.633; 31(4).594(2).633(5)
3 + 1 + 4 = 8; ─ 8 mod 7 + 59 + 4 + 2 = 71;
─ 71 mod 7 + 63 + 3 + 5 = 77; 7|77 e 7|N

DETERMINAÇÃO DO RESTO

Quando 7ƗN, conforme foi explicado, o resultado final (RF) é equivalente ao valor do resto multiplicado por 5. Como (3 . 5) mod 7 ≡ 1, para determinar o resto da divisão de N por 7 basta calcular: 3RF mod 7.

Para N = 293.526 o resultado final é igual a 66 e o cálculo do resto é (3 . 66) mod 7 ≡ 2 = resto da divisão de N por 7.

Exemplo adicional:

Para evitar números de mais de dois dígitos é útil expressar as dezenas de valor superior a 7 respectivamente: 7 por 0, 8 por 1 e 9 por 2, como no exemplo a seguir.

N = 823.951.634.223; 823(5).951(4).634(2).223(5)
12 + 3 + 5 = 20; ─ 20 mod 7 + 25 + 1 + 4 = 31;
─ 31 mod 7 + 63 + 4 + 2 = 73; ─ 3 mod 7 + 22 + 3 +5 = 34 = RF

Determinação do resto: ( 3 . 34 ) mod 7 ≡ 4 = resto da divisão de N por 7.


quarta-feira, 23 de abril de 2014



DETALHES DA PRIMEIRA REGRA MOURA VELHO

Esta postagem se destina a esclarecer detalhes sobre a primeira regra Moura Velho de divisibilidade por 7 mencionada em vídeo recente.
Geralmente as regras Moura Velho funcionam rapidamente através de simples e sucessivos cálculos mentais e dispensam a utilização de lápis e papel.
Mudando-se o que deve ser mudado, esta regra funciona também para a divisibilidade por 11 e 13.


ALGORITMO:

N = a.bcd; a’ ≡ ( ─ cd mod 7 + a ) mod 7; cd é eliminado, resultando em um número de dois dígitos a’b; se 7|a’b então 7|N
Esta regra é aplicada aos pares de dígitos de N da direita para a esquerda.


PORQUE FUNCIONA:


─ cd mod 7 ≡ 6cd; 6cd é incluído na casa do milhar resultando numa adição de 6.000 cd; como cd é eliminado, há uma subtração de 1cd; 6.000 cd ─ cd = 5.999 cd
Como 7|5.999 a operação realizada não altera o valor de N em módulo 7. Observar que, como cd é subtraído, dois dígitos nulos devem substituir esses dígitos.


COMO FUNCIONA:


N = 8.561; ( ─ 61 mod 7 + 8 ) mod 7 ≡ 3 → 35; 7|35 e 7|N
Para números mais extensos o algoritmo deve ser repetido com o deslocamento de a.bcd da direita para a esquerda até que o último dígito à esquerda seja alcançado. Eventualmente o último par à esquerda poderá estar incompleto; neste caso o dígito “a” assume o valor zero.
N = 69.218.683; ( ─ 83 mod 7 + 8 ) mod 7 ≡ 2; → 692126; ( ─ 26 mod 7 + 2 ) mod 7 ≡ 4; → 6941;( ─ 41 mod 7 + 6 ) mod 7 ≡ 0; → 09; 7Ɨ9 e 7ƗN


DETERMINAÇÃO DO RESTO:


1)      Contar o número de pares de dígitos (n), incluindo como par, o eventual par incompleto à esquerda.
2)      Aplicar a seguinte fórmula ao resultado final:


 (RF . 2(n-1) mod 3) mod 7


 
Para N = 69.218.683, n = 4 e RF = 9; (9 . 2(4─1) mod 3) mod 7 ≡ ( 9 . 20 ) mod 7 ≡ 2;
O resto da divisão de N por 7 é igual a 2.
 
Exemplo adicional:


N = 124.934.652; ( ─ 52 mod 7 + 4 ) mod 7 ≡ 1; → 1249316;
( ─ 16 mod 7 + 9 ) mod 7 ≡ 0; → 12403; ( ─ 3 mod 7 + 2 ) mod 7 ≡ 6; → 164;
( ─ 64 mod 7 + 0 ) mod 7 ≡ 6; → 61; 7Ɨ61 e 7ƗN
Determinação do resto: n = 5 e RF = 61; ( 61 . 2(5 ─ 1) mod 3 ) mod 7 ≡ (61 . 21) mod 7 ≡ 3
O resto da divisão de N por 7 é igual a 3.
 
Obs.: As anotações foram efetuadas somente para ilustrar a aplicação da regra; na prática elas são desnecessárias.