[obm-l] Divisibilidade por um primo

[Carlos Eddy Esaguy Nehab <carlos@xxxxxxxxx>]

Oi, gente,

Em 22/dez  Palmerim postou um m�todo curioso para divisibilidade por 
7 e  dois dias depois, Salhab  o justificou.

Agora que surgiu tempo ai vai o resultado de minha navegada pela 
internet (onde se encontra, naturalmente o problema proposto pelo 
Palmerim em http://www.pims.math.ca/pi/current/page30-30.pdf  e um 
crit�rio geral para divisibilidade por um primo arbitr�rio (procurei 
na nossa lista e n�o encontrei a discuss�o que se segue; desculpem-me 
se j� rolou tal discuss�o e eu n�o percebi).  H� v�rios sites 
interessantes mas o mais objetivo que encontrei e simples para a 
garotada � http://www.egge.net/~savory/maths1.htm.

� importante lembrar que h� v�rios m�todos para divisibilidade por 7, 
um m�todo para divisibilidade por 7, 11 e 13, que usa o fato de 7 x 
11 x 13 = 1001, um m�todo do Gustavo Gerald Toja Frachia (Instituto 
de Matem�tica da USP) citado na Wikipedia e tamb�m no link
http://www.cut-the-knot.org (um de meus sites preferidos).

Ai vai um resumo para facilitar a vida dos mais jovens, em portugu�s 
:-) de http://www.egge.net/~savory/maths1.htm.

Seja N um inteiro, r seu �ltimo d�gito e M o n�mero formado pelos 
algarismos anteriores (por exemplo, se N = 3249, ent�o r = 9 e M = 324).

a) Exemplo preliminar: divibilidade 17
N � divis�vel por  17  se e somente (sss)   M - 5r  tamb�m � divis�vel por 17.

Exemplos:   a | b significa a divide b
17 | 2343  sss 17 | ( 234  - 5x3)  sss 17 | 219 sss  17 | 21 - 5x9 
sss 17 |  -24; logo, 2343 n�o � divis�vel por 17, pois 17 n�o divide -24;
17 |  15912 sss 17 | (1591 - 5x2)  ss 17 |  1581 sss  17 | (158 - 
5x1)   sss   17 |  153  sss 17|  (15 - 5x3)  sss 17 | 0; logo, 17 | 15912

� interessante observar que este m�todo possui uma quantidade de 
passos proporcional ao n�mero de algarismos de N.

b) Caso geral
Se p � primo, seja q o menor m�ltiplo positivo de p terminado em 1 ou 
9  (observe que no caso p = 17  tem-se q = 51).

O crit�rio geral �:
i) Se o �ltimo d�gito de q = 1:  p | N  sss p |  M -  ar , onde a � o 
n�mero que sobra de q quando tiramos o 1 (no caso de 17, o 5);
ii) Se o �ltimo d�gito de q = 9:  p | N  sss p |  M +  (a+1) r , onde 
a � o n�mero que sobra de q quando tiramos o 9;

Veja a tabela abaixo, onde indicamos nesta ordem, o primo p, o valor 
de q,  o valor de a e a propriedade...
p	q	a	p | N sss p divide...
7  	21	1    	M - 2r
11	11	1	M - r
13 	39 	3	M + (3+1)r   = M + 4r
17	51	5	M - 5r
23  	69	6	M + (6+1)r  = M + 7r
29	29	2	M + (2+1)r = M + 3r
31	31	3	M - 3r
37	111	11	M - 11r
41	41	4	M - 4r
43	129	12	M + 13r
47	141	14	M  - 14r
...

A demonstra��o geral � simples mas � interesante para a turma mais 
jovem fazer a demonstra��o de um dos casos particulares (p = 13 ou 
17, etc). Finalizando, exibo um outro crit�rio de divisibilidade por 
7 para n�meros maiores que 1000 que utiliza menos passos que o 
crit�rio anterior:..
Seja N > 1000 e  escrevamos N como (R.S) onde S � o n�mero formado 
pelos 3 �ltimos d�gitos de N e R o numero formado pelos anteriores a 
eles (por exemplo, se N = 3245123  ent�o R = 3245 e S = 123.  O 
crit�rio � trivial e a demonstra��o, simples:  7 | N  sss 7 | R - S

Seria interessante investigar a generaliza��o deste crit�rio para 
outros primos....

Abra�os,
Nehab

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