This question was asked in a competitive exam.
Find the remainder of dividing $6^{83}+ 8^{83}$ by $49$
Are there any theorems/rules to compute the answer ?
This question was asked in a competitive exam.
Find the remainder of dividing $6^{83}+ 8^{83}$ by $49$
Are there any theorems/rules to compute the answer ?
Since $6$ and $8$ are both coprime to $49$, we can apply Euler's theorem. We have $\varphi(49)=7^2-7=42$, so we have $(6\times 8)(6^{83}+8^{83}) \equiv 6+8\equiv 14\mod 49$ and observing that $6\times 8\equiv -1\bmod 49$ we get that $6^{83}+8^{83} \equiv (-1)^{-1}(6\times 8)(6^{83}+8^{83})\equiv -14\equiv 35\mod 49$ thus the remainder is $35$.
Use the formula for $(a+b)^n$ for $(7-1)^{83}+(7+1)^{83}$
Using Euler's Totient theorem,
As $(6,49)=1$ and $\phi(49)=42$
$6^{42}\equiv 1\pmod {49}\implies 6^{42.k}\equiv1\pmod {49}$ where is any integer. $\implies 6^{84}\equiv 1\pmod{49}\implies 6^{83}\equiv 6^{-1}\pmod{49}$
By observation, $6\times 8=48\equiv -1\pmod{49}\implies 6\times (49-8)\equiv 1\pmod{49}\implies 41\equiv 6^{-1}\pmod{49}$
Similarly, $8^{84}\equiv 1\pmod{49}\implies 8^{83}\equiv 8^{-1}\pmod{49}$ as $(8,49)=1$
As, $6\times 8=48\equiv -1\pmod{49}$, so $(49-6)\times 8\equiv 1\pmod {49}\implies 43\equiv 8^{-1}\pmod{49}$
So, the remainder be $43+41=84\equiv 35\pmod{49}$.
$\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}$