Re: Alguem pode ajudar?

["Ecass Dodebel" <ecassdodebel@xxxxxxxxxxx>]

>From: "nautilus" <titular@nautilus.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>Subject: Alguem pode ajudar?
>Date: Tue, 1 Aug 2000 18:25:47 -0300
>
>Não consigo fazer os dois exercícios abaixo sobre divisores positivos de um
>inteiro, será que alguém poderia me ajudar?. Acredito que sejam até 
>bastante
>parecidas as suas soluções, pois os enunciados são similares.
>
>1) Demonstrar que existem infinitos inteiros positivos n tais que a
>quantidade de divisores positivos que tem 2^n - 1  é maior que n.
>
>2) Seja d(n) o número de divisores positivos de um inteiro positivo n
>(incluindo 1 e n).
>Sejam  a > 1  e  n > 0  inteiros tais que  a^n + 1  é um primo.
>Prove que  d(a^n - 1) >= n.
>
>

Olá Nautilus,

demorou para alguém responder a sua mensagem, mas aí vai a solução que eu 
encontrei para a sua questão. Vou usar # para indicar soma, para que todos 
possam ler, e MDC(a,b) para indicar o maior divisor comum a "a" e "b". Vou 
por etapas (1,2,...) e depois trato dos seus problemas.

1) Se a>1 e n,m>0 inteiros, então MDC(a^n - 1,a^m - 1)=a^MDC(n,m) - 1
Demonstração.
Supondo m > n, temos
MDC(a^n - 1,a^m - 1) =
MDC(a^n - 1,a^(m-n)*(a^n - 1) # a^(m-n) - 1) =
MDC(a^n - 1,a^(m-n) - 1) =
De forma que se (m-n) > n reaplicamos o processo até (pela divisão 
euclidiana m = qn # r, com r<n)
MDC(a^n - 1,a^(m-qn) - 1) =
MDC(a^n - 1,a^r - 1) =
Ressalto que MDC(m,n)=MDC(n,r). Fazendo o mesmo processo, para n > r, vendo 
que pela divisão euclidiana n = pr # r', veremos que
MDC(a^r' - 1,a^r - 1)
Ressalto novamente que MDC(n,r)=MDC(r,r'). Repetindo o processo, claramente 
estamos tratando do precesso de obtenção do MDC de Euclides, veremos que
MDC(a^n - 1,a^m - 1)=
MDC(a^MDC(m,n) - 1,a^0 - 1) = a^MDC(m,n) - 1

2) Se a>1 e n,m>0 inteiros, então MDC(a^(2^n) # 1,a^(2^m) # 1) = 1
Demonstração.
Vemos primeiramente que
MDC(a # 1,a - 1) = MDC((a - 1) + 2, (a - 1) = MDC(a - 1,2)
Ou seja, se a é par, MDC(a # 1,a - 1)=1; se a é ímpar MDC(a # 1,a - 1)=2.
Já que 2^(2^n) é par
MDC(2^(2^n) # 1, 2^(2^n) - 1)=1
E ainda
2^(2^n) - 1 = (2 - 1)(2 # 1)(2^2 # 1)...(2^(2^(n-1)) # 1)
Donde tiramos que 2^(2^n) # 1 não tem nenhum fator comum com os números da 
forma 2^(2^m) # 1 com m<n, o que conclui a demonstração.

3) Se a>1 e n>0 e a^n # 1 é primo, então n é uma potência de 2.
Escrevendo n=p*2^m, onde p é impar, temos
a^n # 1 = (a^(2^m))^p # 1 = (a^(2^m))^p - (-1)^p = X^p - Y^p
É fácil de ver que X - Y divide X^p - Y^p, de forma que a^n # 1 não é primo, 
e portanto p deve ser igual a 1, e n uma potência de 2.

Agora vamos aos problemas.
Problema 2.
Se a^n # 1 é primo, escrevemos n=2^m por (3), e
a^(2^m) - 1 = (a - 1)(a # 1)...(a^(2^(m-1)) # 1)
De forma que todos esses fatores (os m últimos) são primos entre si, por 
(2), e maiores que 1, logo cada um contribui com pelo menos 1 número primo 
para a^(2^m) - 1, o número de divisores é dado por (1#i1)...(1#ik) para as 
potências iq dos primos, donde d(a^(2^m) - 1)>= (1#1)...(1#1) = 2^m.

Problema 1.
Tomamos n=2^m
2^(2^m) - 1 tem 2^m divisores ou mais, pelo problema 2.

Obrigado!

Eduardo Casagrande Stabel.

PS. o (1) que eu inclui no meu e-mail é inútil para o problema, mas acabei 
conseguindo prová-lo pensando que era necessário para resolver a questão, já 
que é relacionado ao assunto e é bastante conhecido, eu inclui.

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com