[obm-l] Fwd: Divisibilidade ( Reply: Criterio de Divisibilidade) )

["Alexandre Augusto da Rocha" <arocha@xxxxxxxxxxxxxxxx>]

To forwarding pq nao achei link nos arquivos.

Enquanto procurava achei essa aki que tb trata do assunto
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200103/msg00101.html


----- Original Message -----
From: "F�bio "ctg \pi" Dias Moreira" <fabio.dias.moreira@terra.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Friday, June 27, 2003 12:04 PM
Subject: Re: [obm-l] Divisibilidade


> -----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
> =========================================================================
>


=========================================================================
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
=========================================================================