Re: [obm-l] Divisibilidade

["Fábio \"ctg \\pi\" Dias Moreira" <fabio.dias.moreira@xxxxxxxxxxxx>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Em Sex 27 Jun 2003 01:32, Denisson escreveu:
> Alguém poderia demonstrar como se chegou aos critérios de divisibilidade?
> Em especial aos mais dificeis como o critério do 17. Não peço uma
> demonstração matemática formal, peço algum argumento lógico.
> [...]

Suponha que você quer o critério de divisibilidade por um primo m, inspirado 
na idéia de arrancar o úmtimo dígito do número. Suponha que n = 10a + b. 
Suponha que após arrancarmos o último dígito, ele seja multiplicado por c. 
Então o novo n, n', é a - bc. Se descobrirmos constantes x, y e z tais que

xn + yn' = mp (*)

onde p é uma função de a, b e c, e nem x nem y são múltiplos de m, então temos 
um critério de divisibilidade para m (se um dos termos do lado esquerdo for 
múltiplo de m, o outro também deve ser).

Exemplo: Seja m = 7. Então a equação (*) se escreve como

x(10a + b) + y(a - bc) = 7p

a(10x + y) + b(x - yc) = 7p

Basta encontar x, y e c tais que tanto 10x + y quanto x - yc sejam múltiplos 
de 7. Mas então 10x + y - 10*(x - yc) = y(1 + 10c) é múltiplo de 7. Mas y não 
é múltiplo de 7, logo 1 + 10c é múltiplo de 7. Um c pequeno que satisfaz isso 
é c = 2. Logo 10x + y e x - 2y são múltiplos de 7. Não é muito difícil achar 
um par que satisafaça isso (x=1 e y=4, por exemplo). Logo o critério de 
divisibilidade por 7 é arrancar o último dígito e subtrair o seu dobro do 
número restante.

Note que a escolha de x e y não importa. De fato, 10x + y = 0 e x - 2y = 0 são 
expressões equivalentes módulo 7, logo tomar y = 1 e x qualquer funciona.

Mas agora olhe para o problema no caso geral novamente. A equação (*) 
significa

a(10x + y) + b(x - yc) = mp

logo basta encontrar x, y, c tais que (10x + y) e (x - yc) sejam múltiplos de 
m, o que implica que 10x + y - 10*(x - yc) = y(1 + 10c) é múltiplo de m, o 
que implica que 1 + 10c é múltiplo de m. Armado de tal c, basta achar x e y 
tais que 10x + y e x - yc seja múltiplos de m. Mas x = c, y = 1 é uma solução 
automática.

Logo todo o problema se resume a achar tal c. Mas os múltiplos de m da forma 
10c + 1:

i) ou são positivos e terminam em 1
ii) ou são negativos e terminam em 9.

Logo, para descobrir um valor de c, basta listar os múltiplos de m até 
encontar o primeiro múltiplo que termine em 1 ou 9. Se ele for da forma xyz1, 
c = xyz. Se for da forma xyz9, c = -xyz - 1 (muito cuidado: um c negativo 
significa subtrair um múltiplo negativo do último dígito, i.e. você está 
*somando* um múltiplo do último dígito).

Exemplo: m = 13. Quais são os múltiplos de 13?

13, 26, *39*, 52, ...

Logo c = -3-1 = -4. Logo a regra de divisibilidade é arrancar o último dígito 
e somá-lo, multiplicado por 4, ao número restante.

(Tente isso com 13*246346356 = 3202502628)

Exemplo: m = 17. Quais são os múltiplos de 17?

17, 34, *51*, ...

Logo c = 5. Logo a regra de divisibilidade é arrancar o último dígito e 
subtraí-lo, multiplicado por 5, do número restante.

(Tente isso com 17*7612058 = 129404986)

Isso tem uma conseqüência legal: Achar a regra de divisibilidade por um primo 
m qualquer terminado em 1 ou 9 (i.e. 11, 31, 41, ..., 19, 29, 59, ...) é 
trivial.

[]s,

- -- 
Fábio "ctg \pi" Dias Moreira
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE+/HknalOQFrvzGQoRArKdAJ92brzRRBv1H6GBEQcmrttmOTKp+ACgoyh2
OXzZ5WKFDns2rqQWRpB9ugM=
=n1iC
-----END PGP SIGNATURE-----

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================