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