Divisibilidade de 45

por pedrodemargomes Ter 05 Abr 2016, 10:17

Mostre que 45 divide 6^120 - 3^120.

por **Carlos Adir** Ter 05 Abr 2016, 21:08

Para que o nḿero seja divisivel por 45, énecessário que seja divisivel por 9 e por 5 simultaneamente.
Podemos ver que:
$\\ \mathrm{6 \equiv 1 \pmod{5}} \\ \mathrm{6^{120} \equiv 1 \pmod{5}} \\ \mathrm{3^{4} \equiv 1 \pmod{5}} \\ \mathrm{3^{120}\equiv \left(3^{4} \right )^{30} \equiv 1^{30} \equiv 1 \pmod{5}} \\ \therefore \mathrm{6^{120}-3^{120} \equiv 1 -1 \equiv 0 \pmod{5}}$
Agora, podemos provar que é multiplo de 9 fatorando:
$\mathrm{6^{120}-3^{120}=2^{120}\cdot 3^{120}-3^{120} = 3^{120}\left(2^{120}-1 \right )=9^{60}\left(2^{120}-1 \right )}$
Ou seja, se é multiplo de 5 e de 9, então é multiplo de 45.

por pedrodemargomes Ter 05 Abr 2016, 21:39

Obrigado pela resposta, estava tentando fazer sem usar o mod.

por **Carlos Adir** Ter 05 Abr 2016, 22:09

Bem, mostrar que 2^(120) - 1 é multiplo de 5 pode ser um pouco complicado, mas há como:
$\\ \mathrm{2^{4} - 1 = 16 - 1 = 15 = 5 \cdot 3} \\ \mathrm{2^{8} - 1 = 256 - 1 = 255 = 5 \cdot 51}$
Será que 2^(4k) -1 é multiplo de 5 toda vez? Podemos ver que:
$\\ \mathrm{2^{4k}=16^{k}=\left(15+1 \right )^{k}=15^{k}+\binom{k}{1}15^{k-1}+\cdots+\binom{k}{k-1}15+1} \\ \mathrm{2^{4k} - 1 = 15 \left(15^{k-1}+\binom{k}{1}15^{k-2}+\cdots+\binom{k}{k-2}15+\binom{k}{k-1} \right )}$
Que é multiplo de 5 toda vez.