Re: [obm-l] ajuda

["marcelo oliveira" <marcelo_rufino@xxxxxxxxxxx>]

>  Olá, gostaria de ajuda nestas 2 questões:

>1.Prove que existem infinitos nºs da forma 1999...9991 que são múltiplos de 
>1991.

Essa é da OBM de 1991.

Notemos que  1999...991 = 2000...00 – 9 = 2.10^(n + 1) – 9 = 2000.10^(n – 2) 
– 9   e que  1991 = 11.81
Assim, como  2000 == 9 (mod. 1991)   =>
1999...991 == 9(10^(n – 2) – 1) (mod. 1991).
Para que  1999...991  seja múltiplo de 1991, devemos ter:
9(10^(n – 2) – 1) == 0 (mod. 1991)   =>
10^(n – 2) == 1 (mod. 1991), uma vez que 9 e 1991 são primos entre si.
Sendo 181 e 10 primos entre si, pelo teorema de Fermat:
10^180 == 1 (mod. 181).
Analogamente, para 11 e 10:  10^10 == 1 (mod. 11)   =>   10^180 == 1 (mod. 
11).
Assim, temos que 10^180 – 1 é múltiplo de 181 e 11 e, portanto, múltiplo do 
mínimo múltiplo comum de 11 e 181, que é 1991.
Em outras palavras:  10^180 == 1 (mod. 1991).
Desta forma, para n = 182   =>
1999...991 == 0 (mod. 1991),  onde temos 182 números 9.
Como  10^(180k) == 1 (mod. 1991)  então  basta fazer   n – 2 = 180k   =>   n 
= 180k + 2  para que os números da forma 1999...991 (com n 9’s) sejam 
múltiplos de 1991.


>2.Prove que existem infinitos primos da forma 4k +3.

Esse é um problema clássico, tem em vários livros de olimpíadas e caiu na 
olimpíada da Espanha em 1992.

Suponhamos, por absurdo, que exista um número finito de primos da forma  pi 
= 4n – 1.
Seja o número  N = 4p1p2p3…pn – 1,  onde  pi  são todos os primos da forma  
4n – 1.
Notemos que  N  também é da forma  4n – 1 e é ímpar.
Fatorando em fatores primos N, temos que os primos que dividem N devem ser 
da forma  4n – 1  e  4n + 1.
Repare que:
(4n1 – 1)(4n2 – 1) = 4(4n1n2 – n1 – n2) + 1 = 4k + 1
(4n1 – 1)(4n2 + 1) = 4(4n1n2 + n1 – n2) – 1 = 4k – 1
(4n1 + 1)(4n2 + 1) = 4(4n1n2 + n1 + n2) + 1 = 4k + 1
Como  mdc (N, pi) = 1,  então  cada  pi  não divide N
Entretanto, na fatoração de N temos que ter fatores primos da forma  4n – 1, 
pois somente multiplicando um termo da forma  4n1 – 1 com outro da forma  
4n2 + 1  conseguimos um número da forma  4k – 1, que é a forma de N.
Assim, este fator primo de N da forma  4n – 1 deve ser distinto dos outros 
primos pi da forma 4n – 1, que é um absurdo, pois todos os primos da forma 
4n - 1 estão na expressão de N.


>Obrigada!
>  Fê
>

Até mais,
Marcelo Rufino de Oliveira

_________________________________________________________________
MSN Photos is the easiest way to share and print your photos: 
http://photos.msn.com/support/worldwide.aspx

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================