Esta pregunta se formuló en una oposición.
Hallar el resto de la división de $6^{83}+ 8^{83}$ por $49$
¿Existe algún teorema o regla para calcular la respuesta?
Respuestas
¿Demasiados anuncios?
clintp
Puntos
5127
Desde $6$ y $8$ son ambos coprimos a $49$ podemos aplicar Teorema de Euler . Tenemos $\varphi(49)=7^2-7=42$ , por lo que tenemos $$(6\times 8)(6^{83}+8^{83}) \equiv 6+8\equiv 14\mod 49$$ y observando que $6\times 8\equiv -1\bmod 49$ conseguimos que $$6^{83}+8^{83} \equiv (-1)^{-1}(6\times 8)(6^{83}+8^{83})\equiv -14\equiv 35\mod 49$$ por lo que el resto es $35$ .
hernan43
Puntos
477
Farkhod Gaziev
Puntos
6
Utilizando el teorema del Totiente de Euler,
Como $(6,49)=1$ y $\phi(49)=42$
$6^{42}\equiv 1\pmod {49}\implies 6^{42.k}\equiv1\pmod {49}$ donde es un número entero cualquiera. $\implies 6^{84}\equiv 1\pmod{49}\implies 6^{83}\equiv 6^{-1}\pmod{49}$
Por observación, $6\times 8=48\equiv -1\pmod{49}\implies 6\times (49-8)\equiv 1\pmod{49}\implies 41\equiv 6^{-1}\pmod{49}$
De la misma manera, $8^{84}\equiv 1\pmod{49}\implies 8^{83}\equiv 8^{-1}\pmod{49}$ como $(8,49)=1$
Como, $6\times 8=48\equiv -1\pmod{49}$ Así que $(49-6)\times 8\equiv 1\pmod {49}\implies 43\equiv 8^{-1}\pmod{49}$
Por lo tanto, el resto sea $43+41=84\equiv 35\pmod{49}$ .
David HAust
Puntos
2696
$\begin{eqnarray}\rm{\bf Hint}\ \ \ mod\ \phi(49)\!\!&:&\rm\,\ \color{#C00}{83}\equiv -1\ \ \ by\ \ \ \phi(49) = \phi(7^2) = 7\cdot 6 = 42_{\phantom{\frac{c}{c}}}\\ \Rightarrow\ \rm mod\ 49\!\!&:&\,\ 6^{\color{#C00}{83}}\!+\,8^{\color{#C00}{83}}\equiv\, \dfrac{1}6+\dfrac{1}8\,\equiv\,\dfrac{8+6}{8\cdot 6}\,\equiv\, \dfrac{14}{-1\ }\,\equiv\, 35\end{eqnarray}$
$\begin{eqnarray}\rm and\ \ \ \ mod\ \phi(p^2)\!\!&:&\rm\,\ \color{#C00}{\bf K}\equiv -1\\ \Rightarrow\ \rm mod\ p^2\!\!&:&\rm\,\ (p\!-\!1)^{\color{#C00}{\bf K}}\!+\!\,(p\!+\!1)^{\color{#C00}{\bf K}}\!\equiv \dfrac{1}{p\!-\!1}\!+\!\dfrac{1}{p\!+\!1}\equiv\dfrac{2p}{p^2\!-\!1}\equiv \dfrac{2p}{-1\ }\equiv p(p\!-\!2)\equiv \phi(p)\!-\!p\end{eqnarray}$
