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