O
-ésimo número de Mersenne é
.
(a) Mostre que se
é primo então
é primo.
(b) (Teorema de Euclides sobre números perfeitos)
Um número natural
é perfeito se
é igual à soma de seus divisores positivos próprios (isto é , diferentes de
).
Por exemplo,
Mostre que se
é primo e
é primo então o número
é perfeito.
(a) Mostre que se
(b) (Teorema de Euclides sobre números perfeitos)
Por exemplo,
Passo 1
Vamos organizar o que o enunciado pede e quais informações temos, com calma. Temos definido o
-ésimo número de Mersenne por
O enunciado tem duas partes:
(a) Mostrar que: se
é primo então
é primo.
(b) Mostrar (Teorema de Euclides): se é primo e
é primo então
(b) Mostrar (Teorema de Euclides): se
é um número perfeito (ou seja, igual à soma de seus divisores próprios positivos).
Estas são as perguntas. As informações relevantes: definição de
; em (b) sabe-se que
e
são primos. Não há outras figuras ou tabelas.
Passo 2
Prova de (a): ideia básica e contrapositive. Vou provar a contrapartida: se
não é primo (isto é,
é composto) então
não é primo (ou seja, é composto). Isso é equivalente ao enunciado e costuma ser mais direto.
Se
é composto, então existem inteiros
e
com
tais que
Agora use uma identidade algébrica bem conhecida: para qualquer
e inteiros
,
Isto é a fatoração de uma diferença de potências (pense em fator comum). Vou aplicar essa identidade com
.
Passo 3
Aplicando a identidade com
e
obtemos
Observe dois pontos importantes:
-
O primeiro fator
é maior que porque (já que ). De fato, se então . -
O segundo fator também é um inteiro maior do que
. É uma soma de termos positivos (cada termo pelo menos ), logo é .
Portanto
tem uma fatoração não-trivial, isto é, é composto. Isso mostra que se
é composto então
é composto. Tomando a contrária: se
for primo então não pode ser composto, logo
não é composto; portanto
é primo. Isso prova (a).
Exemplo rápido para intuição: com
temos
, composto.
Passo 4
Agora (b). Primeiro vamos lembrar o que é um divisor próprio e a ideia de soma dos divisores. Um divisor próprio positivo de um número
é qualquer divisor positivo de
diferente de
(por exemplo, para
os divisores próprios são
). Um número é perfeito se a soma de todos os seus divisores próprios é igual ao próprio número.
Queremos provar: se
é primo e
também é primo, então
é perfeito.
Vou proceder listando os divisores e calculando a soma deles. Para facilitar, uso que
e
são coprimos (explico por quê) e então os divisores de
são produtos dos divisores de cada fator.
Passo 5
Verificação de coprimalidade e estrutura dos divisores. Como
é ímpar (porque
é par), temos
. Quando dois inteiros
e
são coprimos, todo divisor de
é produto de um divisor de
por um divisor de
. Aqui:
- Os divisores positivos de
são exatamente . (Porque é uma potência de 2.) - Como
é primo, os divisores positivos de são apenas e .
Logo os divisores positivos de
são todos os produtos
com
e
. Em lista ordenada: os divisores são
Destes, o maior
é o próprio
; os demais são divisores próprios.
Passo 6
Cálculo da soma dos divisores (função
). Uma forma elegante é usar a multiplicatividade de
para fatores coprimos:
se
. Aqui, porém, vou fazer diretamente a soma com séries geométricas para ficar bem mastigado:
A soma de todas as potências de
de
até
é uma progressão geométrica:
Esta fórmula vem da soma de uma série geométrica com razão
. Sempre que temos
; aqui
e
.
Como os divisores de
são os que listei, a soma de todos os divisores de
(incluindo
próprio) é
Isto corresponde a somar os blocos "poderes de
" e "esses mesmos poderes multiplicados por
".
Passo 7
Agora substituo a soma geométrica e o fato de que
. Primeiro
E como
é primo,
Multiplicando:
Mas note que
. Então
Passo 8
A soma de todos os divisores de
(incluindo
stesso) é
. A soma dos divisores próprios é
. Portanto
Isto mostra precisamente que
é perfeito. Concluímos a parte (b).
Resposta
(a)
é primo.
(b) é perfeito.
(b)