Questão 3 (2 pontos)
Sejam m, n \in \mathbb{N}, tais que \operatorname{mdc}\{m, n\}=1. Prove que
m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 \quad \bmod m n .

Passo 1

O enunciado pede para provar que, para m,n\in\mathbb{N} com \gcd(m,n)=1,
m^{\varphi(n)} + n^{\varphi(m)} \equiv 1 \bmod m\,n.
O que vamos usar é o Teorema de Euler (se \gcd(a,N)=1, então a^{\varphi(N)}\equiv1\bmod N) e o Teorema Chinês do Resto (TCR).

Passo 2

Mostramos primeiro a congruência módulo m. Seja
S = m^{\varphi(n)} + n^{\varphi(m)}.
Note que m^{\varphi(n)}\equiv0\bmod m pois é múltiplo de m. Como \gcd(n,m)=1, o Teorema de Euler dá
n^{\varphi(m)}\equiv1\bmod m.
Somando, obtemos
S \equiv 0 + 1 \equiv 1 \bmod m.

Passo 3

De forma análoga, vemos a congruência módulo n. Agora
m^{\varphi(n)}\equiv1\bmod n
por Euler, já que \gcd(m,n)=1, e
n^{\varphi(m)}\equiv0\bmod n.
Logo
S \equiv 1 + 0 \equiv 1 \bmod n.

Passo 4

Como S\equiv1\bmod m e S\equiv1\bmod n e \gcd(m,n)=1, o Teorema Chinês do Resto garante
S \equiv 1 \bmod m\,n.

Resposta

m^{\varphi(n)} + n^{\varphi(m)} \equiv 1 \bmod m\,n.

Exercícios relacionados