Question

Teorema de Euler (Álgebra)

Dado dois inteiros m e n com mdc(m,n) = 1, tem-se que

$\mathsf{n^{\phi(m)}\equiv1\,(mod\,m)}$

Onde $\phi(\cdot)$ é a função Phi de Euler, que, para cada inteiro n, retorna a quantidade de inteiros menores que n que são coprimos com n

Algumas propriedades importantes de $\phi$:

$\bullet\,\,\mathsf{mdc(m,n)=1\,\,\,\Longrightarrow\,\,\,\phi(m\cdot n)=\phi(m)\cdot\phi(n)}\\\\\bullet\,\,\mathsf{\phi(p)=p-1,\,\,onde\,\,p\,\,\'e\,\,primo}}$
________________________________

Encontre o resto da divisão de $\mathsf{32^{8}+15^{16}}$ por $\mathsf{480=32\cdot15}$.

Answer 1

Olá Niiya.


Queremos determinar o resto da divisão de $\mathsf{32^{8}+15^{16}}$, por 480.


Sabemos que 480 = 32 . 15. Aplicando congruência mod 15, temos.


$\mathsf{32^{8}+15^{16}\equiv32^{8}~(mod~15)}\\\\\\\mathsf{32^{8}+15^{16}\equiv2^{8}~(mod~ 15)}$

Vamos verificar agora quantos inteiros positivos menores que 15 são primos com o 15, atavés da fução phi.

$\mathsf{\phi(15)=\phi(3\cdot5)}\\\\\\\mathsf{\phi(15)=(3-1)\cdot(5-1)}\\\\\\\mathsf{\phi(15)=8}$

Como o mdc(2, 15) = 1, temos que.


$\mathsf{32^{8}+15^{16}\equiv2^8~(mod~15)}}\\\\\\\mathsf{32^{8}+15^{16}\equiv1~(mod~15)}$


Aplicando agora congruência mod 32, temos.


$\mathsf{32^{8}+15^{16}\equiv15^{16}~(mod~32)}$

Se p é primo e a um inteiro positivo, temos que:

$\mathsf{\phi(p^a)=p^a-p^{a-1}}$

Calculando o phi de 32.

$\mathsf{\phi(32)=\phi(2^5)}\\\\\\\mathsf{\phi(32)=2^4\cdot(2-1)}\\\\\\\mathsf{\phi(32)=16}$


Como o mdc(32, 15) = 1, temos que.


$\mathsf{32^{8}+15^{16}\equiv15^{16}~(mod~32)}\\\\\\\mathsf{32^{8}+15^{16}\equiv1~(mod~32)}$


Então temos que:

$\mathsf{15~|~32^{8}+ 15^{16}-1~~~~e~~~~32~|~~32^{8}+15^{16}-1}$

Logo, $\mathsf{32^8+15^{16}-1}$ é multiplo comum de 15 e 32, portanto, também é multiplo comum do menor multiplo comum entre 15 e 32.

mmc(15, 32) = 15 . 32 = 480

Dessa forma:

$\mathsf{32^8+15^{16}-1\equiv0~(mod~480)}\\\\\\\mathsf{32^{8}+15^{16}\equiv1~(mod~480)}$

Então o resto é 1.


Dúvidas? Comente.