bc1405 – A função de Euler e o Teorema de Euler

A função ${\varphi}$ de Euler associa a cada inteiro positivo ${n}$ a quantidade de inteiros positivos menores que ${n}$ que são coprimos com ${n}$

$\displaystyle \varphi(n):=\Big| \{a\in{\mathbb N} \colon \mathrm{mdc}(a,n)=1 \text{ e } 1\leq a\leq n \}\Big| \ \ \ \ \ (65)$

${n}$	1	2	3	4	5	6	7	8	9	10
${\varphi(n)}$	1	1	2	2	4	2	6	4	6	4

Decorre da definição que se ${p}$ é primo então ${\varphi(p) = p-1}$ . Para potências de primo temos que dentre ${1,2,\dots,p^k}$ não são coprimos com ${p^k}$ aquele que têm ${p}$ como fator primo, a saber ${p,2p,3p,\dots, p^{k-1}p}$ , portanto ${p^k - p^{k-1}}$ são os coprimos, isto é

$\displaystyle \varphi(p^k) = p^k - p^{k-1}= p^k\left(1-\frac 1p\right)$

A função ${\varphi}$ é multiplicativa

Teorema 36 Se ${n,m\in{\mathbb Z}^+}$ são coprimos então ${\varphi(nm)=\varphi(n)\varphi(m)}$ .

Demonstração: O caso ${m=1}$ ou ${n=1}$ é imediato. Sejam ${n,m>1}$ inteiros. Definimos os conjuntos

$\displaystyle \begin{array}{rcl} A&:=&\{a\in{\mathbb N} \colon \mathrm{mdc}(a,nm)=1 \text{ e } 1\leq a\leq nm \}\\ B&:=&\{b\in{\mathbb N} \colon \mathrm{mdc}(b,n)=1 \text{ e } 1\leq b\leq n \}\\ C&:=&\{c\in{\mathbb N} \colon \mathrm{mdc}(c,m)=1 \text{ e } 1\leq c\leq m \} \end{array}$

portanto o enunciado do teorema afirma que ${|A|= |B|\cdot |C|}$ . Vamos mostrar uma bijeção entre ${A}$ e ${B\times C}$ .

Seja ${a\in A}$ . Primeiro, vejamos que ${ (a\mod n,a\mod m)}$ pertence a ${B\times C}$ . Observemos que se ${a}$ é múltiplo de ${n >1}$ ou múltiplo de ${m>1}$ então ${\mathrm{mdc}(a,nm) >1}$ , o que contraria ${a\in A}$ , portanto ${ a\mod n\neq 0 \neq b\mod m}$ . Ainda

$\displaystyle \mathrm{mdc}(a,nm)=1 \Rightarrow \mathrm{mdc}(a,n)=1 \text{ e } \mathrm{mdc}(a,m)=1 \ \ \ \ \ (66)$

$\displaystyle \mathrm{mdc}(a \mod n,n) = \mathrm{mdc}(a,n)=1 \text{ e } \mathrm{mdc}(a \mod m,m) = \mathrm{mdc}(a,m)=1$

como sabemos do algoritmo de Euclides. Para provar (66) notemos que existem ${x, y\in{\mathbb Z}}$ tais que ${ax+nmy=1}$ donde temos que ${aX+nY=1}$ tem solução e ${aX+mY=1}$ tem solução, portanto, ${\mathrm{mdc}(a,n)=\mathrm{mdc}(a,m)=1}$ pelo corolário 22.

Com isso temos que a função ${f\colon A\rightarrow B}$ dada por

$\displaystyle f(a) = (a\mod n,a\mod m)$

está bem definida. Para provar o teorema, vamos mostrar que a função é uma bijeção.

Sejam ${a_1}$ e ${a_2}$ são elementos de ${A}$ . Se ${f(a_1)=f(a_2)}$ então ${a_1 \mod n = a_2 \mod n}$ e ${a_1 \mod m = a_2 \mod m}$ portanto

$\displaystyle \begin{array}{rcl} &a_1\equiv a_2 \pmod n \\ &a_1\equiv a_2 \pmod m \end{array}$

logo ${a_1\equiv a_2 \pmod {nm}}$ (veja o argumento no parágrafo anterior a equação (57)), e como ${1\leq a_1,a_2 \leq nm}$ temos ${a_1=a_2}$ . Portanto a função é injetiva. Resta provar que a função é sobrejetiva. Seja ${(b,c)}$ um elemento qualquer de ${B\times C}$ , isto é, ${1\leq b\leq n}$ , ${1\leq c \leq m}$ , ${\mathrm{mdc}(b,n)=1}$ e ${\mathrm{mdc}(c,m)=1}$ . Como ${\mathrm{mdc}(n,m)=1}$ o Teorema Chinês do Resto garante que há uma única solução ${a}$ módulo ${nm}$ para o sistema de congruências

$\displaystyle \begin{cases} X\equiv b \pmod n\\ X\equiv c \pmod m \end{cases}$

portanto ${(a\mod n,a\mod n) = (b,c)}$ , ademais, ${\mathrm{mdc}(a,nm)=1}$ pela recíproca de (66) (veja exercício 17, item 6). $\Box$

Exercício 47 Use indução (em ${k}$ ) para mostrar que se ${\mathrm{mdc}(n_i,n_j)=1}$ para todo ${i\neq j}$ então ${\varphi(n_1n_2\cdots n_k)=\varphi(n_1)\varphi(n_2)\cdots\varphi(n_k)}$ .

Agora, pelo exercício anterior, se ${n=p_1^{m_1}\cdots p_k^{m_k}}$ é a fatoração canônica de ${n}$ então ${\varphi(n) = \prod_{i=1}^k \varphi(p_i^{m_i}) = \prod_{i=1}^k p_i^{m_i}( 1 -1/p_i) = \prod_{i=1}^k p_i^{m_i} \prod_{i=1}^k (1-1/p_i) }$ ou seja,

$\displaystyle \varphi(n) = n \prod_{i=1}^k \left(1-\frac{1}{p_i}\right). \ \ \ \ \ (67)$

Exercício 48 Mostre que ${\varphi(n)=n-1}$ se e só se ${n}$ primo.

— Sistema completo de invertíveis (sci) —

Do conjunto ${R:= \{0,1,\dots,n-1\}}$ dos restos módulo ${n}$ , consideremos apenas os que são coprimos com ${n}$ , isto é, o subconjunto ${S:=\{r_1,r_2,\dots,r_{\varphi(n)}\}\subset R}$ de todos os restos ${r_i\in R}$ tais que ${\mathrm{mdc}(r_i,n)=1}$ . Como ${R}$ é um sistema completo de restos (scr) módulo ${n}$ , todo inteiro ${b}$ é côngruo a um, e só um, ${r\in R}$ ; agora, se ${b}$ é coprimo com ${n}$ então ${r\in S}$ : do Teorema de Euclides temos ${\mathrm{mdc}(n,b\mod n ) = \mathrm{mdc}(b,n)=1}$ e ${r= b\mod n}$ . Ou seja, todo inteiro coprimo com ${n}$ é congruente a um e só um elemento de ${S}$ .

Para ${n\geq 1}$ , um conjunto com ${\varphi(n)}$ inteiros incongruentes entre si módulo ${n}$ e coprimos com ${n}$ é chamado de sistema completo de invertíveis módulo ${n}$ . Equivalentemente, um conjunto ${S\subset {\mathbb Z}}$ tal que ${\mathrm{mdc}(a,n)=1}$ para todo ${a\in S}$ e tal que para todo ${z\in{\mathbb Z}}$ com ${\mathrm{mdc}(z,n)=1}$ existe um único ${a\in A}$ tal que ${a\equiv z \pmod n}$ é um sistema completo de invertíveis módulo ${n}$ .

Por exemplo ${\{1,3,5,7\}}$ , ${\{\pm1,\pm3\}}$ e ${\{\pm5,\pm7\}}$ são sci módulo ${8}$ .

Exercício 49 Seja ${S}$ um scr módulo ${n}$ qualquer. Mostre que os elementos de ${S}$ coprimos como ${n}$ formam um sci módulo ${n}$ .

Em vista disso, um sci também é chamado de sistema reduzido de restos módulo ${n}$ .

Proposição 37 Se ${S}$ é um sci módulo ${n}$ então para todo ${a}$ coprimo com ${n}$ o conjunto ${a\cdot S}$ é um sci módulo ${n}$ .

Demonstração: Tome ${S=\{x_1,x_2,\dots,x_{\varphi(n)}\}}$ um sistema completo de invertíveis módulo ${n}$ e forme o conjunto ${a\cdot S =\{ax_1,ax_2,\dots,ax_{\varphi(n)}\}}$ para ${a}$ coprimo com ${n}$ . Como ${a}$ é invertível módulo ${n}$ , então

$\displaystyle ax_i\equiv ax_j \pmod n \Rightarrow x_i\equiv x_j\pmod n \Rightarrow i = j ,$

ademais ${\mathrm{mdc}(ax_i,n)=1}$ para todo ${i}$ , ou seja, os ${\varphi(n)}$ elementos de ${a\cdot S}$ são incongruentes entre si e invertíveis módulo ${n}$ . $\Box$

— O Teorema de Euler —

Teorema 38 (Teorema de Euler) Sejam ${a,n\in{\mathbb Z}}$ , ${n>0}$ e ${\mathrm{mdc}(a,n)=1}$ . Então

$\displaystyle a^{\varphi(n)}\equiv 1 \pmod n. \ \ \ \ \ (68)$

Demonstração: Tome ${A=\{x_1,x_2,\dots,x_{\varphi(n)}\}}$ sci e consideremos ${a\cdot A}$ . Como, para cada ${i}$ vale ${\mathrm{mdc}(ax_i,n)=1}$ , devemos ter ${ax_i\equiv x_j \pmod n}$ para algum ${j}$ portanto, ${x_1x_2\cdots x_{\varphi(n)}a^{\varphi(n)}\equiv x_{1} x_{2}\cdots x_{\varphi(n)} \pmod n }$ e como cada ${x_i}$ é invertível módulo ${n}$ segue (68). $\Box$

Exemplo
${2|(n^{13} - n)}$ para todo ${n}$ pois ${n^{13} - n = n(n^{12} - 1)}$ e

$\displaystyle n^{12}-1 = (n-1)(n^{11}+n^{10}+\cdots+n+1)$

e ${2|n(n-1).}$ ${3|(n^{13} - n)}$ para todo ${n}$ pois

$\displaystyle n^{12}-1 = (n^2-1)(n^{10}+n^{8}+\cdots+n^2+1)$

e ${3|n}$ ou, pelo Teorema de Euler, ${n^2\equiv 1 \pmod 3}$ isto é ${3|n^2-1}$ . Ainda, ${5|(n^{13} - n)}$ para todo ${n}$ pois

$\displaystyle n^{12}-1 = (n^4-1)(n^{8}+n^{4}+1)$

e ${5|n}$ ou, pelo Teorema de Euler, ${n^4\equiv 1 \pmod 5}$ isto é ${5|n^4-1}$ .

Se ${\textrm{mdc}(a,n)=1}$ então ${aX\equiv b \pmod n}$ tem solução ${x}$ que é única módulo ${n}$ , e como ${a}$ é invertível

$\displaystyle x\equiv a^{\varphi(n)-1}b \pmod n \ \ \ \ \ (69)$

de modo que todas as soluções da congruência linear são

$\displaystyle x= a^{\varphi(n)-1}b+tn , \qquad \forall t\in{\mathbb Z} \ \ \ \ \ (70)$

agora, se ${\mathrm{mdc}(a,n)=d>1}$ e a congruência linear tem solução, então a congruência tem as mesmas soluções de ${\frac ad X \equiv \frac bd \pmod{\frac nd}}$ , de modo que, agora ${\frac ad}$ é invertível módulo ${\frac nd}$ e a única solução módulo ${\frac nd}$ é

$\displaystyle x= \left(\frac ad\right)^{\varphi(\frac nd)-1}\frac bd \ \ \ \ \ (71)$

e as ${d}$ soluções módulo ${n}$ são

$\displaystyle x\equiv \left(\frac ad\right)^{\varphi(\frac nd)-1}\frac bd + \frac nd t \pmod n , \qquad \forall t\in\{0,1,\dots,d-1\}. \ \ \ \ \ (72)$

— O Pequeno Teorema de Fermat revisitado —

Corolário 39 (Pequeno Teorema de Fermat) Seja ${a\in {\mathbb Z}}$ e ${p}$ um primo que não divide ${a}$ . Então

$\displaystyle a^{p-1}\equiv 1 \pmod p. \ \ \ \ \ (73)$

Equivalentemente

Teorema 40 (Pequeno Teorema de Fermat) Para todo ${a\in {\mathbb Z}}$ e todo primo ${p}$

$\displaystyle a^p\equiv a \pmod p. \ \ \ \ \ (74)$

Demonstração: Se ${p\not|a}$ , o resultado segue de (73). Se ${p|a}$ , então ${p|(a^p-a)}$ . $\Box$

A recíproca do teorema de Fermat não é verdadeira (verifique), mas vale o seguinte resultado.

Teorema 41 Sejam ${a,n >1}$ . Se ${\mathrm{mdc}(a,n)=1}$ , ${a^{n-1}\equiv 1 \pmod n}$ e ${a^k \not\equiv 1 \pmod n}$ para todo inteiro positivo ${k<n-1}$ então ${n}$ é primo.

Demonstração: Do Teorema de Euler temos ${a^{\varphi(n)}\equiv 1 \pmod n}$ , portanto, por hipótese, ${\varphi(n)\geq n-1}$ , donte temos ${\varphi(n) = n-1}$ . O teorema segue do exercício 48. $\Box$

— Exercícios —

Se ${n=kd}$ então ${|\{m\colon 1\leq m\leq n~e~\mathrm{mdc}(m,n)=d\}| =\varphi(k)}$ .
Mostre que se ${p}$ é primo ímpar então ${\{\pm 1,\pm 2,\dots,\pm (p-1)/2\}}$ é um sci módulo ${n}$ .
Mostre que se ${\mathrm{mdc}(a,n)=1}$ então
$\displaystyle i\equiv j\pmod{\varphi(n)} \Rightarrow a^i\equiv a^j \pmod n.$
Mostre que ${7}$ e ${13}$ dividem ${n^{13} - n}$ para todo ${n}$ .
Mostre que ${2730|n^{13}-n}$ .
Seja primo.
1. Prove que ${p}$ divide ${\binom pi}$ para todo ${i\in \{1,2,\dots,p-1\}}$ .
2. Prove que para inteiros ${x}$ e ${y}$ vale ${(x+y)^p \equiv x^p + y^p \pmod p}$ .
3. Prove, usando indução, que ${n^p \equiv n \pmod p}$ para todo natural ${n\geq 1}$ .
4. Deduza (73) a partir dos resultados obtidos acima.
Use o Pequeno Teorema de Fermat para provar que
1. ${13|(2^{70}+3^{70})}$ .
2. ${9|(n^3 + (n+1)^3 + (n+2)^3)}$ .
3. ${X^{13} + 12X +13Y^6 =1}$ não admite solução inteira.

— RSA —

Relembrando o protocolo de criptografia RSA:

Escolha dois números primos ${p}$ e ${q}$ e compute ${n:= p \cdot q}$ ;
Compute ${\varphi(n) = (p - 1) \cdot (q - 1)}$ ;
Escolha ${e \in \{ 2,3,\dots \varphi(n)-1\}}$ com ${\mathrm{mdc}(e,\varphi(n))=1}$ ; disponibilize o par ${(e, n)}$ , é a sua chave pública.
Compute ${d}$ tal que ${d \cdot e \equiv 1 \pmod{\varphi (n)}}$ e mantenha-o em segredo, a chave privada é o par ${(d, n)}$ .

Consideremos que uma mensagem é um natural ${m\in {\mathbb Z}}$ (por exemplo, ${m}$ é o número representado em base ${2}$ que o computador usa para gravar o arquivo com a mensagem no HD) tal que ${m<n}$ (isso não é uma restrição que põe tudo a perder, como foi explicado em sala, basta considerar o binário em blocos).

Para eu mandar-lhe a mensagem ${m}$ criptografada busco pela sua chave pública e calculo ${c:= m^e \mod n}$ e o envio. Você, que é o único portador da chave privada, calcula a ${c^d \mod n}$ e tem de volta a mensagem ${m}$ .

$\displaystyle c^d \mod n = (m^e \mod n)^d \mod n$

Notemos que, quaisquer inteiros ${a}$ e ${k\geq0}$ , vale ${a^k\equiv (a\mod n)^k \pmod n}$ . Assim, ${c^d \equiv (m^e)^d \pmod n}$ e de ${ed=1+r\varphi(n)}$ para algum ${r\in {\mathbb Z}}$