Mostre que varphi(n) <= n-1.

Passo 1

Beleza, vamos lá! O enunciado pede para mostrarmos que varphi(n) <= n - 1. Estamos falando da função totiente de Euler, que conta quantos números de 1 até n são coprimos com n. Para resolver isso, vamos precisar entender o que significa dois números serem coprimos e como a função totiente funciona.

Passo 2

Primeiro, vamos entender o que é varphi(n). A função totiente de Euler, varphi(n), representa a quantidade de números naturais menores ou iguais a n que são coprimos com n. Dois números são coprimos se o único divisor comum deles é 1.

Passo 3

Agora, vamos observar que, no mínimo, o número 1 é sempre coprimo com qualquer n, já que o único divisor comum é 1. Portanto, varphi(n) é pelo menos 1.

Passo 4

Por outro lado, o número n não é coprimo consigo mesmo, porque n divide n e, portanto, têm pelo menos o divisor n em comum. Assim, entre 1 e n, o próprio n não está incluso em varphi(n).

Passo 5

Então, estamos contando os números de 1 até n-1 que são coprimos com n. Portanto, o máximo que varphi(n) pode ser é n-1, caso todos os números de 1 até n-1 sejam coprimos com n.

Passo 6

Isso significa que a função totiente nunca excede n-1, já que n nunca está incluído na contagem de números coprimos.

Resposta

Portanto, mostramos que varphi(n) <= n - 1 para todo número natural n.

Exercícios relacionados

Seja ( G, *) um grupo e a in G com |a|=n e n=r cdot s tal que (r, s)=1. Prove que existe um único par de elementos b, c in G tal que as condições abaixo são satisfeitas:
i) |b|=r e|c|=s
Prove que o inverso de m-1 in(Zm ^*,) é m-1.
Seja G um grupo cíclico de ordem n gerado por a. Prove que G tem varphi(n) geradores.
Enuncie o Teorema de Euler e dê aplicações.