Mostre que: varphi(n)=n-1 Long<=ftrightarrow n é primo.
Resolucão: Rightarrow Vamos supor n não primo. Então n admite um divisor r, 1<r<n, e portanto mdc(n, r) simeq r>1. Assim, há pelo menos dois elementos em 1,2, ldots, n não primos com n : ren. Mas isto implica que varphi(n) é no máximo igual a n-2. Absurdo.

Passo 1

Resumindo, queremos mostrar que \r
varphi(n)=n-1iff n é primo,é \r
onde varphi(n) (função totiente de Euler) conta quantos inteiros k em 1,2,dots,n satisfazem gcd(k,n)=1.

Passo 2

Prova de que n primo impliesvarphi(n)=n-1. \r
Se n=p é primo, então todo k com 1<= k<p não admite nenhum divisor comum com p além de 1. Logo \r
gcd(k,p)=1 para k=1,2,dots,p-1, \r
enquanto gcd(p,p)=p>1. \r
Isso significa que, dos números 1,2,dots,p, exatamente os p-1 primeiros são coprimos com p. Portanto \r
varphi(p)=p-1

Passo 3

Prova de que varphi(n)=n-1implies n é primo. \r
Faremos a contrapartida: se n não é primo então varphi(n)<= n-2. \r
Como n não é primo, existe um divisor próprio r tal que \r
1<r<ne rmid n \r
Então \r
gcd(r,n)=r>1egcd(n,n)=n>1, \r
isto é, há pelo menos dois números em 1,2,dots,n r e n — que não são coprimos com n. \r
Logo, dentre os n inteiros de 1 a n, no máximo n-2 são coprimos com n, ou seja, \r
varphi(n)<= n-2< n-1 \r
Isso contradiz varphi(n)=n-1, mostrando que n não pode ser composto, logo deve ser primo.

Resposta

Mostramos que varphi(n)=n-1 ocorre exatamente quando n é primo.

Exercícios de Livros Relacionados